A week ago, George asked about probability in P-1 factoring. I haven't seen a single response, though I would guess that he has received many private emails. Could this please be included on the list? I am interested in this, as (I'm guessing) many others are. > Extra credit: Can someone tell me the probability that P-1 factoring > will find an n-bit factor? Shouldn't the probability of it finding a n-bit factor be immaterial, as the fact that it finds a factor is all that matters. The whole n-bit concept should only matter if we speak of trial factoring. > This is but one piece of the puzzle in > determining the best trial factoring limits and P-1 bounds. To compute > this probability the k in the 2kp+1 factor must be "smooth", that is > all factors must be less than bound #1 except for one factor that > must be less than bound #2. I'm sure I have the info around here somewhere, > but everyone might be interested in the math behind deriving trial factoring > limits and P-1 bounds. The k must be smooth to B1, yes, but a more rigorous requirement is there also. What if k=2^70? Smooth to any B1, but this number would not be found by P-1 factoring. I'm guessing that numbers that are smooth with high exponents is low, so it should be about the same. Here's what I was able to come up with while doing repetitive jobs at work: A number p^x (p prime) is said to be "enough for" n if p^(x+1) does not divide n. Let f(p,a,b)="the sum from v=a to v=b of 1/p^v" (note for those of you who don't know, f(p,0,b)=(1-(1/p)^n)/(1-1/p)) The probability that p^x is not enough for n is p(p,x,n)=1-f(p,1,x)+f(p,x+1,[log_p(n)]) Thus the probability that value of Q=2^x_1*3^x_2...B1^x_(pi(B1)) will be enough for n, for all p_i<B1 is 1-(prod(p(p_i,x_i,n), i=1, i=B1)) (I think this should be about 1-exp(-gamma)/log(B1)). This should make the probability that P-1 will find a d bit factor ~(1-exp(-gamma)/log(B1))*.81*(1/d-1/(d+1)) -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
