mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-03-08, 21:52   #1
paul0
 
Sep 2011

2×52 Posts
Default 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.
paul0 is offline   Reply With Quote
Old 2015-03-09, 01:40   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·52·47 Posts
Default

'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.
jasonp is offline   Reply With Quote
Old 2015-03-09, 03:04   #3
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

How was the existing code written? By the same people who created the algorithm?
Dubslow is offline   Reply With Quote
Old 2015-03-09, 13:54   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

5·653 Posts
Default

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.
bsquared is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 05:49.

Wed Jul 15 05:49:40 UTC 2020 up 112 days, 3:22, 0 users, load averages: 1.14, 1.27, 1.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.