### Abel51's blog

By Abel51, history, 3 months ago,

### Congruence

The congruence equation is one of the fundamental concepts in number theory:

Let $m$ be a given positive integer, and let $a$ and $b$ be integers. If $m\mid(a−b)$, then $a$ is congruent to $b$ modulo $m$, denoted as $a\equiv b\pmod m$ or $a\equiv b(m)$.

Other forms of expressing congruence include:

• $a=b+km$
• $a$ and $b$ have the same remainder when divided by $m$

Properties of congruence equations:

• If $a_1\equiv b_1\pmod m$ and $a_2\equiv b_2 \pmod m$, then $a_1 + b_1 \equiv a_2 + b_2 \pmod m$
• If $a\equiv b \pmod m$, then $a\equiv b + km\pmod m$, where $k$ is an integer
• If $a_1\equiv b_1 \pmod m$ and $a_2\equiv b_2 \pmod m$, then $a_1 b_1\equiv a_2 b_2 \pmod m$

Finding the smallest positive integer solution for the congruence equation $ax \equiv 1 \pmod b$ involves transforming the equation into $ax+by=1$ and using the Extended Euclidean Algorithm (EXGCD) to solve it.

### EXGCD

The fundamental equation is to find $ax+by=1$, for instance, $8x+3y=1$.

A step-by-step breakdown is performed to arrive at a solution:

• If $a < b$ in the equation $ax + by = 1$, no modifications are needed.
• When $a$ and $b$ are not coprime in the equation $ax + by = 1$, adjustments are necessary.
• For an equation in the form $ax + by = c$, the algorithm needs to be adjusted by dividing $a$, $b$, and $c$ by their greatest common divisor ($\gcd$) to yield a coprime equation. The final result using EXGCD yields $x=\frac{c}{\gcd(a,b)}$ and $y=0$.
• To find specific solutions or multiple solutions, adjustments are made to ensure $x$ is a positive minimum. Techniques like % operations or loops are employed to handle these cases.

### Multiplicative Inverse (Modular Inverse)

Addition and multiplication operations are modular-friendly, but division isn't. Multiplicative inverse, denoted as $b^{-1}$ with respect to modulo $p$ (where $p$ is a prime number), satisfies the equation $(b\times b^{-1}) \pmod p = 1$. The range of $b^{-1}$ is $[0,p-1]$.

• Fermat's Little Theorem states that if $p$ is a prime number and integer $a$ is not a multiple of $p$, then $a^{p-1}\pmod p=1$.
• For a prime $p$, the modular inverse of $a$ is $a^{p-2}$, often computed using fast exponentiation techniques.
• If $p$ is not prime, the EXGCD method is employed to solve $b\times b^{-1} \equiv 1 \pmod p$, provided $b$ and $p$ are coprime. If they aren't, the inverse doesn't exist.
• Linear preprocessing from $1$ to $p-1$ can be utilized to compute inverses efficiently by using $a=p \text{ mod } i$ and $b=\frac{p}{i}$.
• +9

By Abel51, history, 4 months ago,

NOI Gold Coach Wang_Xiaoguang taught me last weekend.

The $\text{Miller Rabin}$ algorithm is a randomization algorithm used to test whether an integer is a prime. It is based on Fermat's small theorem and quadratic detection theorem, and determines whether an integer may be a prime number through multiple random tests. The basic idea of the algorithm is to perform a series of randomness proofs, and if an integer passes these tests, it is likely to be a prime number. If an integer fails any of these tests, then it is definitely not a prime number.

The following are the basic steps of the $\text {Miller Rabin}$ algorithm: 1. Select the integer $n$ to be tested: First, select an integer $n$ greater than $1$ to determine if it is a prime number.

1. Decomposing $n-1$ into $2^t\times u$: Calculate the prime factorization of $n-1$, where $u$ is an odd number and $t$ is a non negative integer, representing the number of factors $2$.

2. Select Random Evidence Number $a$: Randomly select an integer $a$ from the interval $[2,n-2]$.

3. Calculate $v=a^u \mod n$: Calculate the modulus of $n$ to the power of $u$ of $a$, and obtain $v$.

4. Check if $v$ is equal to $1$:

• If $v=1$, then continue with the next round of testing and choose a new random evidence number of $a$.

• If $v$ is not equal to $1$, go to the next step.

1. Repeat square detection $t$times:
• Perform the $t$ sub square operation on $v(v=v ^ 2\mod n)$ while checking if $v$ is equal to $n-1$.

• If $v=n-1$, continue with the next round of testing and select a new random evidence number of $a$.

• If $v$ is not equal to $n-1$, continue the square operation and check up to a maximum of $t-1$ times.

1. Check the final result:
• If $v$ is still not equal to $n-1$ after $t$ squared detection, then $n$ is considered not a prime number and can be determined to be a composite number.

• If $v$ equals $n-1$ after $t$ tests, then $n$ may be a prime number and continue with the next round of testing.

1. Repeat multiple tests: Repeat the above steps and select different random evidence numbers $a$ for testing. Usually, repeated testing multiple times can improve the accuracy of the algorithm.

Summary: The reliability of the $\text{Miller Rabin}$ algorithm depends on the selection of iteration times and random evidence numbers. Usually, conducting multiple tests (such as $15$ or more) and selecting a random number of evidence can make the algorithm highly reliable in practice, but it is still a random algorithm. Therefore, although it can quickly exclude most composite numbers, it cannot provide absolute proof.

Code:

import random
def millerRabin(n):
if n<3 or n%2==0:
return n==2
u,t=n-1,0
while u%2==0:
u=u//2
t=t+1
test_time=8
for i in range(test_time):
a=random.randint(2,n-1)
v=pow(a,u,n)
if v==1:
continue
s=0
while s<t:
if v==n-1:
break
v=v*v%n
s=s+1
if s==t:
return False
return True
t=int(input())
for i in range(t):
x=int(input())
y=millerRabin(x)
if y==True:
print("YES")
if y==False:
print("NO")

• +17