Questions tagged [modular-arithmetic]
The modular-arithmetic tag has no usage guidance.
86
questions
1
vote
3
answers
72
views
n (mod k) circuit
I wondered if, for a fixed integer k ≥ 3, the divisibility by k is in P/poly.
How can I construct a boolean circuit for each n ∈ N, that takes as input an n-bit integer x and outputs whether 3|x?
The ...
- 23
1
vote
0
answers
21
views
Algorithm for checking whether a set of hyperplanes covers $\mathbb{Z}_r^n$
In what follows, $r \in \mathbb{N}$ is not necessarily prime. $\mathbb{Z}_r$ is shorthand for $\mathbb{Z}/r\mathbb{Z}$.
Given a set of $h$ hyperplanes $A \vec x = b \mod r$, we can check whether the ...
- 378
3
votes
2
answers
176
views
Floating-point modular multiplication algorithm
Is there a well-known algorithm for modular multiplication of floating-point numbers?
I would like to multiply some large angle in single precision (6-7 significant digits) and wrap it back to 360 ...
- 33
0
votes
1
answer
69
views
Within the set of signed integers representable by a bit string of length n, are any two elements equivalent to each other mod 2^n?
Donald Knuth's The Art of Computer Programming, Volume 1 Fascicle 1 contains the following exercise:
If $\alpha$ is any string of 0s and 1s, let $\operatorname{s}(\alpha)$ and $\operatorname{u}(\...
- 101
2
votes
1
answer
55
views
Are there any mathematical properties of consecutive integer power modulo operations that could be exploited for algorithmic speed gain?
I'm attempting to search through all the integers between 10^15 and 10^16 to check if they are in the oeis sequence A277274, and the entirety of the program can be summarized as mostly equivalent to :
...
- 153
2
votes
1
answer
290
views
Understanding Rabin-Karp's rolling hash computation
Possibly related to this. Let $T$ be the text and $n$ be the length of the pattern. I understand that if substrings of $T$ are interpreted as base-$d$ numbers where $d$ is the alphabet's size, then ...
- 183
1
vote
1
answer
29
views
Universal class $\mathcal{H}_{p, m}$ of hash functions has $p(p-1)$ members
In CLRS it is stated that the class $\mathcal{H}_{p, m} = \{ h_{ab}:\mathbf{Z}_p \to \mathbf{Z}_m \mid a \in \mathbf{Z}_p^*, b \in \mathbf{Z}_p\}$, $h_{ab}(x) = (ax+b) \mod p \mod m$, $m < p$ prime ...
- 13
2
votes
0
answers
61
views
Fastest algorithm for polynomial multiplication in 256-bit finite fields
I am looking for the fastest algorithm (in practice) to multiply two polynomials $f(X)\cdot h(X)$ in $\mathbb{F}_p[X]$. The prime $p$ is roughly $256$ bits but the integer $p-1$ might not have any ...
- 93
2
votes
0
answers
40
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 ...
- 469
1
vote
1
answer
88
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
2
votes
0
answers
36
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
0
answers
55
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
1
answer
263
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 ...
- 33
1
vote
0
answers
44
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
0
votes
2
answers
240
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
1
answer
101
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
2
votes
1
answer
198
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 ...
- 353
3
votes
2
answers
191
views
Find a vector of non-negative integers $b$ that minimizes $\prod_{i = 1}^{D}\left(a_i + b_i\right)$ such that the product is a multiple of $c$
I'm trying to come up an efficient algorithm that, given a list of positive integers $a = \left(a_1, \ldots, a_D\right)$ and positive integer $c$, finds a list of non-negative integers $b = (b_1, \...
- 133
1
vote
1
answer
101
views
RSA Encryption for specitic messages x with x = ap mod pq for ap-bq=1
I want to make a following proof but I got some difficulties with it.
Would be super if you people have any tips / advises.
Introduction:
Let (N,e) be our public key and (N,s) our private key with $N=...
2
votes
3
answers
451
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
0
votes
1
answer
50
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
2
votes
0
answers
166
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 ...
- 21
0
votes
1
answer
124
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
3
answers
68
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
2
votes
2
answers
316
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
0
answers
54
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
0
answers
204
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
2
votes
1
answer
84
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,453
2
votes
1
answer
47
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 ...
-1
votes
1
answer
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.
...
- 251
0
votes
2
answers
122
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
1
answer
54
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
2
votes
4
answers
203
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
0
votes
1
answer
53
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 <...
- 105
1
vote
0
answers
168
views
How is the modular multiplication matrix unitary in Shor's Algorithm?
I have been reading papers about the construction of this matrix in Shor's Algorithm all night. The behavior of the controlled modular multiplication matrix is described as
$$C U_{a^{2}}(|c\rangle|y\...
- 11
2
votes
1
answer
66
views
Exercise 11 of section 3.2.2(The art of computer programming)
I'm asking about its part a.
a) If $f(z),\space a(z),\space b(z)$ are polynomials with integer coefficients, let
us write $a(z)\equiv b(z) (\operatorname{mod} f(z)\space and\space m)$
if $a(z) = b(z) ...
0
votes
0
answers
83
views
Solving a modular equation programmatically
Consider that I've a mathematical equation of the form:
$$ (6+4\times x)\text{ } mod\text{ } 22 = 0 $$
How can I solve this modular equation by using a program, efficiently? By trial and error, one ...
- 169
1
vote
1
answer
35
views
Given $L$ and $D$ find $X, \text { such that } X * 10^L + D \equiv 0 \mod M$
Given $L$ and $D$ find $X, \text { such that } X * 10^L + D \equiv 0 \mod M$. Integer $M$ is given and it is the same for all calculations however we need to solve for $X$ for more different numbers. ...
- 1,408
2
votes
1
answer
50
views
Conditions for maximum period of quadratic congruential method (PRNG)
$X_{n} = (d^2X_{n-1} + aX_{n-1} + c) \operatorname{mod} m$
Knuth lists out the necessity and sufficiency of 4 conditions (Exercise 8 in page 49 of "The art of computer programming Vol.II"):
$c$ ...
2
votes
2
answers
29
views
An approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$
Consider a prime finite field $\mathbb{F}_p$ of quite large characteristics $p$, for example $\log_2(p) \approx 256$ bits. I would like to know an approximate quantity of multiplications in $\mathbb{F}...
- 141
3
votes
1
answer
125
views
Last digit of polynomial value
There is a simple-looking problem.
Given integer coefficients $c_{0}, c_{1}, c_{2}, \dots, c_{n - 1}$ of polynomial $$ p(x) = c_{0} + c_{1} x + c_{2} x^{2} + \dots + c_{n - 1} x^{n - 1} $$ and ...
- 155
1
vote
0
answers
76
views
Sum of long geometric progression [closed]
Finding sum of a geometric progression is simple when we just need to report the sum,
but when some modulo or multiplicative inverse is asked of that sum the task become tedious for me.
I have a ...
- 11
1
vote
1
answer
343
views
Checking Divisibility Using Minimal Bits
Suppose we're given an infinite stream of integers, $x_1, x_2, \dots$.
a) Show that we can compute whether the sum of all integers seen so far is divisible by some fixed integer $N$ using $O(\log ...
- 163
2
votes
0
answers
93
views
Modular reduction in a finite field
Let $\mathbb{F}_p$ be a finite field of prime order $p$. Define $r_q : \mathbb{F}_p \to \mathbb{F}_p$ as $r_q (x) = x \bmod q$ with $q<p$. A tad more formally, treat $x$ as an integer in $[0, p)$ ...
- 21
0
votes
2
answers
85
views
Given $0 <(x, y) < z < 2^{64}$, How can I compute $\lfloor \frac{xy}{z} \rfloor$ using only 64-bit arithmetic operations?
I can compute this easily in the case that $xy < 2^{64}$. But I'm not sure how to do this if $xy \geq 2^{64}$.
I know that $\lfloor \frac{xy}{z} \rfloor = \frac{xy - (xy\ \text{mod} \ z)}{z}$, but ...
1
vote
0
answers
77
views
Equality checking mod $10$ via arithmetic circuits
I'm interested in implementing equality checking mod 10 in an arithmetic circuit.
Is this possible? Preliminary evidence points towards "no", but I thought it best to ask before completely writing it ...
- 288
0
votes
1
answer
82
views
Efficient way to compute mod(w +1) or mod(w - 1) where w= 2^p
Knuth in his book provides a method of how to efficiently calculate mod(w +1) or mod(w-1) where w is a power of 2. I am not sure I could understand his assembly language completely.
Could you explain ...
4
votes
0
answers
159
views
Optimal parallel-time repeated modular squaring circuit
Given a 4096-bit integer $x$ and a 4096-bit RSA modulus $N$ (of unknown factorisation) what is the fastest circuit to compute $x^{2^T} \mod N$ where $T=2^{40}$. That is, what is the fastest parallel-...
- 133
1
vote
4
answers
803
views
What is the big-$\Omega$ complexity of Fermat's Little Theorem?
Fermat's Little Theorem states that if an integer $n$ is prime them
$$
a^n \equiv a \pmod n \hspace{10mm} (*)
$$
for any $a \in \mathbb{N}$
My question is, is it correct to say that testing $(*)$ for ...
- 467
0
votes
0
answers
40
views
What is the complexity of checking whether $f(x) \equiv g(x) \hspace{3mm} (\text{mod } h(x), n)$?
Can anyone please help me to understand what the complexity of checking whether
$$
f(x) \equiv g(x) \hspace{3mm} (\text{mod } h(x), n)
$$
might be? This notation denotes that $f(x)$ is congruent to $g(...
- 467