Here's something interesting, it *might* allow us to almost eliminate the
x squarings in p-1 factoring.
P-1 factoring is based upon Fermat's little theorem which states that
with gcd(a,p)=1, p prime, a^(p-1)==1 mod p. Now, say we are factoring
the number n, and p|n. We assume that (p-1)|q (hence q needs to have small
factors), therefore a^q==1 mod p. Then we find (a^q-1) mod n, and then find
gcd((a^q-1) mod n,n). If it is not equal to 0,1, or n then you have found a
non-trivial factor (note, a result of zero would occur when (m-1)|q, and m
was a base a Fermat prob. prime).
(Now none of the variables in the previous paragraph carry over into the
next :)
What if we use 2 as a base? Well, for mersenne numbers, this might be to
our advantage. Note that 2^n==1 mod Mn, hence 2^q==2^(q mod n) mod Mn.
This would bring us down to (at most) log_2(n) squarings, which is
insignificant.
The possible problem (other than the required gcd) is this:
Take 2^(a#)-1 has the factor (the product from 1 to a, p prime, of 2^p-1)
Where # is the primorial function. Now, as I understand it, each prime
number is "assigned" to a certain Mersenne, and this may or may not
cause problems, I don't know. (Note that even after the removal of
the trivial factors, there is still a very large number remaining).
This would allow us to have huge, and I mean fricking huge B1 values,
for no extra cost. Maybe even as high as 2^32. Using a linear approximation
of my pseudo-primorial function in my previous posting, I get this number
would have around 6.18*10^9 bits (627 megabytes), though it could be
calculated indirectly (1.9*10^8 multiplications mod n).
If this pans out, then P-1 would have decided advantages over trial
factoring (past a certain point), even at lower exponent ranges.
-Lucas
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
