Primality

Checking for primality is one of the most elementary operations in number theory and as such we show two simple techniques to do so.

Trial Division

Trial division can be done by successive division of an integer n by all numbers less than the sqrt of n. As we technically only need to check if n is divisible by primes, we can reduce operations by performing divisions on a smaller set with greater prime density. Examples of such sets are the odd numbers Z+1, which can be further extended to the p-rough numbers.

Let SP be the set of primes less than or equal to an arbitrary prime p. Then let PR be the set of p-rough numbers. As PR set includes all primes greater than or equal to p we can speed up our primality check by only checking the divisibility of n by all the elements of PR less than the sqrt of n as long as we check if it is not any of the primes smaller than p


 trial_division(n)                

   if n ∈ SP                 

       return true                

   end if                         
 
  if ∃ x ∈ PR := x|n   

   return false                   
 
  end if                          

  return true

A proper implementation of this requires producing a generating function for the p-rough numbers. Suppose that we have a n such that n is the product of all primes less than p then we have the following generating function n * k ± x ∀ x ∈ S where S is the set of all primes in the interval [p;n/2]

We show an example using the 7-rough numbers

 
 trialdivision(n)                

  primorial <- 30   // 2*3*5             
 
  rough_gen <- [1,7,11,13]    // P - {2,3,5} + 1  

  primes    <- [2,3,5,7,11,13]   

  
  if n == 1                      

   return false                  

  end if                         

  
  for i in primes     // checks if n ∈ primes           

    if n == i                    

     return true                 

    end if                       

    if i|n           // checks if n is divisible by  i ∈ primes             

     return false                

    end if                       

   end for                       

   
 suprenum <- (sqrt(n)/primorial) + 1 

 
  for i in [1;suprenum]               

    for j in rough_gen                 

      if (primorial*i - j)|x ∨ (primorial*i+j)|x  

       return false                     

      end if                            

    end for                            

  end for                             

 return true

Fermat

The pseudoprime test. This checks if the condition a^p-1 = 1 mod p holds true. If so then a is called a weak witness to the primality of p. For instance we want to check the primality of 341, so we use 2 as the base and checking that 2³⁴⁰ mod 341 = 1. So 2 is a witness for the primality of 341. However if we factor 341 we see that it is infact composite (11*31) making 2 a Fermat liar.

SPRP

Fortunately there is a stronger condition that we can check. We first check if base^p mod p = 1 We rewrite a potential prime p into d*2^n -1 and then check if any integer in the interval [1;n] satisfies the condition that d*2^i mod p = p-1. Using our previous example we can break 341 into 341 = 85* 2^2 + 1, we pick the same base in the previous example {2} and evaluate 2^85 mod 341. The remainder is 32 which is both not equal to 1 and not equal to 340, so we then go to the next step. Using 32 as the new base we then perform the checks of each of the zeros in the intervals. First step 32^2 mod 341 = 1, as there are only two factors of 2 in 340 our job is complete and we never got a result of 340, meaning that it failed. We show a pseudocode implementation below.


 sprp(p,base)
    zeroes <- trailing_zeros(p-1) // Real implementation can be found in builtin_ctz (G++ C++) or trailing_zeros (Rust) or TZCNT (Intel instruction)
    
         d <- (p-1)/ 2^zeroes
         
         x <- base^d mod p 
         
     if x == 1u64 ∨ x==p-1
     
       return true
       
     end if 
     
    loop zeroes-1 times
    
       x <- x^2 mod p
       
      if x == p-1
      
        return true
        
      end if
      
    end loop 
    
  return false

Miller

Probabilistic

Given the SPRP we have before we can make a random test that shows primality with high probability.We do this by setting the base using a randomly-generated number. One thing to note is that you need a rand number in a specific range. It must be between 2 and p-2, we can use the simple function 2 + rand mod (p - 4) to ensure that.

Deterministic

To produce a deterministic check in a interval of numbers [1;2^64-1] we only need to check for a small range of bases


  det_miller(p) 

    base <- [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] 
    
    for i in base 

      if p == i   

        return true 

      end if 

     if sprp(p,i) == false 

       return false        

     end if                

   return true