mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-02-22, 17:11   #1
paul0
 
Sep 2011

3×19 Posts
Default NFS success probability in practice

Hello, I figured out a while back the problem with my python implementation. It turns out I wasn't checking that the (a,b) pairs were coprime. Anyway, it works now it and factors numbers up to 30 digits in reasonable time. However, it seems like my implementation factors with a chance of 1/4 per dependency versus 1/2 from literature. Is 1/2 the actual probability in practice?
paul0 is offline   Reply With Quote
Old 2015-02-22, 19:16   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×7×337 Posts
Default

It is 1/2 in practice (if there are exactly two factors).
Maybe your probability is because there were more than two factors? What was your test set - random numbers?
Batalov is offline   Reply With Quote
Old 2015-02-23, 03:55   #3
paul0
 
Sep 2011

1110012 Posts
Default

No, somehow, after computing the sqrt using CRT, the numbers will sometimes fail to be congruent. I will github the code soon.
paul0 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ECM success/failure probability graphs, the interactive online version! WraithX Math 0 2018-01-13 17:41
Another success (not)! ATH Data 133 2012-03-09 17:19
Success again?!? ATH Data 80 2011-11-15 11:40
Success?... (M46 related) lycorn News 631 2010-05-26 10:33
Success edorajh Lounge 5 2004-08-15 16:51

All times are UTC. The time now is 10:38.

Tue May 18 10:38:24 UTC 2021 up 40 days, 5:19, 0 users, load averages: 1.50, 1.79, 1.69

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.