mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-11-17, 13:39   #1
paul0
 
Sep 2011

3×19 Posts
Default Generating reduced basis for special-q

Hello,

I have code that tries to generate lattice points of a special-q: https://github.com/paulocode/ppyNFS/...alq-lattice.py

However, norms of points it generates through the reduced basis are not divisible by q. I've checked that the reduction is correct through Pari. This is the output:
Code:
r is a root of f() mod q
basis: [[-110, 1], [249, 1]]
reduced basis: [[1, -180L], [1, 179L]]
generating lattice points...
[-4, 2L] is not q-divisible
[-3, 181L] is not q-divisible
[-2, 360L] is not q-divisible
[-1, 539L] is not q-divisible
[-3, -178L] is not q-divisible
[-2, 1L] is not q-divisible
[-1, 180L] is not q-divisible
[-2, -358L] is not q-divisible
[-1, -179L] is not q-divisible
[1, 179L] is not q-divisible
[-1, -538L] is not q-divisible
[1, -180L] is not q-divisible
[2, -1L] is not q-divisible
Also, an unreduced basis generates q divisible points. If you uncomment line 21 so the basis is not reduced, you'll get this output:
Code:
r is a root of f() mod q
basis: [[-110, 1], [249, 1]]
reduced basis: [[-110, 1], [249, 1]]
generating lattice points...
[-278, -4] is q-divisible
[-29, -3] is q-divisible
[220, -2] is q-divisible
[469, -1] is q-divisible
[-388, -3] is q-divisible
[-139, -2] is q-divisible
[110, -1] is q-divisible
[-498, -2] is q-divisible
[-249, -1] is q-divisible
[249, 1] is q-divisible
[-608, -1] is q-divisible
[-110, 1] is q-divisible
[139, 2] is q-divisible
So for some reason, my code's unreduced basis generates points divisible by q, not but not when the basis is reduced. I may have misunderstood something. Can anyone try to point it out? The code is not that complicated, and I used the notation from the paper of Franke and Kleinjung.

Thanks

Last fiddled with by paul0 on 2015-11-17 at 14:01
paul0 is offline   Reply With Quote
Old 2015-11-17, 14:19   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by paul0 View Post
Hello,

I have code that tries to generate lattice points of a special-q: https://github.com/paulocode/ppyNFS/...alq-lattice.py

However, norms of points it generates through the reduced basis are not divisible by q. I've checked that the reduction is correct through Pari. This is the output:
[CODE]r is a root of f() mod q
basis: [[-110, 1], [249, 1]]
reduced basis: [[1, -180L], [1, 179L]]



(0) You should set your initial basis to have determinant equal to q, not -q. [-359 in your case]

(1) What is the "L"? Is it a language syntax artifact?

(2) You do not have a reduced basis. I get [29 3] [23 -10]. (or [6 13] [23 -10])

How did you get [1,-180][1,179]? Its determinant is +359.
You changed signs during your basis reduction......

Last fiddled with by R.D. Silverman on 2015-11-17 at 14:19
R.D. Silverman is offline   Reply With Quote
Old 2015-11-17, 14:27   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

638310 Posts
Default

I'm a bit unsure of your signs here; I think [110,1],[-249,1] might be a better basis for the lattice of (x,y) with x^3 + 15x^2y + 29xy^2 + 8y^3 == 0 mod 359

Might you be confusing the matrix-which-reduces-the-basis (which is what qflll() in Pari outputs) with the reduced basis?

Code:
? M=matrix(2,2)
%1 = 
[0 0]
[0 0]
? M[1,1]=110
%2 = 110
? M[2,1]=1
%3 = 1
? M[2,2]=1
%4 = 1
? M[1,2]=-249
%5 = -249
? M
%6 = 
[110 -249]
[1 1]

? redmat=qflll(M)
%7 = 
[9 -7]
[4 -3]

? M*redmat
[-6 -23]
[13 -10]
and indeed [-6,13] and [-23,-10] appear to have f(x,y)%359==0.
fivemack is offline   Reply With Quote
Old 2015-11-17, 14:47   #4
paul0
 
Sep 2011

3·19 Posts
Default

Quote:
Originally Posted by fivemack View Post
Might you be confusing the matrix-which-reduces-the-basis (which is what qflll() in Pari outputs) with the reduced basis?
It appears that I was confusing the rows & columns of the matrix, I was running it like this in Pari:

Code:
(22:53) gp > x = [-110, 1;249, 1]
%15 =
[-110 1]
[ 249 1]

(22:53) gp > x=x*qflll(x)
%16 =
[1 -180]
[1  179]
which explains why I thought it was right. The current commit works now :)

Quote:
Originally Posted by R.D. Silverman View Post
(1) What is the "L"? Is it a language syntax artifact?
Yes, it's more of an artifact in python. L is appended when the number is represented as a bignum. It gets printed out when the number is not printed directly, e.g. though an array: print [a,b]

Last fiddled with by paul0 on 2015-11-17 at 15:03
paul0 is offline   Reply With Quote
Old 2015-11-17, 22:52   #5
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Any reason you're not using Python 3?
Dubslow is offline   Reply With Quote
Old 2015-11-18, 06:16   #6
paul0
 
Sep 2011

1110012 Posts
Default

Quote:
Originally Posted by Dubslow View Post
Any reason you're not using Python 3?
No particular reason, python 2 is what I currently have installed. I'll switch to python 3 soon.

Quote:
Originally Posted by paul0 View Post
I have code that tries to generate lattice points of a special-q: https://github.com/paulocode/ppyNFS/...alq-lattice.py
if anyone's looking, I renamed the file: https://github.com/paulocode/ppyNFS/...st-specialq.py

Last fiddled with by paul0 on 2015-11-18 at 06:24
paul0 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
What would increased and reduced gravity do to a person's abilities? jasong Science & Technology 15 2016-01-21 17:13
Generating Low-Weight Ks henryzz Riesel Prime Search 9 2012-04-09 21:36
On the basis of finite fields meng_luckywolf Math 6 2007-12-13 04:21
Generating 2005 Wacky Puzzles 46 2005-06-05 22:19
Prime-generating polynomials Orgasmic Troll Math 28 2004-12-02 16:37

All times are UTC. The time now is 17:46.

Wed Apr 21 17:46:24 UTC 2021 up 13 days, 12:27, 0 users, load averages: 3.09, 2.86, 2.58

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.