mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-03-10, 14:46   #1
there_is_no_spoon
 
Jun 2003
Switzerland

3×5 Posts
Default 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
there_is_no_spoon is offline   Reply With Quote
Old 2004-03-10, 15:34   #2
MrHappy
 
MrHappy's Avatar
 
Dec 2003
Paisley Park & Neverland

5·37 Posts
Default

The probability is something like "1 - starting bit depth/default bit depth", I guess. Maybe I'm wrong...
MrHappy is offline   Reply With Quote
Old 2004-03-10, 17:57   #3
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

3·1,601 Posts
Default

Quote:
Originally Posted by MrHappy
The probability is something like "1 - starting bit depth/default bit depth", I guess. Maybe I'm wrong...
If I read (and translate) well "the chance of finding a factor between 2x and 2x+1 is about 1/x"

Luigi
ET_ is online now   Reply With Quote
Old 2004-03-10, 18:22   #4
there_is_no_spoon
 
Jun 2003
Switzerland

178 Posts
Default

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^67-1, doesn't it?
there_is_no_spoon is offline   Reply With Quote
Old 2004-03-10, 19:14   #5
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

3×1,601 Posts
Default

Quote:
Originally Posted by there_is_no_spoon
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^67-1, doesn't it?
Let'say that factoring proceeds in stages of one byte... Factoring from 258 to 259 gives you 1/59 probability of finding a new factor, factoring from 259 to 260 gives you 1/60 probability of finding a new factor and so on, up to 267.

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
ET_ is online now   Reply With Quote
Old 2004-03-10, 19:30   #6
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

2·13·43 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2004-03-10, 20:16   #7
dsouza123
 
dsouza123's Avatar
 
Sep 2002

29616 Posts
Default

Quote:
My laptop is doublechecking M24842771.
What is the possibility that it will find a factor?
None, because doublechecking doesn't find factors.
It only declares prime or not.

If you first have some trial factoring and p-1 factoring work for the same exponent
those steps could find a factor.
dsouza123 is offline   Reply With Quote
Old 2004-03-10, 21:49   #8
there_is_no_spoon
 
Jun 2003
Switzerland

3·5 Posts
Default

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 :)
there_is_no_spoon is offline   Reply With Quote
Old 2004-03-10, 22:27   #9
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3·787 Posts
Default

Quote:
Originally Posted by there_is_no_spoon
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 :)
Adding up the numbers gives you the expected number of factors, which should, eventually, be more than one. What you meed is the probability of NO Factors, which is 62/63 x 63/64 ... x 66/67 = 62/67. So the probability of finding a factor is 1 - 62/67 = 5/67
wblipp is offline   Reply With Quote
Old 2004-03-11, 18:53   #10
juergen
 
Mar 2004

29 Posts
Default

Quote:
Originally Posted by there_is_no_spoon
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^67-1, doesn't it?
Oh I guess you will find not only two factors if your program works fine:

If by M24842771 you mean

2^24842771-1

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 2004-03-11 at 18:55
juergen is offline   Reply With Quote
Old 2004-03-11, 20:05   #11
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3×787 Posts
Default

Quote:
Originally Posted by juergen
Probably also M71593 is not prime
Will Edgington's lowM.txt shows that 2061145545795336268297 is a factor of M71593, but I would guess there was a trascription error, and his exponent is really prime.
wblipp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
how much ECM without finding an existing factor dbaugh PrimeNet 4 2013-01-11 16:31
p-1 testing ram vs finding a factor crash893 Software 11 2006-07-03 21:48
Probability of finding a factor JuanTutors Software 20 2004-09-26 09:47
Probability of finding a factor in TF eepiccolo Math 4 2003-06-07 05:56
Probability of finding a factor in DC p-1 Deamiter Math 4 2002-12-25 06:06

All times are UTC. The time now is 12:48.

Sun Mar 7 12:48:56 UTC 2021 up 94 days, 9 hrs, 0 users, load averages: 2.05, 1.88, 1.66

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.