mersenneforum.org NFS Square root problems
 Register FAQ Search Today's Posts Mark Forums Read

 2015-01-14, 14:21 #1 paul0   Sep 2011 3×19 Posts NFS Square root problems Hi, I didn't think NFS could get more complicated until I got to the square root stage. Anyway, I'm trying to implement the NFS square root as described here: http://www.mersenneforum.org/showthread.php?t=6670 (which in turn is from Buhler et. al.) $S_{k+1} = \frac{S_k (3 - S * S_k^2)}{2} mod q^{2^k}$ My problem is that the coefficients get unwieldy because of the exponent of $q^{2^k}$ and all those multiplications. Is this normal? Also, I can't get the proper square root after multiplying S, I just get really large coefficients, even after taking modulo $q^{2^k}$. This seems to be the simplest way, is there a more trivial way of taking the square root? Last fiddled with by paul0 on 2015-01-14 at 14:27
2015-01-14, 14:59   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by paul0 Hi, I didn't think NFS could get more complicated until I got to the square root stage. Anyway, I'm trying to implement the NFS square root as described here: http://www.mersenneforum.org/showthread.php?t=6670 (which in turn is from Buhler et. al.) $S_{k+1} = \frac{S_k (3 - S * S_k^2)}{2} mod q^{2^k}$ My problem is that the coefficients get unwieldy because of the exponent of $q^{2^k}$ and all those multiplications. Is this normal? Also, I can't get the proper square root after multiplying S, I just get really large coefficients, even after taking modulo $q^{2^k}$. This seems to be the simplest way, is there a more trivial way of taking the square root?
It depends on what you mean by trivial. If you want to bound the size of the arithmetic, use Peter Montgomery's method based
on fractional ideals and lattice basis reduction.

Another "trivial" way is to actually find generators of the ideals, as well as computing the unit group. Then, the square root can be found
by taking a dependency, adding up the exponents, dividing by 2, then multiplying out the ideal generators mod N. You must also
correct for unit group not having argument 0 via (say) a Givens (or similar rotation); figure out the correct powers of the generators
of the unit group by computing logs of a particular embedding then force the logs to sum to 0.

2015-01-14, 15:14   #3
paul0

Sep 2011

718 Posts

Quote:
 Originally Posted by R.D. Silverman It depends on what you mean by trivial. If you want to bound the size of the arithmetic, use Peter Montgomery's method based on fractional ideals and lattice basis reduction. Another "trivial" way is to actually find generators of the ideals, as well as computing the unit group. Then, the square root can be found by taking a dependency, adding up the exponents, dividing by 2, then multiplying out the ideal generators mod N. You must also correct for unit group not having argument 0 via (say) a Givens (or similar rotation); figure out the correct powers of the generators of the unit group by computing logs of a particular embedding then force the logs to sum to 0.
Thanks, I'm studying Montgomery's paper. It looks complicated and beyond grasp, but hey, understanding NFS seemed impossible a month ago, yet here I am.

2015-01-14, 17:22   #4
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by paul0 Thanks, I'm studying Montgomery's paper. It looks complicated and beyond grasp, but hey, understanding NFS seemed impossible a month ago, yet here I am.
It is indeed complicated.

 2015-01-15, 00:45 #5 paul0   Sep 2011 3·19 Posts Nevermind, I'll be implementing the CRT method.
2015-01-15, 15:34   #6
jasonp
Tribal Bullet

Oct 2004

2×3×19×31 Posts

Quote:
 Originally Posted by paul0 My problem is that the coefficients get unwieldy because of the exponent of $q^{2^k}$ and all those multiplications. Is this normal? Also, I can't get the proper square root after multiplying S, I just get really large coefficients, even after taking modulo $q^{2^k}$. This seems to be the simplest way, is there a more trivial way of taking the square root?
See this reference. Couveignes' algorithm is handy for odd degree, but large coefficients are a requirement for the brute force method.

