possibility of finding a factor

[there_is_no_spoon]

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

[MrHappy]

The probability is something like "1 - starting bit depth/default bit depth", I guess. Maybe I'm wrong...

[ET_]

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 2^x and 2^x+1 is about 1/x"

Luigi

[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?

[ET_]

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 2⁵⁸ to 2⁵⁹ gives you 1/59 probability of finding a new factor, factoring from 2⁵⁹ to 2⁶⁰ gives you 1/60 probability of finding a new factor and so on, up to 2⁶⁷.

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

[philmoore]

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.

[dsouza123]

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.

[there_is_no_spoon]

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 :)

[wblipp]

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

[juergen]

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

[wblipp]

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.