Generating reduced basis for special-q

[paul0]

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:

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:

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

[R.D. Silverman]

Originally Posted by paul0

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

[fivemack]

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?

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

[paul0]

Originally Posted by fivemack

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:

(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 :)

Originally Posted by R.D. Silverman

(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]

[Dubslow]

Any reason you're not using Python 3?

[paul0]

Originally Posted by Dubslow

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.

Originally Posted by paul0

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