mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-10-21, 14:49   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default QS Lattice Siever

Has anyone ever looked at writting a QS lattice siever?

QS normally implements a line sieve in the (b,a) plane. It processes
-M < a < M one b at a time.

But there is n reason why it couldn't do what NFS does. Sieve
over -M < a < M for (say) B1 < b < B2 all at once. The sieve area
would be (2M x (B2-B1). We would sieve only those points
such that q(x), the value of the quadratic polynomial was divisible
by a chosen special_q. After sieving B1 < b < B2, we then move
to B2 < B < B3, etc.

You would solve q(x) = 0 mod special_q (generally there would be
two roots r1, r2). You then construct a reduced basis for (q, r1)
and one for (q, r2), than lattice sieve over the region as NFS does.
You would sieve twice; once for each root.

If I can find the time (I am very busy with real work and improving
my NFS siever) I may even write a paper on the technique.

Meanwhile, I toss out the idea as food for thought for anyone who
might want to tackle this. (Perhaps a joint paper??)

Bob
R.D. Silverman is offline   Reply With Quote
Old 2010-10-21, 15:08   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·32·191 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Has anyone ever looked at writting a QS lattice siever?

QS normally implements a line sieve in the (b,a) plane. It processes
-M < a < M one b at a time.

But there is n reason why it couldn't do what NFS does. Sieve
over -M < a < M for (say) B1 < b < B2 all at once. The sieve area
would be (2M x (B2-B1). We would sieve only those points
such that q(x), the value of the quadratic polynomial was divisible
by a chosen special_q. After sieving B1 < b < B2, we then move
to B2 < B < B3, etc.

You would solve q(x) = 0 mod special_q (generally there would be
two roots r1, r2). You then construct a reduced basis for (q, r1)
and one for (q, r2), than lattice sieve over the region as NFS does.
You would sieve twice; once for each root.

If I can find the time (I am very busy with real work and improving
my NFS siever) I may even write a paper on the technique.

Meanwhile, I toss out the idea as food for thought for anyone who
might want to tackle this. (Perhaps a joint paper??)

Bob
msieve processes multiple b's at a time, by storing the info necessary to change the roots of each prime from b to b as it sieves. But if I understand correctly, this is different from what you're talking about here; it is more of a sieving optimization. There is no reduced basis or special_q in msieve, that I know of.

I'm willing to spend time writing code to try it out, but I would need some more info/coaching on several things - how to do the basis reduction, for instance. I'm also pretty busy, so I may not be the best candidate if you want to write something short term.
bsquared is offline   Reply With Quote
Old 2010-10-21, 15:27   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by bsquared View Post
msieve processes multiple b's at a time, by storing the info necessary to change the roots of each prime from b to b as it sieves. But if I understand correctly, this is different from what you're talking about here; it is more of a sieving optimization. There is no reduced basis or special_q in msieve, that I know of.

I'm willing to spend time writing code to try it out, but I would need some more info/coaching on several things - how to do the basis reduction, for instance. I'm also pretty busy, so I may not be the best candidate if you want to write something short term.
I would first need to write a paper on the algorithm. What I am discussing
is totally different from what you do. The technique I propose here would
sieve over lattice points where the norm of q(x) is a priori divisible by
the special_q, making it much more likely to be smooth with respect to
the factor base. It could easily add 20 to 30 digits in the same amount
of time.
R.D. Silverman is offline   Reply With Quote
Old 2010-10-21, 16:06   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Has anyone ever looked at writting a QS lattice siever?

QS normally implements a line sieve in the (b,a) plane. It processes
-M < a < M one b at a time.

But there is n reason why it couldn't do what NFS does. Sieve
over -M < a < M for (say) B1 < b < B2 all at once. The sieve area
would be (2M x (B2-B1). We would sieve only those points
such that q(x), the value of the quadratic polynomial was divisible
by a chosen special_q. After sieving B1 < b < B2, we then move
to B2 < B < B3, etc.

You would solve q(x) = 0 mod special_q (generally there would be
two roots r1, r2). You then construct a reduced basis for (q, r1)
and one for (q, r2), than lattice sieve over the region as NFS does.
You would sieve twice; once for each root.

If I can find the time (I am very busy with real work and improving
my NFS siever) I may even write a paper on the technique.

Meanwhile, I toss out the idea as food for thought for anyone who
might want to tackle this. (Perhaps a joint paper??)

Bob
Note that we would need to make q(x) bivariate.....
R.D. Silverman is offline   Reply With Quote
Old 2010-10-21, 16:16   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1101011011102 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I would first need to write a paper on the algorithm. What I am discussing
is totally different from what you do.
I know, and I'm really excited about that! I'm tired of trying to eek out 1-2% improvements in my siqs code, so this is a great chance for me to try out something new that isn't (hopefully) as much of a stretch as implementing a NFS siever would be.

I'm willing to write code when it gets to that point or to test out ideas as they occur to you (if you want help with that sort of thing).
bsquared is offline   Reply With Quote
Old 2010-10-21, 16:24   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by bsquared View Post
I know, and I'm really excited about that! I'm tired of trying to eek out 1-2% improvements in my siqs code, so this is a great chance for me to try out something new that isn't (hopefully) as much of a stretch as implementing a NFS siever would be.
It would be close. The only real difference would be in not having
to deal with two different factor bases, and not having to deal with
algebraic number theory, (esp.) in the square root phase.

They would have many common elements.
R.D. Silverman is offline   Reply With Quote
Old 2010-10-21, 17:10   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·32·191 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
It would be close. The only real difference would be in not having
to deal with two different factor bases, and not having to deal with
algebraic number theory, (esp.) in the square root phase.

They would have many common elements.
I'm aware that there will be a learning curve, but it sound like it won't be as steep as the one to an NFS lattice siever would be. This sound to me like a good half way point, and I'm excited about the possibilities.
bsquared is offline   Reply With Quote
Old 2010-10-21, 17:52   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by bsquared View Post
I'm aware that there will be a learning curve, but it sound like it won't be as steep as the one to an NFS lattice siever would be. This sound to me like a good half way point, and I'm excited about the possibilities.
Here is a sketch.

Construct a polynomial q(x,y) = Ax^2 + 2Bxy + Cy^2 whose discriminant
is a multiple of N. Set x = 1 (say) and solve q(x,y) = 0 mod q.
There will be two roots, r1, r2. Find reduced lattices for [q r1][0 1]
and [q r2][0 1]. This yields two sets of vectors V1, V2, and W1, W2.

Now lattice sieve as in NFS.

This will give a whole slew of points (e,f) such that (x,y) = eV1 + f V2
will have q(x,y) divisible by q. We now hope that q(x,y)/q is smooth
with respect to the factor base. Repeat for the W1, W2 vectors.
Now try a new special q. REPEAT.
R.D. Silverman is offline   Reply With Quote
Old 2010-10-21, 19:18   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×29×61 Posts
Default

I think there might be some related ideas in this paper, in that one can sieve over a degree 4 polynomial whose coefficients might be small, depending on the exact form of N, and lattice sieving can be used here too. If memory serves the coefficients would have to be extremely small to be competitive with ordinary QS.

While we're doing blue-sky about QS, Colin Percival wrote in his blog about an idea to turn MPQS with an extremely small sieve interval into a subset-sum problem. The idea is that if the large primes in the factor base are much larger than the sieve interval, most will hit once or twice across tens of thousands of different b values. I actually implemented his idea in an experimental msieve version, and it can complete the same amount of sieving in half the time, but it requires massive amounts of memory and the relation rate drops by 4x compared to the parametrization in the production QS code.
jasonp is offline   Reply With Quote
Old 2010-10-21, 20:55   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by jasonp View Post
I think there might be some related ideas in this paper, in that one can sieve over a degree 4 polynomial whose coefficients might be small, depending on the exact form of N, and lattice sieving can be used here too. If memory serves the coefficients would have to be extremely small to be competitive with ordinary QS.

While we're doing blue-sky about QS, Colin Percival wrote in his blog about an idea to turn MPQS with an extremely small sieve interval into a subset-sum problem. The idea is that if the large primes in the factor base are much larger than the sieve interval, most will hit once or twice across tens of thousands of different b values. I actually implemented his idea in an experimental msieve version, and it can complete the same amount of sieving in half the time, but it requires massive amounts of memory and the relation rate drops by 4x compared to the parametrization in the production QS code.
I know about the Zhang result. It's applicability is somewhat limited and
AFAIK, noone has ever implemented it.
R.D. Silverman is offline   Reply With Quote
Old 2010-10-22, 00:15   #11
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DD216 Posts
Default

I agree that Zhang's method per se won't help much here, but the paper goes through the process of converting the input number into a homogeneous polynomial which can be sieved over a lattice just like we know how to do. I only bring it up because their analysis of the size of the norms involved implies that you'd be better off using QS for almost any input. So what chance do we have splitting N into fewer than three pieces?
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Compiling 64 bit lattice siever on gcc 4.8.5 chris2be8 Factoring 6 2018-02-06 17:22
OpenCL accellerated lattice siever pstach Factoring 1 2014-05-23 01:03
Shape of a CUDA lattice siever fivemack Programming 2 2012-12-16 01:07
Msieve / lattice siever with degree 7/8 poly Batalov Msieve 54 2010-01-13 19:45
ggnfs lattice siever misses some primes fivemack Factoring 1 2008-01-18 13:47

All times are UTC. The time now is 23:54.

Tue May 18 23:54:00 UTC 2021 up 40 days, 18:34, 0 users, load averages: 0.87, 1.35, 1.43

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.