Primality test algorithms - Prime test - The fastest way to check primialty of a number

• Download source - 1.98 KB

Introduction

In this article I will review some primality test algorithms, their implementation (in Python), and finally we will test their performance in order to determine which is the fastest. The first part of the article would present the algorithm implementations and the second part would present the performances tests. 

We will see three well known primality tests:

• The naive algorithm
• Fermat primality test
• Miller Rabin primality test

Part one - Implementation

Naive primality test

def simplePrimaryTest(number):
    if number == 2:
       return true
    if number % 2 == 0:
        return False
    
    i = 3
    sqrtOfNumber = math.sqrt(number)
    
    while i <= sqrtOfNumber:
        if number % i == 0:
            return False
        i = i+2
        
    return True  

Fermat primality test 

def FermatPrimalityTest(number):
    ''' if number != 1 '''
    if (number > 1):
        ''' repeat the test few times '''
        for time in range(3):
            ''' Draw a RANDOM number in range of number ( Z_number )  '''
            randomNumber = random.randint(2, number)-1
            
            ''' Test if a^(n-1) = 1 mod n '''
            if ( pow(randomNumber, number-1, number) != 1 ):
                return False
        
        return True
    else:
        ''' case number == 1 '''
        return False  

Miller Rabin primality test 

def MillerRabinPrimalityTest(number):
    '''
    because the algorithm input is ODD number than if we get
    even and it is the number 2 we return TRUE ( spcial case )
    if we get the number 1 we return false and any other even 
    number we will return false.
    '''
    if number == 2:
        return True
    elif number == 1 or number % 2 == 0:
        return False
    
    ''' first we want to express n as : 2^s * r ( were r is odd ) '''
    
    ''' the odd part of the number '''
    oddPartOfNumber = number - 1
    
    ''' The number of time that the number is divided by two '''
    timesTwoDividNumber = 0
    
    ''' while r is even divid by 2 to find the odd part '''
    while oddPartOfNumber % 2 == 0:
        oddPartOfNumber = oddPartOfNumber / 2
        timesTwoDividNumber = timesTwoDividNumber + 1 
     
    '''
    since there are number that are cases of "strong liar" we 
    need to check more then one number
    '''
    for time in range(3):
        
        ''' choose "Good" random number '''
        while True:
            ''' Draw a RANDOM number in range of number ( Z_number )  '''
            randomNumber = random.randint(2, number)-1
            if randomNumber != 0 and randomNumber != 1:
                break
        
        ''' randomNumberWithPower = randomNumber^oddPartOfNumber mod number '''
        randomNumberWithPower = pow(randomNumber, oddPartOfNumber, number)
        
        ''' if random number is not 1 and not -1 ( in mod n ) '''
        if (randomNumberWithPower != 1) and (randomNumberWithPower != number - 1):
            # number of iteration
            iterationNumber = 1
            
            ''' while we can squre the number and the squered number is not -1 mod number'''
            while (iterationNumber <= timesTwoDividNumber - 1) and (randomNumberWithPower != number - 1):
                ''' squre the number '''
                randomNumberWithPower = pow(randomNumberWithPower, 2, number)
                
                # inc the number of iteration
                iterationNumber = iterationNumber + 1
            '''     
            if x != -1 mod number then it because we did not found strong witnesses
            hence 1 have more then two roots in mod n ==>
            n is composite ==> return false for primality
            '''
            if (randomNumberWithPower != (number - 1)):
                return False
            
    ''' well the number pass the tests ==> it is probably prime ==> return true for primality '''
    return True 

Part two - Performance tests 

After we have understood the theory and the implementation, it's time to determine which is the fastest.

We'll divide the test into two:

• Performance for composite numbers
• Performance for prime numbers

In order to measure the performance, I'll use the "timeit" module and the following code:

# main loop
while True:
    ''' get number to test '''
    print "Enter the number you want to test:"
    number = int(raw_input())
    
    ''' break the loop if recived 0 '''
    if number == 0:
        break
    
    ''' test for primility '''
    if PrimalityTest.MillerRabinPrimalityTest(number) and PrimalityTest.FermatPrimalityTest(number):
        print number, "is prime"
    else:
        print number, "is not prime" 
    
    ''' time the algorithms. we repeat the test 100 times in order to get some
     significant time. '''
    naive       = timeit.timeit('import PrimalityTest;PrimalityTest.simplePrimaryTest('+str(number)+');',number=1000)
    Fermat      = timeit.timeit('import PrimalityTest;PrimalityTest.FermatPrimalityTest('+str(number)+');',number=1000)
    MillerRbin  = timeit.timeit('import PrimalityTest;PrimalityTest.MillerRabinPrimalityTest('+str(number)+');',number=1000)
    
    ''' print result '''
    print number, naive, Fermat,MillerRbin

Composite numbers test

As you can see, when we try to test composite numbers primality, Miller-Rabin and Fermat perform almost the same, but the Naive test is faster than both of them. I was a bit surprised to see this result, but I think that the next test would show a different perspective.

Prime numbers test

So, when we are testing prime numbers for primality, Miller-Rabin and Fermat are much, much faster than Naive. As you can see, the performance difference is getting bigger and bigger with the size of the number. The last number is not very big and still it took my computer a few minutes to test it with the naive primality test - that's what made me understand that if I want to test the primility of a big number fast, I would stick to the more sophisticated methods.