-
Notifications
You must be signed in to change notification settings - Fork 0
/
Fermat_primes_tester
61 lines (55 loc) · 1.57 KB
/
Fermat_primes_tester
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import Sieve_of_Eratosthenes
import random
def Fermat_Comp_Test(p,a):
"""uses Fermat's theorem to test if a number is prime
Returns True if prime.
Usually returns False is composite.
Composites that return True need a different a.
At most the chances of finding a bad a are 1/2.
this means the probability of
incorrectly callling a composite prime is at most .5^(number of as tried)
the pow(x,y[,z]) operator which returns (x**y)%z (if a z is given else it gives x**y)
for speeding up fermat's theorem on paper the following could be used:
https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation"""
k=p-1
t=pow(a,k,p)
if t == 1:
return True
else:
return False
def gcd(a,p):
if p==0:
return a
else:
return gcd(p,a%p)
def a_chooser(p):
if p>200:
return random.randrange(2,200)
else:
return random.randrange(2,p)
def primes_tester(p):
"""Returns True if prime.
Usually returns False is composite."""
a=a_chooser(p)
if gcd(p,a) !=1:
return False
elif Fermat_Comp_Test(p,a)==False:
return False
else:
return True
def looped_primes_tester(p,certainty):
"""loops primes_tester(p) to avoid fools.
p is the number you want to test.
the certainty is the % chance of being wrong you are acceptable with"""
c=1
certainty=certainty/100
t=True
k=0
while t==True and k<certainty:
t=primes_tester(p)
c=c<<1
k=1-(1/c)
if t==True:
return True
else:
return False