Click here to Skip to main content
11,633,654 members (80,770 online)
Click here to Skip to main content

Tagged as

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

, 12 Dec 2013 CPOL 19.9K 169 10
Rate this:
Please Sign up or sign in to vote.
Review primality test algorithms and test their preformance in order to find out which is the fastest.

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

Number  Fermat/Naive Miller-Rabin/Naive
105 
10053 
1005415 
10054033243 
10054033321154111121  13  13 

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

Number Naive/Fermat Naive/Miller-Rabin
997  1 0 ( Naive is 2 time faster here )  
40487 
53471161  61  47 
1645333507  322  287 
188748146801  960 

661   

99194853094755497  313148 

385993  

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Shay Margalit
Student Software Engineering Intern
Israel Israel
No Biography provided

You may also be interested in...

Comments and Discussions

 
SuggestionComposite number performance test skewed Pin
Member 1109989721-Sep-14 23:30
memberMember 1109989721-Sep-14 23:30 
GeneralMy vote of 5 Pin
Tesfamichael G.21-Apr-14 6:36
memberTesfamichael G.21-Apr-14 6:36 
GeneralMy vote of 1 Pin
Member 884486027-Dec-13 0:48
memberMember 884486027-Dec-13 0:48 
General[My vote of 2] Some serious issues... Pin
Matt T Heffron4-Dec-13 8:41
professionalMatt T Heffron4-Dec-13 8:41 
GeneralRe: [My vote of 2] Some serious issues... Pin
Shay Margalit4-Dec-13 9:46
memberShay Margalit4-Dec-13 9:46 
SuggestionRe: [My vote of 2] Some serious issues... Pin
Matt T Heffron4-Dec-13 10:10
professionalMatt T Heffron4-Dec-13 10:10 
GeneralRe: [My vote of 2] Some serious issues... Pin
Shay Margalit4-Dec-13 10:46
memberShay Margalit4-Dec-13 10:46 
GeneralRe: [My vote of 2] Some serious issues... Pin
Member 96925308-Dec-13 21:55
memberMember 96925308-Dec-13 21:55 
GeneralRe: [My vote of 2] Some serious issues... Pin
Shay Margalit11-Dec-13 22:48
memberShay Margalit11-Dec-13 22:48 
GeneralRe: [My vote of 2] Some serious issues... Pin
Member 969253011-Dec-13 23:33
memberMember 969253011-Dec-13 23:33 
GeneralRe: [My vote of 2] Some serious issues... Pin
Shay Margalit12-Dec-13 1:03
memberShay Margalit12-Dec-13 1:03 
QuestionNumber 9 is showing as prime number Pin
tanmoysarkar2-Dec-13 22:27
membertanmoysarkar2-Dec-13 22:27 
AnswerRe: Number 9 is showing as prime number Pin
Shay Margalit3-Dec-13 2:08
professionalShay Margalit3-Dec-13 2:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150728.1 | Last Updated 12 Dec 2013
Article Copyright 2013 by Shay Margalit
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid