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

- - **ppyNFS**
(*https://www.mersenneforum.org/showthread.php?t=20147*)

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

This is a very generous contribution. Thank you!
-Don |

[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. Ask if you need help. |

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

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

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.