# 「Old Article」笔记：费马质数检验算法

### An Algorithm for detecting prime number (Primality Test)

##### 1. Fermat’s Little Theorem and its converse-negative proposition
• Fermat’s Little Theorem is introduced:If ​ is an integer, and ​ is a prime number, then ​ must be one of multiples of ​Which means that: ​Then we have:​ Then the commonly used format is:​
• If Fermat’s Little Theorem is true, then we have its converse negative proposition is true:If we have a number ​, and we randomly choose a number ​, if ​, then we know that the number ​ is a prime number.
##### 2. Operation
• In real operation, we choose a base number, for example, 2, and according to Fermat’s Little Theorem introduced above, we know that if ​, then ​ is very likely to be a prime number.
• But, the problem is that ​ is not easy to compute,
• To solve this problem, we have:​​
• And we notice that in binary system, we have:​​If we want to find the value of, for example, ​, that is to see if ​ is a prime number, and we find this is too difficult to compute, so we first turn 20 into binary representation:
``` bin(20)= 10100
​
and we can divide it into (2^[1010]_2 %21)^2%21
then we compute 2^[1010]_2%21
then we compute 2^[101]_2%21
then we compute 2^[101]_2%21= ((2^[10]_2%21)^2*2)%21
then we compute 2^[1]_2%21
then we compute (2^[0]%21)^2*2```
• Then we can start from the first number, for example, this question, we start from ‘1’ from ‘10100’:
```k= bin(20)[2:] #'10100'
length= len(k) #5
​
result = 1
​
for i in range(0, length):
result= result**2%21
if k[i]=='1':
result= (result* 2)%21```