mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-03-29, 21:06   #1
paul0
 
Sep 2011

3·19 Posts
Default 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_
paul0 is offline   Reply With Quote
Old 2015-03-30, 01:58   #2
dleclair
 
dleclair's Avatar
 
Mar 2003

7×11 Posts
Default

This is a very generous contribution. Thank you!

-Don
dleclair is offline   Reply With Quote
Old 2015-03-30, 12:52   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by paul0 View Post
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_
Applause. Kudos. Congratulations. It is always pleasing to see someone take the time to dig into a complicated
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 re-write my siever.] Note that a line-siever
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 even-degree fields.

Ask if you need help.
R.D. Silverman is offline   Reply With Quote
Old 2015-03-31, 10:48   #4
paul0
 
Sep 2011

3·19 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I did not dig into your polynomial root finder. May I ask what method you use?
I used the recursive "random splitting" algorithm as described in page 103 of Prime Numbers: A Computational Perspective. See functions getRootsModPFast() and getRootsModPSlow() in poly.py.

Quote:
Originally Posted by R.D. Silverman View Post
(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.
Though not currently uploaded, I have code that does singleton filtering.

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 2015-03-31 at 10:51
paul0 is offline   Reply With Quote
Old 2015-04-02, 00:03   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,181 Posts
Default

Nicely done.

The crappy thing about NFS is that in order to scale above small problems (70-80 digits) you have to implement all the features Bob lists. You can do line sieving with a single large prime per side, simple graph-based filtering, and keep the Gauss elimination, and that will get you up to 80-digit general numbers. But QS can factor numbers that size in a few minutes.
jasonp is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 09:22.


Sat Nov 27 09:22:48 UTC 2021 up 127 days, 3:51, 0 users, load averages: 1.01, 0.96, 1.08

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.