mersenneforum.org Lattice Sieving - where do I start?
 Register FAQ Search Today's Posts Mark Forums Read

 2015-03-08, 21:52 #1 paul0   Sep 2011 1110012 Posts Lattice Sieving - where do I start? My python NFS implementation is now up and working, and mostly cleaned. I currently use line sieving, now I want to take it up a notch with lattice sieving. But where do I start? Is there an explicit example (like Briggs') I can work with? The papers about lattice sieving are not accessible to me as I do not have a good understanding of lattices. There seems to be two definitions of lattices in wikipedia: http://en.wikipedia.org/wiki/Lattice_(group) and http://en.wikipedia.org/wiki/Lattice_(order). Which one is applicable? Also, please recommend books regarding lattices relevant to NFS. I've gotten this far, lattices should be doable, eventually.
 2015-03-09, 01:40 #2 jasonp Tribal Bullet     Oct 2004 5·709 Posts 'The Development of the Number Field Sieve' contains a paper that gives a few details of lattice sieving, but it's not enough to implement the algorithm. I think you're going to have to look at existing code to get all the details you need.
 2015-03-09, 03:04 #3 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2015-03-09, 13:54 #4 bsquared     "Ben" Feb 2007 7·11·47 Posts There is the paper by Franke and Kleinjung: "Continued Fractions and Lattice Sieving". Probably also not enough detail to complete an implementation but it is the best (only?) reference out there for their algorithm that I know of, aside from their code.

 Similar Threads Thread Thread Starter Forum Replies Last Post Hailstone YAFU 30 2018-05-23 19:33 paul0 Factoring 6 2015-11-20 21:12 JHansen NFSNET Discussion 9 2010-06-09 19:25 joral Factoring 5 2008-04-03 08:01 jasonp Factoring 16 2006-01-12 22:53

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

Sat Jul 2 13:51:30 UTC 2022 up 79 days, 11:52, 1 user, load averages: 1.31, 1.13, 1.15