20150329, 21:06  #1 
Sep 2011
111001_{2} Posts 
ppyNFS
Hi guys,
I've been asking lots of questions here to understand NFS, and people who answered really helped me understand it. So, I was able to eventually code NFS, it's a really good learning exercise. I've uploaded the code at https://github.com/solidwrench/ppyNFS Thanks, paulo_ 
20150330, 01:58  #2 
Mar 2003
1001110_{2} Posts 
This is a very generous contribution. Thank you!
Don 
20150330, 12:52  #3  
Nov 2003
2^{2}×5×373 Posts 
Quote:
algorithm. However, you will find that the numbers you can factor with your code are quite limited in size. I did not dig into your polynomial root finder. May I ask what method you use? Some suggestions: (1) The most severe constraint for your code is the LA. You will find that Gaussian elimination sharply restricts your factor base size. This, in turn, sharply restricts the numbers you can do. (2) You need to implement a lattice siever. Use the more modern approach of Kleinjung et.al. rather than Pollard's approach. [Note! I wish I could find the time to rewrite my siever.] Note that a linesiever will (with better LA, filter, sqrt code) allow you to perform factorizations up to (say) SNFS C180 or so. (3) I did not look at your filtering/matrix preparation code. If you have not done so, you will need to implement a clique based filter. (4) Couveigne's sqrt algorithm is also rather limiting. It can't handle evendegree fields. Ask if you need help. 

20150331, 10:48  #4  
Sep 2011
3×19 Posts 
Quote:
Quote:
Everything else you've mentioned is a future goal, but I'll need to invest time to study and implement them. Last fiddled with by paul0 on 20150331 at 10:51 

20150402, 00:03  #5 
Tribal Bullet
Oct 2004
3·1,181 Posts 
Nicely done.
The crappy thing about NFS is that in order to scale above small problems (7080 digits) you have to implement all the features Bob lists. You can do line sieving with a single large prime per side, simple graphbased filtering, and keep the Gauss elimination, and that will get you up to 80digit general numbers. But QS can factor numbers that size in a few minutes. 