Mersenne: P-1, N-1 tests
Hi! Recently, I've been playing with some number theoretical problems (just for fun). I've met two similar approches mentioned in the subject: a) P-1 method of factorization and b) N-1 primality test. It seems (if I understand well) that a) we assume that a prime factor p of a given (composite) number n is such that p-1 is smooth; then we can try to determine p itself; b) we _know_ factorization of n-1 and there are some primality tests (see, e.g., Chris Caldwell pages) for n My question is: Is there any method/algorithm to determine _factors_ of n if the factorization of n-1 is known? I understand that there is no _exact_ formula for factors, but maybe there are some strong conditions, which restrict factors to a specific form (like k2^r+1 for Fermat numbers) The second question I should send directly to Chris Caldwell. In his Prime Pages the N-1 test of primality needs such a that a^(N-1)=1 mod N and a^(N-1)/q is not 1 mod N (q is a factor of N-1). Methods for determining the number a are not presented. Are there any such methods? Regards Wojciech Florek (WsF) Adam Mickiewicz University, Institute of Physics ul. Umultowska 85, 61-614 Poznan, Poland phone: (++48-61) 8295033 fax: (++48-61) 8295167 email: [EMAIL PROTECTED] _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: M#40 - what went wrong?
At 07:52 PM 6/15/2003 -0700, Luke Welsh wrote: I'm fishing What about +/- INF ? Yes, they would be treated just like a NaN. Prime95 checks if the sum of the FFT inputs is NaN, or +/- INF every iteration (generating the common ILLEGAL SUMOUT error). What about corruption of any of the pre-computed arrays? Yes, if the first weight value was NaN, then that would corrupt the entire FFT data array. Of course, this generates an ILLEGAL SUMOUT on the next iteration, but if this single corruption happened during the last iteration then a false positive would have been generated. Version 23.5 will now detect this. I'm also adding code to 23.5 to check EVERY iteration for an impossible result such as -2, -1, 0, 1, 2. This test will be very, very quick. FYI, six times a result of 0002 has been reported to the server. So, somehow or another it is possible for a hardware error to zero the FFT data without triggering an ILLEGAL SUMOUT. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: M#40 - what went wrong?
I'm also adding code to 23.5 to check EVERY iteration for an impossible result such as -2, -1, 0, 1, 2. This test will be very, very quick. But no matter how quick this additional test will be, it will slow down all machines globally, while a false positive report would only slow down two machines to double check for a limited time!!! If we consider a double check will take 15 days on an average machine, and 15 days (in the same time) on another machine, this makes 30 days x 24 x 3,600 = 2,592,000 seconds. While if we consider that this additional test takes only 3 minutes per exponent overall in average, there are over 40,000 machines working in the project, I don't know the exact number but if we consider half that number work on LL tests, 20,000 x 180 = 3,600,000 seconds. (There's a lot more machines assigned LL tests!) So this makes a difference of 1,008,000 seconds and this of course just in the case a false positive was reported!!! So I think the additional test is not needed, it would only slow down the project... _ Help STOP SPAM with the new MSN 8 and get 2 months FREE* http://join.msn.com/?page=features/junkmail _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
