View Single Post
 2015-11-17, 13:39 #1 paul0   Sep 2011 3×19 Posts 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