NFS Square root problems

[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.)



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?

[R.D. Silverman]

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.)



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?

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.

[paul0]

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.

[R.D. Silverman]

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.

[paul0]

Nevermind, I'll be implementing the CRT method.

[jasonp]

Originally Posted by paul0

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?

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).

[paul0]

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

[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.

[paul0]

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.

[paul0]

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.

[stubbscroll]

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.