Questions tagged [modular-arithmetic]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
3 views

Logarithm and squareroot in prime fields

I got an interresting question. Introduction: Let p be a prim number and $a,b\in \mathbb{Z}$ with $ggT(a,p)=1$ and $\exists r\in \mathbb{Z}:r^2\equiv a\mod p$ aswell as $\exists l\in \mathbb{Z}:b^l\...
1
vote
1answer
43 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
116 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
32 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
43 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
53 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
51 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
100 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
43 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
74 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
41 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
38 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
28 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
48 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
30 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
161 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
27 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
52 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
56 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
34 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
38 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
108 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
61 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
222 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
59 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
82 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
47 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
62 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
127 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
532 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
78 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
472 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
59 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
205 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
737 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
88 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
532 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
3k 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
120 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.
-1
votes
1answer
60 views

Time required for mod operation [closed]

Let $x,y,n$ be $1234567809, 12345, 9087654321$. My laptop can perform 1 64-bit mod operation in 1 microsecond. Estimate the number of seconds needed for each of the following: Find $x^y \pmod{n}$ ...
1
vote
1answer
327 views

Sum of two elements in set evenly divisible by k

I have gone through this particular problem in hackerrank. You are given an array of $n$ integers, $a_0, a_1, a_2 , \ldots, a_n$, and a positive integer $k$. Find and print the number of pairs $(i,...
4
votes
2answers
323 views

Curious about an old algorithm which calculates modular inverse

I am not sure if I should ask this question here or somewhere else. In fact, I initially asked my question here at mathoverflow.net but it was marked as off-topic Background: I was searching through ...
4
votes
2answers
311 views

Calculating modulus of large non-factored numbers

The internet is full of algorithms to calculate the modulo operation of large numbers that have the form $a^e \bmod p$. How about numbers with unknown factorization. More precisely, let's say I have a ...
1
vote
0answers
80 views

Parallel algorithm for Chinese remainder theorem

What is the most efficient (in terms of running time) algorithm that solves the Chinese remainder theorem (CRT) on a set of integer residues. That is, given a set of moduli $\{m_i\}_{i=1}^{r}$ and set ...