mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)

 paul0 2015-03-29 21:06

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 [URL="https://github.com/solidwrench/ppyNFS"]https://github.com/solidwrench/ppyNFS[/URL]

Thanks,
paulo_

 dleclair 2015-03-30 01:58

This is a very generous contribution. Thank you!

-Don

 R.D. Silverman 2015-03-30 12:52

[QUOTE=paul0;398895]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 [URL="https://github.com/solidwrench/ppyNFS"]https://github.com/solidwrench/ppyNFS[/URL]

Thanks,
paulo_[/QUOTE]

Applause. Kudos. Congratulations. :bow::bow: 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, [b]sharply[/b] 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.

 paul0 2015-03-31 10:48

[QUOTE=R.D. Silverman;398926]I did not dig into your polynomial root finder. May I ask what method you use?[/QUOTE]
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=R.D. Silverman;398926](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.[/QUOTE]
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.

 jasonp 2015-04-02 00:03

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.

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