20150114, 14:21  #1 
Sep 2011
39_{16} 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.)
My problem is that the coefficients get unwieldy because of the exponent of 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 . This seems to be the simplest way, is there a more trivial way of taking the square root? Last fiddled with by paul0 on 20150114 at 14:27 
20150114, 14:59  #2  
Nov 2003
1D24_{16} Posts 
Quote:
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. 

20150114, 15:14  #3  
Sep 2011
111001_{2} Posts 
Quote:


20150114, 17:22  #4 
Nov 2003
2^{2}×5×373 Posts 

20150115, 00:45  #5 
Sep 2011
3×19 Posts 
Nevermind, I'll be implementing the CRT method.

20150115, 15:34  #6  
Tribal Bullet
Oct 2004
3532_{10} Posts 
Quote:
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 qadic iteration has enough precision. Note that polynomial coefficients may be negative, which are large positive numbers mod q^(2^k). 

20150116, 00:21  #7 
Sep 2011
3·19 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 20150116 at 00:28 
20150117, 13:32  #8 
Sep 2011
57_{10} 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^d1)/(p1)) * 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 2subgroups (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 20150117 at 13:42 
20150117, 15:41  #9  
Sep 2011
3·19 Posts 
Quote:


20150117, 18:57  #10 
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 20150117 at 19:00 
20150119, 12:25  #11 
Oct 2014
1 Posts 
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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
All square roots failed  chris2be8  Msieve  13  20201014 07:08 
Square Root Days  davar55  Lounge  0  20160316 20:19 
square root crash  bsquared  Msieve  17  20100409 14:11 
Square root of 3  Damian  Math  3  20100101 01:56 
Divisible up to Square Root  davar55  Puzzles  3  20070905 15:59 