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. 2. 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$$$. 3. Select Random Evidence Number $$$a$$$: Randomly select an integer $$$a$$$ from the interval $$$[2,n-2]$$$. 4. Calculate $$$v=a^u \mod n$$$: Calculate the modulus of $$$n$$$ to the power of $$$u$$$ of $$$a$$$, and obtain $$$v$$$. 5. 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. 6. 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. 7. 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. 8. 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")