mersenneforum.org Generating reduced basis for special-q
 Register FAQ Search Today's Posts Mark Forums Read

 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
2015-11-17, 14:19   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by paul0 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]]

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

 2015-11-17, 14:27 #3 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 638310 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 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] and indeed [-6,13] and [-23,-10] appear to have f(x,y)%359==0.
2015-11-17, 14:47   #4
paul0

Sep 2011

3·19 Posts

Quote:
 Originally Posted by fivemack Might you be confusing the matrix-which-reduces-the-basis (which is what qflll() in Pari outputs) with the reduced basis?
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]
which explains why I thought it was right. The current commit works now :)

Quote:
 Originally Posted by R.D. Silverman (1) What is the "L"? Is it a language syntax artifact?
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 2015-11-17 at 15:03

 2015-11-17, 22:52 #5 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2015-11-18, 06:16   #6
paul0

Sep 2011

1110012 Posts

Quote:
 Originally Posted by Dubslow Any reason you're not using Python 3?
No particular reason, python 2 is what I currently have installed. I'll switch to python 3 soon.

Quote:
 Originally Posted by paul0 I have code that tries to generate lattice points of a special-q: https://github.com/paulocode/ppyNFS/...alq-lattice.py
if anyone's looking, I renamed the file: https://github.com/paulocode/ppyNFS/...st-specialq.py

Last fiddled with by paul0 on 2015-11-18 at 06:24

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Science & Technology 15 2016-01-21 17:13 henryzz Riesel Prime Search 9 2012-04-09 21:36 meng_luckywolf Math 6 2007-12-13 04:21 Wacky Puzzles 46 2005-06-05 22:19 Orgasmic Troll Math 28 2004-12-02 16:37

All times are UTC. The time now is 17:46.

Wed Apr 21 17:46:24 UTC 2021 up 13 days, 12:27, 0 users, load averages: 3.09, 2.86, 2.58