Generating reduced basis for specialq
Hello,
I have code that tries to generate lattice points of a specialq: [url]https://github.com/paulocode/ppyNFS/blob/master/specialqlattice.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 qdivisible [3, 181L] is not qdivisible [2, 360L] is not qdivisible [1, 539L] is not qdivisible [3, 178L] is not qdivisible [2, 1L] is not qdivisible [1, 180L] is not qdivisible [2, 358L] is not qdivisible [1, 179L] is not qdivisible [1, 179L] is not qdivisible [1, 538L] is not qdivisible [1, 180L] is not qdivisible [2, 1L] is not qdivisible[/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 qdivisible [29, 3] is qdivisible [220, 2] is qdivisible [469, 1] is qdivisible [388, 3] is qdivisible [139, 2] is qdivisible [110, 1] is qdivisible [498, 2] is qdivisible [249, 1] is qdivisible [249, 1] is qdivisible [608, 1] is qdivisible [110, 1] is qdivisible [139, 2] is qdivisible [/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 
[QUOTE=paul0;416407]Hello,
I have code that tries to generate lattice points of a specialq: [url]https://github.com/paulocode/ppyNFS/blob/master/specialqlattice.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...... 
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 matrixwhichreducesthebasis (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. 
[QUOTE=fivemack;416410]
Might you be confusing the matrixwhichreducesthebasis (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] 
Any reason you're not using Python 3?

[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 specialq: [url]https://github.com/paulocode/ppyNFS/blob/master/specialqlattice.py[/url][/QUOTE] if anyone's looking, I renamed the file: [url]https://github.com/paulocode/ppyNFS/blob/master/testspecialq.py[/url] 
All times are UTC. The time now is 07:30. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.