Skip to content

Instantly share code, notes, and snippets.

@st0le

st0le/Fermat Test

Last active December 16, 2015 17:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save st0le/5472010 to your computer and use it in GitHub Desktop.
Save st0le/5472010 to your computer and use it in GitHub Desktop.
Download ZIP
Fermat Primality Test
Raw
Fermat Test
def fermatPass(n):
return n > 1 and ( n == 2 or ( n % 2 != 0 and pow( random.randint( 1, n - 1 ), n - 1, n ) == 1 ) )
def fermatTest(n,k = 10):
return all( fermatPass( n ) for i in xrange(k) )
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment