mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Generating reduced basis for special-q (https://www.mersenneforum.org/showthread.php?t=20671)

 paul0 2015-11-17 13:39

Generating reduced basis for special-q

Hello,

I have code that tries to generate lattice points of a special-q: [url]https://github.com/paulocode/ppyNFS/blob/master/specialq-lattice.py[/url]

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[/CODE]

Also, an unreduced basis generates q divisible points. If you uncomment line 21 so the basis is [B]not[/B] 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
[/CODE]

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 2015-11-17 14:19

[QUOTE=paul0;416407]Hello,

I have code that tries to generate lattice points of a special-q: [url]https://github.com/paulocode/ppyNFS/blob/master/specialq-lattice.py[/url]

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]]
[/QUOTE]

(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 2015-11-17 14:27

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]
[/code]

and indeed [-6,13] and [-23,-10] appear to have f(x,y)%359==0.

 paul0 2015-11-17 14:47

[QUOTE=fivemack;416410]
Might you be confusing the matrix-which-reduces-the-basis (which is what qflll() in Pari outputs) with the reduced basis?
[/QUOTE]

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]
[/CODE]

which explains why I thought it was right. The current commit works now :)

[QUOTE=R.D. Silverman;416409](1) What is the "L"? Is it a language syntax artifact?[/QUOTE]
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 2015-11-17 22:52

Any reason you're not using Python 3?

 paul0 2015-11-18 06:16

[QUOTE=Dubslow;416459]Any reason you're not using Python 3?[/QUOTE]

No particular reason, python 2 is what I currently have installed. I'll switch to python 3 soon.

[QUOTE=paul0;416407]I have code that tries to generate lattice points of a special-q: [url]https://github.com/paulocode/ppyNFS/blob/master/specialq-lattice.py[/url][/QUOTE]

if anyone's looking, I renamed the file: [url]https://github.com/paulocode/ppyNFS/blob/master/test-specialq.py[/url]

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