Thread: ppyNFS
View Single Post
Old 2015-03-30, 12:52   #3
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

11101001001002 Posts

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

Applause. Kudos. Congratulations. It is always pleasing to see someone take the time to dig into a complicated

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