素性测试算法 - 素性测试 - 检查数字素性的最快方法

• 下载源代码 - 1.98 KB

引言

在本文中，我将回顾一些素性测试算法，它们的实现（使用 Python），最后我们将测试它们的性能，以确定哪种算法最快。文章的第一部分将介绍算法实现，第二部分将介绍性能测试。 

我们将看到三种众所周知的素性测试

• 朴素算法
• 费马素性测试
• 米勒-拉宾素性测试

第一部分 - 实现

朴素素性测试

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  

费马素性测试 

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  

米勒-拉宾素性测试 

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 

第二部分 - 性能测试 

在理解了理论和实现之后，现在是时候确定哪种算法最快了。

我们将把测试分成两部分

• 合数性能
• 素数性能

为了衡量性能，我将使用“timeit”模块和以下代码

# 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

合数测试

数字	费马/朴素	米勒-拉宾/朴素
105	3	3
10053	1	2
1005415	2	1
10054033243	2	2
10054033321154111121	13	13

正如你所看到的，当我们尝试测试合数的素性时，米勒-拉宾和费马的性能几乎相同，但朴素测试比它们更快。我对此结果有点惊讶，但我认为下一个测试会显示不同的视角。

素数测试

数字	朴素/费马	朴素/米勒-拉宾
997	1	0 (朴素在这里快 2 倍)
40487	2	2
53471161	61	47
1645333507	322	287
188748146801	960	661
99194853094755497	313148	385993

因此，当我们测试素数的素性时，米勒-拉宾和费马比朴素快得多，得多。正如你所看到的，性能差异随着数字大小的增加而越来越大。最后一个数字不太大，但仍然需要我的电脑花费几分钟才能使用朴素素性测试进行测试 - 这让我明白，如果我想快速测试大数的素性，我会坚持使用更复杂的方法。