If you implement the Newton method correctly, then as q^(2^k) increases the polynomial coefficients become larger until q^(2^k) exceeds the size of the coefficients of the answer; then they stop growing because the q-adic iteration has enough precision. Note that polynomial coefficients may be negative, which are large positive numbers mod q^(2^k).

 2015-01-16, 00:21 #7 paul0   Sep 2011 3916 Posts Hi, I'm almost done implementing the CRT method, but i'm having trouble with the prime tests, specifically the polynomial GCD mod p part. I posted my code & (wrong?) results in the programming section: http://www.mersenneforum.org/showthread.php?p=392530 Last fiddled with by paul0 on 2015-01-16 at 00:28
 2015-01-17, 13:32 #8 paul0   Sep 2011 718 Posts I "finished" my CRT implementation, it works for both Briggs' and Spaans' ( http://daim.idi.ntnu.no/masteroppgav...teroppgave.pdf ) example. I followed Briggs' method line by line, except I calculated r by using python's Fraction module (and then rounding this to an integer) instead of floating point arithmetic. To select the positive square root in each field GF(p) (i.e. Z[x]/f(x) mod p), I calculate the norm for each GF(p) by: N_p(sqrt(S)) = f'(a)^((p^d-1)/(p-1)) * sqrt(N(a+ba) * N(a+ba) * N(a+ba) ... ) mod p So I compare that with the norm of the square roots in GF(p), so I have the proper positive square root. Now, it works for both examples (even with different random primes with proper bounds), but it rarely works for (a,b) pairs that I find myself. Everything else works - I find a square root in GF(p) through Sylows 2-subgroups (as per Briggs), the postive square root check works, I even take the square of the square root in GF(p) just to make sure. But when I calculate the actual integer through CRT, I don't get a congruence. It seems to only work for a small subset of squares in Z[a]. Again, it only works for Briggs' and Spaans' example, and some rare occurrences of (a,b)-pairs I find (through sieving & matrix reduction). Has anyone dealt with this before? I'm hesitant to post code for now because it's unclean, but I'll github this when I clean it up. Last fiddled with by paul0 on 2015-01-17 at 13:42
2015-01-17, 15:41   #9
paul0

Sep 2011

3×19 Posts

Quote:
 Originally Posted by paul0 I "finished" my CRT implementation, it works for both Briggs' and Spaans' ( http://daim.idi.ntnu.no/masteroppgav...teroppgave.pdf ) example. I followed Briggs' method line by line, except I calculated r by using python's Fraction module (and then rounding this to an integer) instead of floating point arithmetic. To select the positive square root in each field GF(p) (i.e. Z[x]/f(x) mod p), I calculate the norm for each GF(p) by: N_p(sqrt(S)) = f'(a)^((p^d-1)/(p-1)) * sqrt(N(a+ba) * N(a+ba) * N(a+ba) ... ) mod p So I compare that with the norm of the square roots in GF(p), so I have the proper positive square root. Now, it works for both examples (even with different random primes with proper bounds), but it rarely works for (a,b) pairs that I find myself. Everything else works - I find a square root in GF(p) through Sylows 2-subgroups (as per Briggs), the postive square root check works, I even take the square of the square root in GF(p) just to make sure. But when I calculate the actual integer through CRT, I don't get a congruence. It seems to only work for a small subset of squares in Z[a]. Again, it only works for Briggs' and Spaans' example, and some rare occurrences of (a,b)-pairs I find (through sieving & matrix reduction). Has anyone dealt with this before? I'm hesitant to post code for now because it's unclean, but I'll github this when I clean it up.
And one more thing, people recommend a CRT implementation I can study. Thanks.

 2015-01-17, 18:57 #10 paul0   Sep 2011 3·19 Posts I found an implementation: https://github.com/stubbscroll/nfs/blob/master/nfs.c Line 1229 This tells me that I have to select primes such that (using Briggs' notation, page 59) p^3 -1 = s * 2^r, where r needs to be small. This was what made my square root code work. What is the significance of this? Edit: I also copied the code that avoids the rounding off of integers. Last fiddled with by paul0 on 2015-01-17 at 19:00
2015-01-19, 12:25   #11
stubbscroll

Oct 2014

1 Posts

Quote:
 Originally Posted by paul0 Line 1229 This tells me that I have to select primes such that (using Briggs' notation, page 59) p^3 -1 = s * 2^r, where r needs to be small. This was what made my square root code work. What is the significance of this?
I am the author of that NFS program. The reason for requiring small r is to make one of the subroutines easier to implement. polysqrtmod() (which finds square roots in GF(p^3), if I remember correctly), starting at line 1054, uses 2^r iterations in one of the operations.

 Similar Threads Thread Thread Starter Forum Replies Last Post chris2be8 Msieve 13 2020-10-14 07:08 davar55 Lounge 0 2016-03-16 20:19 bsquared Msieve 17 2010-04-09 14:11 Damian Math 3 2010-01-01 01:56 davar55 Puzzles 3 2007-09-05 15:59

All times are UTC. The time now is 05:27.

Mon Mar 8 05:27:29 UTC 2021 up 95 days, 1:38, 0 users, load averages: 2.27, 2.43, 2.57