Lattice Sieving - where do I start?

paul0 · 2015-03-08, 21:52

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.

jasonp · 2015-03-09, 01:40

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

Dubslow · 2015-03-09, 03:04

How was the existing code written? By the same people who created the algorithm?

bsquared · 2015-03-09, 13:54

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.

2015-03-08, 21:52	#1
paul0 Sep 2011 111001₂ 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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
I'm getting an error when yafu wants to start lattice sieving	Hailstone	YAFU	30	2018-05-23 19:33
Lattice Sieving Parameters	paul0	Factoring	6	2015-11-20 21:12
Line sieving vs. lattice sieving	JHansen	NFSNET Discussion	9	2010-06-09 19:25
A question on lattice sieving	joral	Factoring	5	2008-04-03 08:01
Initialization for lattice sieving	jasonp	Factoring	16	2006-01-12 22:53

2015-03-09, 01:40	#2
jasonp Tribal Bullet Oct 2004 3541₁₀ 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<A<43 -89<O<-88 3·29·83 Posts	How was the existing code written? By the same people who created the algorithm?

2015-03-09, 13:54	#4
bsquared "Ben" Feb 2007 110110111001₂ 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.