Questions tagged [modular-arithmetic]
The modular-arithmetic tag has no usage guidance.
88
questions
1
vote
4
answers
833
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
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(...
0
votes
2
answers
104
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
1
answer
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
0
answers
49
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
1
answer
941
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
1
answer
63
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
1
answer
540
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
2
answers
1k
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 ...
0
votes
1
answer
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
2
answers
93
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
1
answer
1k
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 ...
11
votes
2
answers
6k
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
1
answer
206
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
1
answer
61
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
1
answer
642
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
2
answers
341
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
2
answers
349
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
0
answers
108
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 ...
2
votes
1
answer
5k
views
Find Divisible Sum Pairs in an array in O(n) time
You are given an array of n integers a0, a1, .. an and a positive integer k. Find and print the number of pairs ...
-1
votes
1
answer
751
views
Can we evaluate a polynomial of degree N modulo M at all M points, faster than Θ(mn) time?
Given a polynomial $P(x)$ of degree $N$, evaluate $P(x) \bmod M$ at $x = 0$ to $M-1$, where $M$ is a prime number of order $10^6$. Can we do any better than $O(NM)$ given the constraints we only need ...
0
votes
1
answer
601
views
Taking the modulus of 2 arrays [closed]
I'm putting together a primality tester for large numbers. When the numbers were smaller things were more straightforwards. I got refined it to a point where I could quickly test any number within the ...
-1
votes
1
answer
97
views
How fast can one compute the power of a number?
Let $x \in \mathbb{R}$ and $k \in \mathbb{Z}^+ \cup \{0\}$ then how fast can one compute $x^k$?
If $x, k \in \mathbb{Z}$ then I guess this previous discussion already settled that, How many ...
5
votes
1
answer
758
views
Computing MOD_4 function using MOD_2, OR, AND, NOT gates
Define the $\newcommand{\MOD}{\text{MOD}}\MOD_q$ function from $\{0,1\}^n \rightarrow \{0,1\}$ as follows:
Let $x_1,\cdots,x_n$ be the input. Then $\MOD_q(x_1,\cdots,x_n)=0$ if the number of 1's in $...
1
vote
0
answers
40
views
How to compute multiplication in $ \mathbb{Z} / n\mathbb{Z} $? [closed]
Good day,
I have heard about the Montgomery modular multiplication, and the Barrett_reduction; (or any other) But in practice I don't understand how could I implement a multiplication algorithm in a ...
22
votes
2
answers
16k
views
What is the difference between modulo and modulus?
Throughout my education in computer science, I feel like I've heard the terms "modulo" and "modulus" used interchangeably. It looks like even Wikipedia claims that "modulo&...
1
vote
3
answers
2k
views
Is the empty string of even length?
There is this example of regular expressions:
$$(\Sigma\Sigma)^*= \{w\mid |w|\text{ is even}\}\,.$$
From that I understand the empty string is valid as a string of even length. Is this true?
1
vote
1
answer
40
views
Issues in RSA setup
Suppose we have public key: $$n= 1015, e= 3$$ and private key: $$d= 635, p= 35, q= 29, \phi(n)= 952$$
For $m = 100$, we have $$c = m^e ~mod~n = 100^3 mod~1015 = 225.$$
To decipher this, let us ...
2
votes
1
answer
247
views
Computing mod inverse?
How might one compute $4^{-1} \mod 17$ I know the answer is 13. I'm just not sure how to arrive at that number, and can't find any good explanations. Any help would be great
4
votes
1
answer
89
views
Computing modular exponent given order
I want to compute $g^{mn}$ mod $n^2$ where $n=pq$ and I know that $g$ has order $kn$ mod $n^2$ where $m<k$. Is there any clever way of doing it utilizing the order? I have tried other methods of ...
5
votes
1
answer
1k
views
Fixed base exponentiation with precomputations
I'm trying to compute $g^m$ mod $n$ where $m,n$ are 1024-bit numbers. The method I want to use is fixed base exponentiation with precomputations, also known as fixed-base windowing.The paper I'm ...
4
votes
3
answers
5k
views
How can I compute an exponential modulo a large integer?
Does anyone have the computational power to check whether or not
$F(m)^d \equiv m \pmod n$, where the values of the variables are found below.
According to Wolfram Alpha, I found the result of the ...
1
vote
1
answer
71
views
How do I compute the huge numbers which occur in el gamal decryption?
I'm trying to do decryption using el gamal. The formula to get the message M is
$$ M=\frac{b}{a^x} mod \:P $$ In one case, we may have $$ M=\frac{18}{62^{62}} mod \: 71 $$ This value cannot be ...
1
vote
1
answer
94
views
Finding Triples that satisfy modulo equation in $O(n\log n)$ time
Given $n$, I am trying to count the number of values $(a,b,c)$ that satisfy the following equation in $O(n\log n)$ time. I do not need the values themselves only the number of total values that ...
0
votes
1
answer
52
views
Dividing large numbers modulo m
I have numbers $a$, $b$ and $m$, and I need to get the result of $\ \dfrac{a}{b} \mod m$.
The catch is that while $m \leq 10^9$, $a$ and $b$ can get extremely large ($2^{100,000}$), so I'm keeping ...
1
vote
1
answer
244
views
Fast checking Matrix multiplication in mod 10
I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In ...
1
vote
2
answers
4k
views
Circuits for Modular Arithmetic
I've read this which describes how to do do integer arithmetic in circuits. The one thing that it does not describe is how to do these operations with a modulus. How can modular arithmetic be done in ...
2
votes
1
answer
584
views
Emulating boolean circuits using addition and multiplication (mod 5)
I'm trying to use gates that do addition and multiplication modulo 5 to emulate logic gates.
Assuming false and true are mapped to 0 and 1 respectively (with 2, 3, and 4 being invalid), I figured out ...