Lucas Primality Test | Python3 program for Lucas Primality Test ; Function to generate prime factors of n ; If 2 is a factor ; If prime > 2 is factor ; This function produces power modulo some number . It can be optimized to using ; Base cases ; Generating and storing factors of n - 1 ; Array for random generator . This array is to ensure one number is generated only once ; Shuffle random array to produce randomness ; Now one by one perform Lucas Primality Test on random numbers generated . ; This is to check if every factor of n - 1 satisfy the condition ; If a ^ ( ( n - 1 ) / q ) equal 1 ; If all condition satisfy ; Driver code
import random NEW_LINE import math NEW_LINE def primeFactors ( n , factors ) : NEW_LINE INDENT if ( n % 2 == 0 ) : NEW_LINE INDENT factors . append ( 2 ) NEW_LINE DEDENT while ( n % 2 == 0 ) : NEW_LINE INDENT n = n // 2 NEW_LINE DEDENT for i in range ( 3 , int ( math . sqrt ( n ) ) + 1 , 2 ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT factors . append ( i ) NEW_LINE DEDENT while ( n % i == 0 ) : NEW_LINE INDENT n = n // i NEW_LINE DEDENT DEDENT if ( n > 2 ) : NEW_LINE INDENT factors . append ( n ) NEW_LINE DEDENT return factors NEW_LINE DEDENT def power ( n , r , q ) : NEW_LINE INDENT total = n NEW_LINE for i in range ( 1 , r ) : NEW_LINE INDENT total = ( total * n ) % q NEW_LINE DEDENT return total NEW_LINE DEDENT def lucasTest ( n ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT return " neither ▁ prime ▁ nor ▁ composite " NEW_LINE DEDENT if ( n == 2 ) : NEW_LINE INDENT return " prime " NEW_LINE DEDENT if ( n % 2 == 0 ) : NEW_LINE INDENT return " composite1" NEW_LINE DEDENT factors = [ ] NEW_LINE factors = primeFactors ( n - 1 , factors ) NEW_LINE rand = [ i + 2 for i in range ( n - 3 ) ] NEW_LINE random . shuffle ( rand ) NEW_LINE for i in range ( n - 2 ) : NEW_LINE INDENT a = rand [ i ] NEW_LINE if ( power ( a , n - 1 , n ) != 1 ) : NEW_LINE INDENT return " composite " NEW_LINE DEDENT flag = True NEW_LINE for k in range ( len ( factors ) ) : NEW_LINE INDENT if ( power ( a , ( n - 1 ) // factors [ k ] , n ) == 1 ) : NEW_LINE INDENT flag = False NEW_LINE break NEW_LINE DEDENT DEDENT if ( flag ) : NEW_LINE INDENT return " prime " NEW_LINE DEDENT DEDENT return " probably ▁ composite " NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT print ( str ( 7 ) + " ▁ is ▁ " + lucasTest ( 7 ) ) NEW_LINE print ( str ( 9 ) + " ▁ is ▁ " + lucasTest ( 9 ) ) NEW_LINE print ( str ( 37 ) + " ▁ is ▁ " + lucasTest ( 37 ) ) NEW_LINE DEDENT