blob: a8bc1424bfd08120d062a1de5dd435588a50accc (
plain)
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
'''
This module implements simple prime generation and primality testing.
'''
from random import SystemRandom
random = SystemRandom()
from os import urandom
def exp(x, n, m):
'''Efficiently compute x ** n mod m'''
y = 1
z = x
while n > 0:
if n & 1:
y = (y * z) % m
z = (z * z) % m
n //= 2
return y
# Miller-Rabin-Test
def prime(n, k):
'''Checks whether n is probably prime (with probability 1 - 4**(-k)'''
if n % 2 == 0:
return False
d = n - 1
s = 0
while d % 2 == 0:
s += 1
d /= 2
for i in xrange(k):
a = long(2 + random.randint(0, n - 4))
x = exp(a, d, n)
if (x == 1) or (x == n - 1):
continue
for r in xrange(1, s):
x = (x * x) % n
if x == 1:
return False
if x == n - 1:
break
else:
return False
return True
# Generate and Test Algorithms
def get_prime(size, accuracy):
'''Generate a pseudorandom prime number with the specified size (bytes).'''
while 1:
# read some random data from the operating system
rstr = urandom(size - 1)
r = 128 | ord(urandom(1)) # MSB = 1 (not less than size)
for c in rstr:
r = (r << 8) | ord(c)
r |= 1 # LSB = 1 (odd)
# test whether this results in a prime number
if prime(r, accuracy):
return r
def get_prime_upto(n, accuracy):
'''Find largest prime less than n'''
n |= 1
while n > 0:
n -= 2
if prime(n, accuracy):
return n
|
