Hi all,
I've been trying to figure out what the chance of finding a P-1 factor
is, given a certain amount of trial factoring and a P-1 bound.
I started with:
The chance of Mp having a factor in [2^n, 2^(n+1)] is 1/n.
The chance of a number N being B-smooth is
(log(B)/log(N))^(log(N)/log(B)) .
Since we know factors of Mp are f = 2kp+1, the difficulty of the problem
of finding f is reduced to factoring k.
So the chance that a factor of Mp can be found by P-1 with bound B is
(log(B)/log(f/2p)) ^ (log(f/2p)/log(B)) .
I get the probabilities of finding any factor by running over factor
sizes in bits (powers of two) and add up the product of the prob of Mp
having a factor of n bits and the prob of P-1 finding such a factor. (In
fact, I make two lists and get the dot product)
Mathematica:
Pfactor[L_] := Table[If[n>L,1/n,0],{n,200}];
// The probabilities of Mp having a factor of n bits, after trial
factoring up to 2^L
Psmooth[B_,p_] := Table[
If [(n-Log[2,2p])<Log[2,B],
1,
(Log[2,B]/(n-Log[2,2p]))^((n-Log[2,2p])/Log[2,B])],
{n,200}];
//The chance of P-1 finding a factor of size n of Mp with stage 1 bound
B
N[Psmooth[1000000,33000000].Pfactor[68]]
0.026342
This would mean that we'd find factors of only 2.6% of the 10 million
exponents, even with a bound of 1M ! Thats pretty disappointing.
Now, is the above about correct ?? I'm pretty unsure about my math, so..
at least N[Psmooth[4000000,300000].Pfactor[53]] ~= 10% which is close to
my empirical data, if a little low ( I get about 11-12% success rate
with B1=100k, B2=4M).
How much error does my quantizing factor sizes to powers of 2 introduce?
And what is the probability of a number being B1-smooth with a single
factor f B1<f<B2 (for P-1 with stage 2) ?
And it just occurred to me: if we know that Mp is composite (because we
did an LL test), after trial factoring the chance for larger factors
must increase, because the interval in which the factor must lie is
narrowed down. How can I take that into account?
Any help would be much appreciated!
Ciao,
Alex.
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
