(b,seed)
| 55 | 47,53,59,61,67,71,73,79,83,89,97) |
| 56 | |
| 57 | def getPrime(b,seed): |
| 58 | #Generates an integer of b bits that is probably prime |
| 59 | #written by Josiah Carlson |
| 60 | #modified (heavily) and optimized by Collin Stocks |
| 61 | bits=int(b) |
| 62 | assert 64<=bits |
| 63 | k=bits<<1 |
| 64 | possible=seed|1 # make it odd |
| 65 | good=0 |
| 66 | while not good: |
| 67 | possible+=2 # keep it odd |
| 68 | good=1 |
| 69 | for i in smallprimes: |
| 70 | if possible%i==0: |
| 71 | good=0 |
| 72 | break |
| 73 | else: |
| 74 | for i in xrange(k): |
| 75 | test=random.randrange(2,possible)|1 |
| 76 | if RabinMillerWitness(test,possible): |
| 77 | good=0 |
| 78 | break |
| 79 | return possible |
| 80 | |
| 81 | def egcd(a,b): |
| 82 | # Extended Euclidean Algorithm |
no test coverage detected