"Matthew Ghio" wrote:
Yes, Phil Karn posted a list of such numbers to the list last May, and the program used to generate them. Since some people have expressed their distaste for large files re-posted/forwarded to the list, I won't send it, but you can get it from ftp cs.cmu.edu: /afs/andrew.cmu.edu/usr12/mg5n/public/Karn.DH.generator
I needed a few of these primes a while ago, so I took a few minutes and hacked Phil's code to operate distributed (ie. a central machine carried out the sieving and handed off candidates to a set of other machines to do the Rabin-Miller). With one Sun Sparc 690MP and approx 40 Sun Sparc LX's, it was getting results like: acacia: 7:21pm up 2:05, 20 users, load average: 0.95, 0.98, 0.77 mg.{~/static/d/dist} date;./go;date Sun Jul 24 19:21:57 EST 1994 [..] server calls: 7235 found modulus p = 72a925f760b2f954ed287f1b0953f3e6aef92e456172f9fe86fdd8822241b9c9788fbc289982743efbcd2ccf062b242d7a567ba8bbb40d79bca7b8e0b6c05f835a5b938d985816bc648985adcff5402aa76756b36c845a840a1d059ce02707e19cf47af0b5a882f32315c19d1b86a56c5389c5e9bee16b65fde7b1a8d74a7675de9b707d4c5a4633c0290c95ff30a605aeb7ae864ff48370f13cf01d49adb9f23d19a439f753ee7703cf342d87f431105c843c78ca4df639931f3458fae8a94d1687e99a76ed99d0ba87189f42fd31ad8262c54a8cf5914ae6c28c540d714a5f6087a171fb74f4814c6f968d72386ef356a05180c3bec7ddd5ef6fe76bfd8717 finding generator trying 2 3 5 generator g = 5 Sun Jul 24 21:10:18 EST 1994 That's 2 hours for a 2048 prime P where (P - 1)/2 is also prime, and they also satisfied the constraint that P = 3(mod 4). The software maintains a TCP connection to each "Rabin-Miller server" and can dynamically deal with the loss of machines, but in it's simplicity doesn't do reconnects. If anyone who operates an FTP archive wants to reply to me, I'll tar it up (in it's current "it works for me, but no guarantees" state). Speaking of primes with constraints, I got my hands on Harn's recent paper on a PKCS based on both factoring and discrete logs. He wants his modulus to be a prime P = 2p x q + 1, where p = 2r + 1, q = 2s + 1. All P, q, q, r, s must be prime -- good luck in finding such primes by probablistic methods ! Matthew. mg.{~/src/rr} ls -l total 26 -rw------- 1 mgream 8339 Jul 24 14:17 client.c -rw------- 1 mgream 2196 Jul 24 15:00 common.h -rw------- 1 mgream 6028 Jul 29 13:35 dhgen.c -rwx------ 1 mgream 270 Jul 24 14:58 go -rw------- 1 mgream 527 Jul 24 14:58 makefile -rw------- 1 mgream 3041 Jul 29 14:50 server.c -rw------- 1 mgream 367 Jul 24 14:26 servers.src -- Matthew Gream <M.Gream@uts.edu.au> -- Consent Technologies, (02) 821-2043 Disclaimer: From? \notin speaking_for(Organization?) [cfqx103]