If you are trying to factor Mp = 2^p - 1 where p is prime and
p > 2^58, then Mp can have no 59-bit factors
[All factors are == 1 (mod 2*p).]
But when factoring a random integer n, we estimate the probability
of a factor between 2^51 and 2^59 as
1 - product (1 - 1/q)
2^51 < q < 2^59
q prime
That is, we model this with a separate event for each
potential prime divisor. You can approximate this
probability by first approximating the logarithm of the product
by an integral. The probability does not depend on n.
If we want to restrict the product to primes q == 1 (mod p),
as when factoring Mp, then (1 - 1/q) becomes (1 - p/(q-1)),
the probability that 2 is a ((q-1)/p)-th residue mod q
This is approximately (1 - 1/q)^p.
There are only 1/(p-1) times as many potential choices for q,
but each such q has approximately p times as much impact.
To a first approximation, the success probability remains
stable (i.e., reaches a limit other than 0 or 1)
as the exponent increases.
Peter Montgomery
------------
Question:
>From a number theoretic point of view, does the
likelihood of small (52 through 59 bits) factors increase
with exponent size?
Regards,
Stefanovic
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
