Let me get this right about p-1 testing please. On the Mersenne site it says
The P-1 method is quite simple. In stage 1 we pick a bound B1. P-1 factoring will find the factor q as long as all factors of k are less than B1 (k is called B1-smooth). We compute E - the product of all primes less than B1. Then we compute x = 3E*2*P. Finally, we check the GCD (x-1, 2P-1) to see if a factor was found.
Now, my exponent was 34642837, and the factor found for M34642837 was 3744250227067525727981257. This turns out to be
2 * 34642837 * 54040756348383444 + 1
ie considering Fermat's result that any factors of 2^p - 1 are of the form 2kp+1, we have k = 54040756348383444. Using Dario Alpern's program (accessible through the Prime Pages) this factorises as
2^2 * 3^5 * 23 * 3677 * 9001 * 73037
I don't remember offhand which B1 was used, but for k to be B1 smooth, it would need to be at least 73038. E would then be
2 * 3 * .... * 73037 - or 73037#
Looking at some of the largest primorial primes, I see that 42209# has 18241 digits - so I guess 73037# has over 30000 digits. And then we are multiplying 3 by itself this number of times! IS this the case?
Thanks
| Douglas CHESTER MPhil
Computer Science Dendrite Compass Team |
| Lilly UK Lilly House, Priestley Road Basingstoke, Hampshire, RG24 9NL UNITED KINGDOM Tel: +44 (0)1256 775091 Fax: +44 1256 315858 Mob: +44 (0)7977 138637 www.lilly.co.uk |  |
"CONFIDENTIALITY NOTICE: This e-mail message from Lilly UK (including all attachments) is for the sole use of the intended recipient(s) and may contain confidential and privileged information. Any unauthorized review, use, disclosure, copying or distribution is strictly prohibited. If you are not the intended recipient, please contact the sender by reply e-mail and destroy all copies of the original message. E-mail is susceptible to data corruption, interception, unauthorized amendment, tampering and viruses, and we only send and receive e-mails on the basis that we are not liable for any such corruption, interception, amendment, tampering or viruses or any consequences thereof." |
_______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
