Modular arithmetic (clock arithmetic) is a system of arithmetic of integers. The basic ingredient is the congruence relation $a \equiv b \bmod n$ which means that $n$ divides $b-a$. In modular arithmetic one can add, subtract, multiply and exponentiate but not divide in general. The Euclidean ...
4
votes
0answers
47 views
Statement about Woodal primes.
A Woodal number is an integer of the form $n 2^{n}-1$.
A Woodal prime is an integer that is both a prime and a Woodal number.
Let $p$ be a prime of the form 1 mod 4.
Then $p 2^{p} -1$ is never a ( ...
3
votes
0answers
107 views
Number of elements in projective special linear group over $\mathbb{Z}/n\mathbb{Z}$
While reading a paper about the modular group $\Gamma = PSL_2(\mathbb{Z})$, I came upon the following sentence ($\Gamma(N)$ is the kernel of the canonical map $PSL_2(\mathbb{Z}) \rightarrow ...
2
votes
0answers
28 views
Is there any relation between the modular inverse of the same integer under different modulus?
I mean, suppose
$$ab \equiv 1 \mod{m}$$
$$ac \equiv 1 \mod{n}$$
I wonder if there is any relation between $b$ and $c$?
Could we compute one from another?
Thanks in advance!
2
votes
0answers
27 views
For which minimal $k$ true is that ${4}^{k}\cdot n\leq \displaystyle\sum^{n}_{i=1}{a}_{i}^{k}\leq {5}^{k}\cdot n$, ${a}_{i}\in {1,2,3,4,5,6}$?
I've got the following inequality, which bounds Minkowski distance.
${4}^{k}\cdot n\leq \displaystyle\sum^{n}_{i=1}{a}_{i}^{k}\leq {5}^{k}\cdot n$
and values of ${a}_{i}\in {1,2,3,4,5,6}$
We know all ...
2
votes
0answers
22 views
Name for summation that returns GCD(k,n)
Define
$$
H(k,n)=2\sum_{i=1}^{n-1}\left\lfloor\frac{ki}{n}\right\rfloor\;.
$$
We can prove that $H(k,n)=nk-k-n+\gcd(k,n)$. Does this $H$ carry some known name?
2
votes
0answers
34 views
eliminate very kth element in mod n… save a given element for last
we are given 1....n numbers. lets say we are to save a given number element k for last in elimination. We start eliminating them in the following manner.
I eliminate 1 at first. Then eliminate the ...
2
votes
0answers
45 views
How much information do I gain from each modular inequality?
Problem details:
Let $p = 2^{48}$, $s\leftarrow\{0,1\}^{48}$, and $a,b$ known constants.
Furthermore let $f(x) = a x + b \pmod{p}$
and let the value $r_k$ be defined by the first-order recurrence ...
2
votes
0answers
98 views
A system of linear equations in integer squares - solvable?
I consider this more a "recreational math" problem, possibly lacking a solution (because it stems from the question of "magic square of squares") or simply intractable with reasonable effort.
...
2
votes
0answers
84 views
Baby-step giant-step algorithm
I have equation in form $a^x = p (\textrm{mod q})$, knowing $p, q, a$.
I have to use Shank's algorithm (Baby-step giant-step).
I found some exercise and explanation on ...
2
votes
0answers
79 views
Multiplication structure for finite abelian rings of order $p^2$.
Consider an odd prime $p$ and a positive integer $a$ as close to 2 as possible that is not a quadratic residue $mod$ $p$.
If we extend the ring $mod$ $p$ with the element $b = a^{\frac{1}{2}}$ then ...
2
votes
0answers
31 views
Solving $key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$ with High limits
I was solving this equation:-
$$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$
Given
$$ 1,000,000,000 < a, n, m \; < 5,000,000,000 $$
$$ a, m \; are \;coprime $$
I solved it bruteforcely but it ...
2
votes
0answers
155 views
$a^{(b^c)} \mod m$ where $c$ can be very very large
I am trying to solve the following problem.
I need to find the value of
$$
a^{(b^x)} \bmod m
$$
where $a,b$ are integers and
$$
x = \pmatrix{n\\0}^2 + \pmatrix{n\\1}^2 + ... + \pmatrix{n\\n}^2 ...
2
votes
0answers
96 views
Determining maximum value of $a^b\bmod N$ when $\gcd(a,b)$ is known
Suppose we know the greatest common divisor, $\gcd(A,B)$, of two numbers $A$ and $B$.
Is there a way that we can find the maximum value of $a^b \bmod N$ where $N$ is any number?
We have a finite ...
1
vote
0answers
38 views
Revised: Primes of form $p \equiv m \in S \mod x \ $
Refer to this question for background.
I was speculating if there was an elegant way to define sequences
A007645,A002313,A045357,A045407,A042986,A045331,
A045425,A045374,A045400,A045350,A042988;
...
1
vote
0answers
18 views
Synthetic Division with mods
$x^4+x+1$/
$2x^2$+1
In $F_5$ (means mod 5)
I said let the leading coefficient be 2.
Since $3$ $*$ $2$ - $5$ $*$ $1$ $=$ $1$, choose 3 to multiply
$3$($2x^2$ $+$ $1$)= $x^2$ + $3$ (this is ...
1
vote
0answers
37 views
Last 2 digits of modular exponentiation
Is there any shortcut way to find the last two decimal digits of a modular exponentiation (base always is a single digit number) without doing square and multiply?
As an example in
$$2^{100001} ...
1
vote
0answers
52 views
A discrete question about modulo
I need conditions for $a, b, c$ such that the system $x \equiv a \pmod{15}$, $x \equiv b \pmod{21}$, $x \equiv c \pmod{35}$ has a unique solution $\pmod{105}$. It must be proved that conditions are ...
1
vote
0answers
49 views
Legendre Symbol, find the value of $\frac{p}{q}$ for all combinations
Legendre Symbol, find the value of $\frac{p}{q}$ for all combinations of $p=7,11,13$ and $q=227$
My thought:
$(7, 227)$ are distint odd primes, same for $(11,227)$ and $(13, 227)$
thus, ...
1
vote
0answers
73 views
Order of kernel of a homomorphism
Let $p,q$ be distinct primes. Prove that the kernel of the map $$f: (\mathbb{Z}/p^k\mathbb{Z})^* \rightarrow (\mathbb{Z}/p^k\mathbb{Z})^*$$ defined by $f(x)=x^q$ has order $\gcd(p-1,q).$
Thank ...
1
vote
0answers
144 views
Binomial coefficient modulo prime power without generalized Lucas theorem
I've been working on this problem computing n choose r for large n and r, modulo a composite.
I could implement the generalized lucas theorem to handle the prime power case, but I want to understand ...
1
vote
0answers
75 views
Residue division algorithm
What is the current state of the art method for determining, the residue of a large integer $k$ modulo $m$?
The only useful idea I can think of, which Ive seen used in base 10, is if $k$ was written ...
1
vote
0answers
77 views
Cycle of remainders
Let $N, K, W$ be natural numbers
If I start from $R_0$, say any integer $r_0, 0 \lt r_0 \lt N$
and proceed with:
$$R_j = ( R_{j-1} + K ) \mod W,\quad j=1,2, \dots$$
(that is the remainder of the ...
1
vote
0answers
61 views
Need help simplifying an equation.
I'm trying to speed up the following code:
sum = 0
for (k = 1 ... N) {
f = Fibonacci(k);
for (a = 1 ... 24)
for (b = 1 ... 24)
for (c = 1 ... 24) {
sum = sum + m(a, b, c) // ...
1
vote
0answers
127 views
How to proof this equation without calculating the values it self
I have the following equation.
$$(X + a)^n\equiv(X^n + a)(X^r - 1)\bmod n.$$
This is part of the AKS algorithm.
The problem is, that I'll have to solve this equation for every $1\leq a<10$ and ...
1
vote
0answers
44 views
Understanding of Pollard rho factorization
I am trying to better understand the ideas and intuition behind the Pollard Rho factorization algorithms.
Given an $x_0$ and an irreducibe polynomial we can create a sequence from the recursive ...
1
vote
0answers
149 views
Modular multiplicative inverse and coprime numbers needed.
I have a 64 bit algorithm that uses modular multiplicative inverse and coprime numbers, and I need to convert it to 32 bit. This math is not my area, and I cannot find an online calculator, so I hope ...
1
vote
0answers
57 views
Modular simple equation
Let's say I have three known numbers : $a$, $b$ and $m$.
I want to find the smallest $x$ so that $a.x \equiv b\ (mod\ m)$ (the product of $a$ and $b$ is congruent to $b$ modulo $m$).
In the cases ...
1
vote
0answers
123 views
Lucas' theorem Consequence
Lucas' theorem consequence
$$\binom {m}{n}=\ \prod_{i=0}^k\;\ \binom {m_i}{n_i} \pmod{p},$$
$$m=m_k\;p^k+m_{k-1}\;p^{k-1}+\cdots +m_1\; p+m_0,$$
$$n=n_k\;p^k+n_{k-1}\;p^{k-1}+\cdots +n_1\;p+n_0$$
...
1
vote
0answers
84 views
Generalizing a result on sums involving Euler's function
Motivation: It's known that there is a constant $0<K$ such that for any natural number $N$, $KN\leq \frac{\varphi(1)}{1}+\frac{\varphi(2)}{2}+\cdots+\frac{\varphi(N)}{N}$ (with $\varphi$ being ...
1
vote
0answers
49 views
Finding the random $r$ in a Paillier encrypted message with knowledge of the private key.
In the Paillier cryptosystem, suppose that I know a Ciphertext encrypted with some unknown random $r$ i.e.
$$C = (g^m r^n) \bmod n^2 $$
I know $g, n$, the prime factorization of $n$, i.e., $pq$. I ...
1
vote
0answers
85 views
How do you find small coefficients that satisfy a particular modular equation
Let's say $p=16301$.
How do I best find sets of small values for $a$, $b$ and $c$ for an equation like
$$a p^3+b p^2+c p=11263 \mod\ 2^{16}.$$
I can use the ...
1
vote
0answers
83 views
Computing a generating set of the kernel of a module
Given a generating set of a $\mathbb{Z}$-module $M \subseteq {\mathbb{Z}_k}^n$, is there a known algorithm to compute a generating set of $\{u \in {\mathbb{Z}_k}^n \, : \, \forall v \in M \quad v ...
1
vote
0answers
89 views
Find $x$ satisfying $x^a\ \textrm{mod}\ b \geq c$ where $a$, $b$, and $c$ are known
If $a$, $b$, and $c$ are known, is there an efficient way to find values of $x$ which satisfy $x^a\ \textrm{mod}\ b \geq c$ ?
1
vote
0answers
487 views
Solving Diffie–Hellman problem for low primitive root
What's a good way of solving the Diffie–Hellman problem when those exchanging the message have chosen a low primitive root $g$ (e.g. $g=3$)?
Of course you could brute force it but I'm interested in ...
0
votes
0answers
13 views
What value minimizes the error from a set of values under modular arithmetic?
I'm working with real numbers using modular arithmetic, say in the range [0,12). I would like to calculate some kind of 'modular mean' over a set of values $X$ that minimizes the total error. In other ...
0
votes
0answers
20 views
Possible to solve a set of congrueces for an unknown divsor?
Recently I started learning about the Chinese remainder theorem and its possibility to solve a set of congruences. Now, for the Chinese remainder theorem you always start from a set of equations from ...
0
votes
0answers
35 views
How do I find $m^q\pmod p$ if I already have the following values
I have $g^k\pmod p$, $m\cdot h^k\pmod p$. I also know that $g$ is ìn the set $\{1, 2, \cdots, p-1\}$ and $g$ is of order $q$, so I believe that means that $g^q = 1\pmod p \Rightarrow 1 = g^q\pmod p$. ...
0
votes
0answers
23 views
Can this function with modulo and truncated division be simplifed?
Can this function with modulo and truncated division (DIV) be simplifed?
f(x)=(x%c)*r+DIV(x,c)%r
Basically, I use this ...
0
votes
0answers
30 views
How do I find the set of integers solving a system of equations that contain outliers?
I have a system of $s$ equations that should (but won't) all equal some real unknown scalar value, $x$:
$x = v_1*k_1 + a_1*k_1*m = v_2*k_2 + a_2*k_2*m = ... = v_s*k_s + a_s*k_s*m$
where,
$k_i$ are ...
0
votes
0answers
10 views
A simple inequality in modular analysis (real domain)
I have a question regarding the solution of the inequality
$$
k\Delta \text{ mod } 1<\varepsilon,
$$
where $k\in\mathbb{N}^+$ and the two parameters $\Delta,\varepsilon \in[0,1)\subset\mathbb{R}$ ...
0
votes
0answers
35 views
Minimum of a linear congruence sub-sequence
I have the following little problem : let $a,b,u,v$ be four given integers with $\gcd(a,b)=1$. Now I would like to find the minimum of the linear congruence subsequence $\{ax \pmod b : u \le x \le ...
0
votes
0answers
53 views
a question from modular arithmetic
Given $a,b$ in $Z_N$* for some composite positive integer N. Let the bit sizes are $a_N , b_N , N_N$ respectively.
Also $a_N = (N_N$ or $N_N-1) , a<N , (a,N)=1$
$ b_N = (N_N$ or $N_N-1) , ...
0
votes
0answers
83 views
Solving systems of linear congruences with rational coefficients
Is there any way to solve for $x$ in a system of linear congruences with rational coefficients in the following form?
$$Ax \equiv b\pmod 2, \space where\space A \in \Bbb Q^{n,m}, b \in \Bbb Q^m$$
...
0
votes
0answers
64 views
Floor function within a congruence
In essence, the floor function is causing problems. Is there any way to get the inner linear expression, outside of the floor function?
$\lfloor(a_1x_1+...+a_nx_n)/d\rfloor \equiv b\pmod m$,
for ...
0
votes
0answers
51 views
Using modular arithmetic for the decimal byte ring, compute the following…
Using modular arithmetic for the decimal byte ring,
Compute: $5 + (- 175+222)*13 = ~?$
This is a question I'm supposed to understand before I start a assembly language course next semester. Can ...
0
votes
0answers
53 views
Distribution of binary digits in moduli
Considering the (infinite) set of all positive integers that are a product of $2$ primes only,
represented in binary $100...01$.
Question: is the distribution of the proportion of $0,1$ digits ...
0
votes
0answers
149 views
Computing square roots modulo prime powers
I am trying to implement an algorithm that can compute the square root of a quadratic residue mod a prime power. For integers $a$ such that
$p\not\mid a$
$p\neq 2$
it's relatively straightforward ...
0
votes
0answers
82 views
Calculate equation using the Shank's algorithm
I have euqaiton with form $a^x = p (\textrm{mod}\ q)$, knowing $a,p,q$. My task is to determine $x$ using Shank's algorithm.
I have no idea how to do it. Can you give me an advice?
Thanks :)
0
votes
0answers
56 views
Pollard $p-1$ factorization
I need some help understanding this algorithm. I want to factor $n$. Suppose $n$ has a factor $p$ s.t. the primes that divide $p-1$ are less than $10,000$. And $p-1$ divides $10000!$.
Let $m = ...
0
votes
0answers
326 views
Hill cipher known-plaintext attack with unknown alphabet
I'm trying to understand a cryptanalysis of a variant of the Hill cipher using an unkown alphabet through a known-plaintext attack.
The classic Hill cipher use an $n\times n$ inversible matrix
$K
...
