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

按:这篇文章写于2018年11月27日

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

Leave a Reply

Your email address will not be published. Required fields are marked *