All,
Here is a potential FAQ of the mersenne mailing list. At the moment
it only deals with factoring, but this should change.
Any suggestions for what should be in the FAQ? Any mistakes? Any
Clarifications?
-Lucas Wiman
Q: How is factoring done on mersenne numbers?
A: We check a potential factor n of Mp by seeing if 2^p (mod n)=1
Q: But doesn't this mean using very large numbers, and computing 2^p?
A: Not at all, there is a very simple algorithm for finding a^b (mod c),
and here's how it works:
we set res=1,
then multiply res by a^(2^n) mod c whenever the nth binary digit of b is 1
a^(2^n) mod c is relativly easy to calculate through repeated sqaring of
a mod c (note that for any o,p, and m, (o^p)==(o mod m)^p (mod m) where ==
is the "congruent to" symbol)
Q: That's still a lot of factors!!!
A: Well we can significantly reduce the number of factors through some
simple theorems which state that:
(1) any factor of 2^p-1 must be of the form 2*k*p+1 for k>0
(2) any factor of 2^p-1 must be of the form 8*n+1 or 8*n-1 for n>0
(3) the smallest factor (other than 1) of any number must be prime
Theorem (1) reduces the number of cases to 1/(2*p) of all numbers.
Theorem (2) reuduces those to 1/2 of those.
Theorem (3) can reduce the factors down to only prime numbers, but that takes
too much time.
It is generally better simply to sieve out potential factors with very small
factors.
Q: But how can you sieve out small factors from potential factors?
A: Well, I think an example would be most illistrative.
Say we want to seive out all potential factors divisable by 3, 5, or 7.
Well we can create an array of 3*5*7=105 elements, with all elements set
to 1 (we'll call this array N). Then elementate all N[i] such that i is
divisable by 3, 5, or 7. Then we can keep a running value of 2*k*p+1 mod 105
then if N[2*k*p+1 mod 105]=0 we skip that factor, and go on to the next one.
Q: How much does all this actually help?
A: The sieving for small factors (up to 17), as well as theorem (2) can can
seive out about 32% of potential factors of the form (2*k*p+1).
Q: Wouldn't it be more effiecient to check prime numbers and see if they
divide as certain 2^p-1?
A: Yes and no. It is theoretically more effiecient to do this, however
this also produces uninteresting (and relativly useless) results for where p
itself is composite.
Q: A prime number cannot divide more than one mersenne number, so why not
create a table of all the prime numbers which divide mersenne numbers so
as not to duplicate work?
A: This isn't really workable because it would take longer to check the
table than it would to just check the factor.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
