20151117, 13:39  #1 
Sep 2011
3×19 Posts 
Generating reduced basis for specialq
Hello,
I have code that tries to generate lattice points of a specialq: https://github.com/paulocode/ppyNFS/...alqlattice.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 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:
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 Thanks Last fiddled with by paul0 on 20151117 at 14:01 
20151117, 14:19  #2  
Nov 2003
2^{2}·5·373 Posts 
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...... Last fiddled with by R.D. Silverman on 20151117 at 14:19 

20151117, 14:27  #3 
(loop (#_fork))
Feb 2006
Cambridge, England
13×491 Posts 
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] 
20151117, 14:47  #4  
Sep 2011
3·19 Posts 
Quote:
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] 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 20151117 at 15:03 

20151117, 22:52  #5 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
1110000110101_{2} Posts 
Any reason you're not using Python 3?

20151118, 06:16  #6  
Sep 2011
111001_{2} Posts 
No particular reason, python 2 is what I currently have installed. I'll switch to python 3 soon.
Quote:
Last fiddled with by paul0 on 20151118 at 06:24 

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  20160121 17:13 
Generating LowWeight Ks  henryzz  Riesel Prime Search  9  20120409 21:36 
On the basis of finite fields  meng_luckywolf  Math  6  20071213 04:21 
Generating 2005  Wacky  Puzzles  46  20050605 22:19 
Primegenerating polynomials  Orgasmic Troll  Math  28  20041202 16:37 