This is a small collection of random code snippets I done while working on some crypto stuff.
Solovay-Strassen primality test (Python)
requires the jacobi function from below
# Solovoy-Strassen primality test (probabilistic)
# http://en.wikipedia.org/wiki/Solovay%E2%80%93Strassen_primality_test
import sys
import random
from jacobi import jacobi
def primeTest(n, tests):
s = set()
for i in range(1,tests+1):
# draw random number never used before
while True:
a = random.randint(1,n-1)
if a in s:
continue
else:
s.add(a)
break
if n == 2: return "yes, 2 is prime (obviously)"
if n % 2 == 0: return "not prime (input is even)"
# calculate jacobi and fermat
j = jacobi(a,n)%n
l = (a**((n-1)/2))%n
if l != j:
return "not prime!"
out = "possibly prime with probability of ",str(100.0-(1.0/2**(tests)*100.0)),"%"
return "".join(out)
def main(argv):
if len(argv) < 2:
print "no argument given"
print "try: ./solovay-strassen.py "
else:
print primeTest(int(argv[0]), int(argv[1]))
if __name__ == "__main__":
main(sys.argv[1:])
Calculates the Jacobi Symbol (Python)
# calculates the jacobi symbol
# http://en.wikipedia.org/wiki/Jacobi_symbol
import sys
import math
def ggT(a,b):
while 1:
r = a % b
if r == 0:
return b
else:
a = b
b = r
def jacobi(n,m):
if ggT(n,m) != 1: return "error in jacobi, ggT(n,m) not 1"
if n == 1: return 1
if n%2 == 0:
if m%8 == 3 or m%8 == 5: return (-1)*jacobi(n/2, m)
else: return jacobi(n/2, m)
if n>m: return jacobi(n%m, m)
if n%4 == 3 and m % 4 == 3: return (-1)*jacobi(m,n)
else: return jacobi(m,n)
def main(argv):
print jacobi(int(argv[0]), int(argv[1]))
if __name__ == "__main__":
main(sys.argv[1:])
Pollard's Roh Algorithm for finding factors (C)
#include
#include
int ggT(a,b) {
int r=0;
while (1) {
r = a % b;
if (r==0) { return b; break; }
a = b; b = r;
}
}
long f(x) {
return (long)pow(2,x) + 1;
}
int main() {
int n, x, y, d;
scanf("%d",&n);
x = 2; y = 2; d = 1;
while (d == 1) {
x = f(x) % n;
y = f(f(x)) % n;
d = ggT(n, abs(x-y));
}
if (d == n) {
printf("error, input %d is prime?\n", n);
} else {
printf("%d\n", d);
}
return 0;
}
Pollard's Roh Algorithm for finding factors (Python)
import sys
import random
def f(x):
return (x**2) + 1
def ggT(a,b):
while 1:
r = a % b
if r == 0:
return b
else:
a = b
b = r
n = input()
x = 2
y = x
d = 1
while d == 1:
x = f(x) % n
y = f(f(x)) % n
d = ggT(x-y, n)
if d == n:
print 'error, n seems to be prime'
else:
print d
Quadratic residue of prime n (Python)
# outputs all quadratic residues for given prime number n
import sys
import math
def quadResidue(n):
i=0
for a in range(1,n):
if a**((n-1)/2) % n == 1:
print(a)
i = i+1
print "Number of residues of prime", n, "found:", i
def main(argv):
quadResidue(int(argv[0]))
if __name__ == "__main__":
main(sys.argv[1:])