View Single Post
Old 2015-11-17, 13:39   #1
paul0
 
Sep 2011

3916 Posts
Default 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
paul0 is offline   Reply With Quote