20040310, 14:46  #1 
Jun 2003
Switzerland
3×5 Posts 
possibility of finding a factor
Hi
This has probably been answered before, but I can't find it ... What is the probability of finding a factor (in trial factoring) for a number around M22'000'000? How is this calculated? thanks Ben 
20040310, 15:34  #2 
Dec 2003
Paisley Park & Neverland
5·37 Posts 
The probability is something like "1  starting bit depth/default bit depth", I guess. Maybe I'm wrong...

20040310, 17:57  #3  
Banned
"Luigi"
Aug 2002
Team Italia
3·1,601 Posts 
Quote:
Luigi 

20040310, 18:22  #4 
Jun 2003
Switzerland
17_{8} Posts 
no, that's not what I meant. My laptop is doublechecking M24842771. What is the possibility that it will find a factor?
on a side note, it checks all numbers from 2 to 2^671, doesn't it? 
20040310, 19:14  #5  
Banned
"Luigi"
Aug 2002
Team Italia
3×1,601 Posts 
Quote:
But the cumulate probability should be SUM(1/n) with n =1,2,3...67 and this can't be true, as it shows a probability higher than 1. Maybe I'm a bit rusty with probabilistic calculus, may anyone shed light on this? : Luigi 

20040310, 19:30  #6 
"Phil"
Sep 2002
Tracktown, U.S.A.
2·13·43 Posts 
To Ben:
Yes, all factors from 2 to 2^67 are checked; however, when you received the exponent, all factors up to some power of 2 had already been checked. So, assuming all factors up to say, 2^63 had already been checked, your chance of finding a factor are roughly 1/63 + 1/64 + 1/65 + 1/66. And to Luigi: Interpret Sum(1/n) as the expected number of factors to find, rather than the probability of finding one factor. If this number is small, the chances of finding more than one factor are small, and this number is then roughly equal to the probability. 
20040310, 20:16  #7  
Sep 2002
296_{16} Posts 
Quote:
It only declares prime or not. If you first have some trial factoring and p1 factoring work for the same exponent those steps could find a factor. 

20040310, 21:49  #8 
Jun 2003
Switzerland
3·5 Posts 
oh, shit, of course I mean trial factoring ... sorry, got confused!
you guys really think the probability is only 1/63 + ... + 1/67? Somehow I can't believe that, because it all adds up to much more than one (from 2 ... 67). surely it should add up to something less than one, otherwise we'll never find a prime :) 
20040310, 22:27  #9  
"William"
May 2003
New Haven
3·787 Posts 
Quote:


20040311, 18:53  #10  
Mar 2004
29 Posts 
Quote:
If by M24842771 you mean 2^248427711 you will get M24842771 = M347 * M71593 * c and M347 is itself not a prime. Mersenne numbers can only be prime if their exponent is also prime. 24842771 is not prime since 24842771=347*71593 If you are interested in factoring M24842771 you can factor M347 by trying factors of the from a*347+1. Probably also M71593 is not prime (I didn't dare to check that on my Smalltalk system *g* since it is a biggy) if it is composite, than all its factors obey the form b*71593+1 (which also M71593 does itself). And you can factor c (if it is composite) all divisors of c obey the form d*24842771+1 Last fiddled with by juergen on 20040311 at 18:55 

20040311, 20:05  #11  
"William"
May 2003
New Haven
3×787 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
how much ECM without finding an existing factor  dbaugh  PrimeNet  4  20130111 16:31 
p1 testing ram vs finding a factor  crash893  Software  11  20060703 21:48 
Probability of finding a factor  JuanTutors  Software  20  20040926 09:47 
Probability of finding a factor in TF  eepiccolo  Math  4  20030607 05:56 
Probability of finding a factor in DC p1  Deamiter  Math  4  20021225 06:06 