Questions tagged [modular-arithmetic]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
38 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 ...
0
votes
2answers
70 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, ...
1
vote
1answer
36 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 ...
2
votes
1answer
44 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 ...
3
votes
2answers
168 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, \...
0
votes
0answers
41 views

Logarithm and square root in prime fields

I got an interesting question. Introduction: Let $p$ be a prime number and $a,b\in \mathbb{Z}$ with $\gcd(a,p)=1$ and $\exists r\in \mathbb{Z}:r^2\equiv a\mod p$ as well as $\exists l\in \mathbb{Z}:b^...
1
vote
1answer
56 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
3answers
168 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 ...
0
votes
1answer
35 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-...
2
votes
0answers
64 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 ...
0
votes
1answer
68 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
3answers
52 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 ...
2
votes
1answer
153 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 ...
1
vote
0answers
46 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], ...
1
vote
0answers
99 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 (...
2
votes
1answer
47 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 ...
2
votes
1answer
40 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
1answer
31 views

Problem with the modulus calculation

I am trying to solve the following calculation, but I can't find the suitable value for B. ...
0
votes
2answers
52 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 ...
1
vote
1answer
34 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 ...
2
votes
4answers
177 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.
0
votes
1answer
31 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 <...
1
vote
0answers
78 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\...
2
votes
1answer
58 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
0answers
40 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 ...
1
vote
1answer
28 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. ...
2
votes
1answer
40 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
2answers
28 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}...
3
votes
1answer
112 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 ...
1
vote
0answers
64 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 ...
1
vote
1answer
241 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 ...
2
votes
0answers
68 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)$ ...
0
votes
2answers
84 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
0answers
48 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 ...
0
votes
1answer
76 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
0answers
141 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-...
1
vote
4answers
619 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 ...
0
votes
0answers
38 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(...
0
votes
2answers
82 views

How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime?

This question is specifically related to https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm The $gcd(x,y)$ is solved in $O(T(n) log n)$, where $n$ is the number of bits ...
-1
votes
1answer
1k views

Calculating mod of n^k mod p in O(log k)

Given $n>0$, $k>0$, and a prime number $p$, compute: $$n^k\mod p$$ in $O(\log k)$ time. Here $x \mod y$ means the remainder for $x$ being divided by $y$. For example, $2^3\mod 7 = 1$. You assume ...
0
votes
0answers
37 views

A question of congruence modulo concept. (Optimization Required)

I have an arr[] of M integers. He has to find all integers K such that : 1) K > 1 2) arr[1]%K = arr[2]%K = arr[3]%K = ... = arr[M]%K where '%' is a modulus operator with following constraints : - 2&...
2
votes
1answer
548 views

Meaning of $|w| ≡ 2 \mod 3$

I'm new to formal language and automata theory and I was left alone with this exercise. The task is to define a formal grammar for given language. $Σ \in \{a,b\}$ $L = \{ w \in Σ^*\, |\, |w| \...
1
vote
1answer
60 views

Finding solutions to $n m\equiv x \mod n$

Given a modulus $n\in\mathbb{N}$ and another natural number $0<x<n$, what's an efficient algorithm to enumerate all pairs of natural numbers $(a,b)\in\mathbb{N}^2$ such that both $a$ and $b$ are ...
3
votes
1answer
261 views

Smallest multiple of a number that gives a specific remainder modulo another number

Given three positive integers $a, b$ and $c$, my task to find the smallest positive integer $k$ such that $(k * a) \mod b = c$. I can obviously try values of $k$ from $1$ and higher, until I find the ...
1
vote
2answers
802 views

modular arithmetic in rolling hash algorithm

My question was around the rolling hash function in RobinKarp algorithm. It is intuitive for me to understand how to get from xi to xi+1 without the mod, however with the mod i am not sure how we ...
-1
votes
1answer
1k views

Calculating greatest common divisor and least common multiple modulo prime number

I'm trying to solve pretty complex problem with number theory and set of numbers. To make the problem more clear we are going to define $GCD(a, b)$ as the greates number that divides both $a$ and $b$...
2
votes
2answers
91 views

Is there an algorithm for a number line from $0$ to $n$

Where $n + 1 = 0$ and $0 - 1 = n$? The $n + 1 = 0$ case can be achieved by using the modulus operator, but I can't figure out how to treat the $0 - 1 = n$ case.
3
votes
1answer
658 views

3-SAT and Systems of Nonlinear Modular Equations

How is the 3-SAT problem reduced to solving for a system of nonlinear modular equations? I have read https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete in how to ...
9
votes
2answers
4k views

modular multiplication

I was reading the Modular Multiplication page on wikipedia...and could not understand the algorithm to compute $a \cdot b \pmod{m}$. ...
0
votes
1answer
129 views

Adding a character in the middle (rolling hash)

Is there a way to support adding characters in the middle and update the hash in O(1) ? All I have is the hash of ABBDE and I want to get the hash of ABBCDE.