mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-01-14, 14:21   #1
paul0
 
Sep 2011

3916 Posts
Default 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
paul0 is offline   Reply With Quote
Old 2015-01-14, 14:59   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by paul0 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-01-14, 15:14   #3
paul0
 
Sep 2011

1110012 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
paul0 is offline   Reply With Quote
Old 2015-01-14, 17:22   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by paul0 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-01-15, 00:45   #5
paul0
 
Sep 2011

3×19 Posts
Default

Nevermind, I'll be implementing the CRT method.
paul0 is offline   Reply With Quote
Old 2015-01-15, 15:34   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

353210 Posts
Default

Quote:
Originally Posted by paul0 View Post
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).
jasonp is offline   Reply With Quote
Old 2015-01-16, 00:21   #7
paul0
 
Sep 2011

3·19 Posts
Default

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
paul0 is offline   Reply With Quote
Old 2015-01-17, 13:32   #8
paul0
 
Sep 2011

5710 Posts
Default

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
paul0 is offline   Reply With Quote
Old 2015-01-17, 15:41   #9
paul0
 
Sep 2011

3·19 Posts
Default

Quote:
Originally Posted by paul0 View Post
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 is offline   Reply With Quote
Old 2015-01-17, 18:57   #10
paul0
 
Sep 2011

3·19 Posts
Default

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
paul0 is offline   Reply With Quote
Old 2015-01-19, 12:25   #11
stubbscroll
 
Oct 2014

1 Posts
Default

Quote:
Originally Posted by paul0 View Post
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.
stubbscroll is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
All square roots failed chris2be8 Msieve 13 2020-10-14 07:08
Square Root Days davar55 Lounge 0 2016-03-16 20:19
square root crash bsquared Msieve 17 2010-04-09 14:11
Square root of 3 Damian Math 3 2010-01-01 01:56
Divisible up to Square Root davar55 Puzzles 3 2007-09-05 15:59

All times are UTC. The time now is 23:45.

Sat Dec 5 23:45:01 UTC 2020 up 2 days, 19:56, 0 users, load averages: 1.57, 1.71, 1.74

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.