# Questions tagged [modular-arithmetic]

The tag has no usage guidance.

78 questions
Filter by
Sorted by
Tagged with
1 vote
32 views

### Efficient algorithm to "lift" a number in CRT representation mod r to mod $r^2$

Integers between 0 and a square-free number $r$ minus one can be represented by their value modulo each of $r$'s prime factors, according the Chinese remainder theorem. Given a number represented like ...
1 vote
58 views

### Does the reliability of polynomial hashing depend on whether the modulus is prime, for coprime base and modulus?

A polynomial hash of a string $s$ with base $b$ and modulus $M$ is defined as $$H(s) = (s_0 + s_1 b + s_2 b^2 + \dots + s_{n-1} b^{n-1}) \mod M.$$ I have proven (and this is quite obvious) that ...
• 11
34 views

### upper bound on the smallest modulus for perfect hashing of a Huffman tree

Given a full binary tree with 256 leaves and depth <= 64, let H be the set of Huffman codes described by the tree (using 0 to go left, and 1 to go right, where ...
• 121
1 vote
52 views

### Find array of coprime integers whose average is maximized

I am creating a class to store large integers in a residue number system. I want each "integer" to be 4-12GB in size and be comprised of 64-bit moduli. These moduli must be pairwise coprime ...
1 vote
83 views

### Why modulo-2 arithmetic over n-bits doesn't produce single bit result?

I was studying CRC and came across modulo 2 arithmetic. When we add two 1 bit numbers like 1 + 1, 0 + 1, then the result is summation modulo 2 which is similar to XORing of the two bits. My doubt is ...
• 13
1 vote
40 views

### Montgomery multiplication -- algorithm question

I am a beginner, but I think I understand how to do Montgomery multiplication. Also, there are online calculators (for dummies like me)... But I have a paper in front of me, that is all about how to ...
• 111
116 views

### What algorithm is prefered to do a x b mod P with big numbers (256 bits)

I'm trying to implement multiple precision arithmetic operations modulo P, with P < 2^256. More specifically, ...
• 103
1 vote
70 views

### Which is (if any) the generic fastest method to perform modular exponentiation?

After a bit of surfing, I have found that Schönhage–Strassen (without taking in consideration recent optimizations) seems to be the base algorithm to perform the requested operation. Anyways, this ...
• 183
59 views

### Is quadratic nonresiduosity in $\textbf{NP}$?

The paper "The Knowledge Complexity of Interactive Proof Systems" uses the language of quadratic nonresidues defined via the following excerpt from page 293 as an example of constructing an ...
• 303
182 views

322 views

### Shortest path in modular arithmetic

Suppose we have 7 vertices, each of which corresponds to a different integer modulo seven. The edge exists between two vertices x and y if x + 3 ≡ y mod 7. For example, there is an edge between 0 and ...
• 202
40 views

### Algorithm to find slope of line with a modulus

Say I have some data which represents a single line, and I want to determine its approximate slope. This data has a known minimum and maximum on the y-axis. When the line crosses the maximum, it re-...
• 15
91 views

### Understanding CRC Computation with PCLMULQDQ

I am currently reading this paper which shows how to calculate CRC using the instruction PCLMULQDQ. I don't quite understand the equations in it yet. Starting with this one for the definition of ...
92 views

### Finding The Inverse of The Modulo Operation

I created an algorithm to convert a hexadecimal digit into an alphanumeric string, but now I want to create the inverse of this algorithm. The algorithm, in short, is as follows: hexadecimal digit %...
1 vote
55 views

### rolling around running numbers

I'm numbering generated files with two digits 00-99 and I want to retain the last 50. The algorithm should tell me the number of the current file that I'm about to save and which of the previous files ...
• 123
219 views

### How does Pollard's rho algorithm work?

I am trying to understand how does Pollard's rho algorithm actually work, but I just can not wrap my head around it. I already read its section in the CLRS book and ...
• 172
1 vote
51 views

### Optimization of modular exponentiation using fft [duplicate]

My math/cs professor said it is trivial to optimize a modular exponentiation ($a^b \bmod c$) problem using fft, yet I am not able to understand how to do this. I found 3 papers on this ([1], [2], ...
• 29
1 vote
133 views

### Optimization of modular exponentiation using fft

My math prof said it is trivial to optimize a modular exponentiation (a^b mod c) problem for large values using fft, but I can't figure out how to do this. I looked it up and found a few papers on it (...
• 29
63 views

### What is the time complexity of determining whether a solution $x$ exists to $x^k \equiv c \pmod{N}$ if we know the factorization of $N$?

Suppose we are given an integer $c$ and positive integers $k, N$, with no further assumptions on relationships between these numbers. We are also given the prime factorization of $N$. These inputs are ...
• 3,413
46 views

### How to prove properties about a specific modular arithmetic equivalence

Ever since I was introduced to modular arithmetic, I've had some trouble with it. I think it uses a part of my brain that I haven't used often. Anyways, I've been thinking about this specific ...
32 views

### Problem with the modulus calculation

I am trying to solve the following calculation, but I can't find the suitable value for B. ...
• 249
65 views

### What are the elements of the modular ring mod 7? [closed]

Are the elements of a modular ring simply the set of all the numbers from 1 to p−1? in this case p−1 = 6 ? I asked this on the math stack exchange https://math.stackexchange.com/q/3375667 and was ...
• 137
1 vote
42 views

### Simple generator of pseudo-random permutations of variable length short sequence

The problem in front of me is to write a function (from scratch) to permute n elements, where n is an argument. I decided to break it down to applying Knuth's shuffles algorithm, therefore I needed to ...
• 125
182 views

### how to calculate $2^{5000}$ mod 10 without calculator in fast way?

How is it possible to calculate $2^{5000}$ mod 10 without using a calculator in a fast way? The result with calculator was 6.
• 53
42 views

### Expressing unsigned comparison through signed comparison of 2's complement

Let n > 0 be a natural number and for any two reminders a, b modulo 2^n we have that <...
• 103
1 vote
125 views