On 14 May 2001, at 21:56, Nathan Russell wrote:
> otherwise, you might
> have someone using a 486 suddenly realize that their computer was
> doing a first-time check that would take over a year, get frustrated,
> and give up.
A first-time check on a 10M exponent would take _several_ years on a
486!
Actually I think that there may be a perceptual problem with many new
users in that they may give up as soon as they realize that a "most
sense" assignment is going to take several weeks to complete.
Unfortunately there seems to be no easy way to fix this!
>
> >There is also a theoretical difference between those exponents
> >congruent to 1 modulo 4 and those congruent to 3 modulo 4. However I
> >believe that this is due to the fact that one of these groups has a
> >larger probability of having a small factor; thus this irregularity
> >is removed by the time that LL testing begins.
>
> I think I read something similiar. Might it relate to whether the
> first potential factor itself is prime, specifically whether it is
> divisible by 3? I can't do the arithmetic in my head, but I have a
> hunch...
Um. 2p+1 = 3 mod 4 irrespective of whether p = 1 mod 4 or p = 3 mod 4
However for "large" p there doesn't seem to be any link to
divisibility of 2p+1 by 3, or any other "small" prime.
The obvious bias against 3 mod 4 exponents is that those which are
Sophie-Germain primes are guaranteed to be divisible by 2p+1.
We can also examine 2kp+1 mod 8, which must be 1 or 7 if it is a
candidate factor of M(p).
When p = 1 mod 4, p = 1 mod 8 or p = 5 mod 8, so 2p = 2 mod 8,
therefore:
2p+1 = 3 mod 8, so can't be a factor
4p+1 = 5 mod 8, so can't be a factor
6p+1 = 7 mod 8, so might be a factor
8p+1 = 1 mod 8, so might be a factor
...
so the values of k which checking are 3, 4, 7, 8, 11, 12, ...
When p = 3 mod 4, p = 3 mod 8 or p = 7 mod 8, so 2p = 6 mod 8,
therefore
2p+1 = 7 mod 8, so might be a factor
4p+1 = 5 mod 8, so can't be a factor
6p+1 = 3 mod 8, so can't be a factor
8p+1 = 1 mod 8, so might be a factor
...
so the values of k which need checking are 1, 4, 5, 8, 9, 12, ...
The multiples of 4 are common to both series, but the other possible
k values are smaller in the p = 3 mod 4 series than those in the
p = 1 mod 4 series. And, other things being equal, smaller k values
are in general more likely to be provide a factor than larger ones.
However, trial factoring to k >> 10^6 surely reduces the difference
to a miniscule amount.
> Perhaps clicking the 'give me the work that makes the most sense' box
> should immediately set the appearance of the others to the work that
> will be chosen, rather than simply graying them out.
Agreed.
Regards
Brian Beesley
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
