Check if a number is Fermat Pseudoprime | Python3 program to check if N is Fermat pseudoprime to the base A or not ; Function to check if the given number is composite ; Check if there is any divisor of n less than sqrt ( n ) ; Effectively calculate ( x ^ y ) modulo mod ; Initialize result ; If power is odd , then update the answer ; Square the number and reduce the power to its half ; Return the result ; Function to check for Fermat Pseudoprime ; If it is composite and satisfy Fermat criterion ; Else return 0 ; Driver code ; Function call
from math import sqrt NEW_LINE def checkcomposite ( n ) : NEW_LINE INDENT for i in range ( 2 , int ( sqrt ( n ) ) + 1 , 1 ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT DEDENT return 0 NEW_LINE DEDENT def power ( x , y , mod ) : NEW_LINE INDENT res = 1 NEW_LINE while ( y ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % mod NEW_LINE DEDENT y = y >> 1 NEW_LINE x = ( x * x ) % mod NEW_LINE DEDENT return res NEW_LINE DEDENT def Check ( n , a ) : NEW_LINE INDENT if ( a > 1 and checkcomposite ( n ) and power ( a , n - 1 , n ) == 1 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 645 NEW_LINE a = 2 NEW_LINE print ( Check ( N , a ) ) NEW_LINE DEDENT