4 from itertools import combinations
15 if p.nbits() < sievebits: lab = LABEL[p] = '%d' % p
17 lab = LABEL[p] = '$%s.%d' % (name, SEQ)
28 lab = DONE[p] = label(p)
31 if pow(a, p - 1, p) != 1:
32 raise ValueError('%d not prime (%d is Fermat witness)' % (p, a))
35 g = gcd(pow(a, (p - 1)/q, p) - 1, p)
36 if 1 < g < p: raise ValueError('%d not prime (%d divides)' % (p, g))
37 if g != 1: win = False
40 POCK.append('pock %s = %d, %d, [%s]' %
41 (lab, a, (p - 1)/(2*r), ', '.join(ll)))
48 if p.nbits() < sievebits:
49 lab = DONE[p] = str(p)
54 qq = [q for (q, e) in factor((p - 1)/2)]
55 for n in xrange(1, len(qq) + 1):
56 for rr in combinations(qq, n):
59 if r < score: best, score = rr, r
61 best = list(best); best.sort()
64 name, p = argv[1], Integer(argv[2])
68 for q in sorted(SMALL): print 'small %d = %d' % (q, q)
71 qq = map(Integer, argv[3:])
72 for i in xrange(len(qq)): LABEL[qq[i]] = DONE[qq[i]] = 'q%d' % i
75 elif p%(2*q) != 1: raise ValueError('incorrect factorization')
76 if q^2 <= p: raise ValueError('factorization insufficient')
80 for line in POCK: print line
81 print 'check %s, %d, %d' % (name, p.nbits(), p)