diff options
author | Keith Isdale <keith.isdale@nokia.com> | 2010-07-26 14:56:53 +1000 |
---|---|---|
committer | Keith Isdale <keith.isdale@nokia.com> | 2010-07-26 14:56:53 +1000 |
commit | 9f034793bcfc51c2b7c1dd14db806f7258f9a9eb (patch) | |
tree | 63bd0f50ce5b77828ad8205eafd7b9412810499e /botan/doc/scripts/primes.py | |
parent | 619d92cfef29e653bfdf852e83888e50cfc4348f (diff) | |
parent | 65271649dbc90f3af1184ad1b23bdb64c0c07d07 (diff) |
Merge branch 'master' of git://git-nokia.trolltech.com.au/qtsoftware/research/qtuitest
Diffstat (limited to 'botan/doc/scripts/primes.py')
-rw-r--r-- | botan/doc/scripts/primes.py | 63 |
1 files changed, 63 insertions, 0 deletions
diff --git a/botan/doc/scripts/primes.py b/botan/doc/scripts/primes.py new file mode 100644 index 0000000..cf4d139 --- /dev/null +++ b/botan/doc/scripts/primes.py @@ -0,0 +1,63 @@ +#!/usr/bin/env python + +import sys + +def gcd(x,y): + if x <= 0 or y <= 0: + raise ValueError, "Arguments must be positive integers" + g = y + while x > 0: + g = x + x = y % x + y = g + return g + + +def gen_primes(): + primes = [2,3,5,7,11] + + # Primes < 11351 fit into less than 256x64 bits + for i in xrange(1+primes[-1], 11351+1): + for prime in primes: + if gcd(i, prime) != 1: + break + else: + primes.append(i) + + return primes + +def extract_product(primes): + product = 1 + + used = set() + + for prime in sorted(primes, reverse=True): + if product * prime < 2**64: + product *= prime + used.add(prime) + + primes -= used + + return product + +def main(): + primes = gen_primes() + + primes.sort() + primes.reverse() + + primes = set(primes) + + while len(primes): + print "0x%016X, " % extract_product(primes) + + #product = 1 + #for prime in primes: + # product *= prime + + # if product >= 2**64: + # print "%016X" % (product/prime) + # product = prime + +if __name__ == '__main__': + sys.exit(main()) |