""" primetest.py: Goal: check whether the Fermat test ("ftest" below) is a good test for primality. Failing this, check more elaborate test (Fermat tests with bases different from 2) are good tests. Examples: >>> check(ftest, 2, 200) >>> check(test, 2, 1000) >>> test2 = lambda n: xtest(n, [2,3,5,7]) >>> check(test2, 2, 10000) """ def modpower(b,e,m): """modpower(b,e,m) = b^e mod m""" P = 1 S = b while e > 0: r = e%2 e = e/2 if r == 1: P = P*S % m S = S*S % m return P ftest = lambda n: modpower(2,n-1,n) # ^^^ Fermat test g = lambda a, n: modpower(a,n-1,n) # ^^^ Fermat test with base a def test(n): """Conjunction of two Fermat tests""" if g(2,n) == 1 and g(3,n) == 1: return 1 else: return 0 def xtest(n,L): """Auxilliary function for Fermat test on a list L of bases""" for a in L: if g(a,n) != 1: return 0 return 1 def isprime(n): """Stupid primality test (trial division)""" if len(td(n)) == 1: return 1 else: return 0 def xxtd(n): d = 2 factors = [] while n >= d*d: if n % d == 0: factors.append(d) n = n/d else: d = d + 1 if n > 1: factors.append(n) return factors def td(n): d = 2 factors = [] while n >= d*d: if n % d == 0: factors.append(d) n = n/d else: d = d + 1 if n > 1: factors.append(n) return factors def check(f,a,b): """check the test 'f' on integers in [a,b)""" for n in range(a,b): if f(n) == 1 and len(td(n)) > 1: print n