From: smith (sandor23) Newsgroups: sci.math Subject: Re: modular square root of a 512-bit number Date: Sun, 13 Nov 1994 12:21:21 -0800 In article , mschoene@math.rwth-aachen.de (Martin Schoenert) wrote: > Could you describe the algorithm you use, or give a reference? The algorithm is due to Derrick Lehmer. You can find it on page 109 of David Bressoud's text "Factorization & Primality Testing". Here is one version of it. Have p = odd prime, 0 < n < p, and (n/p) = +1. Want s such that s^2 = n (mod p). Put q = (p+1)/2. Case p mod 4 = 3: s = n^(q/2) (mod p), using the binary power algorithm. Case p mod 4 = 1: s = 1 n = n-1 while (n/p) = +1 { s = s+1 n = (n-2s+1) mod p if n = 0 return /* s is square root */ } q = q/2 /* integer division */ v = 1 r = s u = 1 while q > 0 { x = (rr - nuu) mod p /* rr = r^2, etc. */ u = 2ru mod p r = x if q odd { x = (sr - nvu) mod p v = (vr + su) mod p s = x } q = q/2 } return There are log2(p/4) steps in the second "while" loop. The time is almost independent of p or n (except for some very special cases that run faster than the average). The only problem with this algorithm is the (approx) 3 "mod p" and (approx) 6-7 multiplies per loop. Multiplies are not so bad but mod's are slow, especially with multi precision arithmetic. It would be nice to have a version that replaced them by shifts (as in the binary gcd and binary Jacobi algorithms). But I have not the faintest idea how it would go ! There is a simpler way of finding s when p mod 8 = 5. It still has the same number of steps, but less mod's and multiplies. Realized after my last post that I had forgotten about Daniel Shanks algorithm. It of course works with the 2 exponent of p-1. For some reason I had not used it for a long time. Probably just because it can have bad run times when this exponent gets large. But it may run faster than the Lehmer method in many situations ? If anyone does comparisons of the methods please post them, or let me know. Nick Burgoyne 13 Nov 1994 ============================================================================== From: mschoene@math.rwth-aachen.de (Martin Schoenert) Newsgroups: sci.math Subject: Re: modular square root of a 512-bit number Date: 14 Nov 94 08:19:58 GMT I wrote: smith (sandor23) writes: >When p mod 4 = 1 it is also a modular power >computation but now using 2 by 2 integer matrices. >The latter case takes about twice as long as the >p mod 4 = 3 case. Neither depend on factors of p-1. I know such an algorithm that can be used if p mod 8 = 5. However, it doesn't work if p mod 8 = 1. >There may be other algorithms that depend on the 2 exp. >of p-1 but I havnÕt seen them in number theory compÕs. Knuth in TACP Seminumerical Algorithms 4.6.2 exercise 15, describes such an algorithm. He doesn't mention an algorithm that works independent of the power of 2 dividing p-1. Could you describe the algorithm you use, or give a reference? Eggs in my face. There is such an algorithm, and I knew it once. According to Bob Riley, who reminded me of this algorithm, it is due to D.H. Lehmer and given in his contribution to MAA Studies in Number Theory. It is usually described using Lucas sequences. As usual with Lucas sequences, it can also be formulated using powers of 2x2 matrices. I once reformulated it using powers of elements in GF(p^2). Allow me to present this formulation. Suppose we want to compute the root of s modulo the prime p. Find a P such that D := P^2/4 - s is a quadratic nonresidue modulo p, i.e., such that Jacobi( D, p ) = -1. It is easy to show that such a P must always exist. Unfortunatly trying P = 0, 1, ... until one is found, seems to be the best known method. We now compute in GF(p^2) = GF(p)[sqrt(D)]. That is we compute with the formal elements a + b sqrt(D), where 0 <= a, b < p, and where the multiplication is defined by (a + b sqrt(D)) * (c + d sqrt(D)) := (a c + b d D) + (a d + b c) sqrt(D). (This is identical to the construction of the complex numbers as the set of formal elements a + b sqrt(-1), where a and b are real). Raising to the p-th power is the conjugation in this field GF(p^2), so (P/2 + sqrt(D))^p = (P/2 - sqrt(D)), (P/2 + sqrt(D))^(p+1) = (P/2 - sqrt(D)) (P/2 + sqrt(D)) = P^2/4 - D = s (P/2 + sqrt(D))^((p+1)/2) = sqrt(s) Note that this holds always, but sqrt(s) is real (i.e., in GF(p)), if and only if s is a quadratic residue modulo p. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany ============================================================================== Date: Tue, 6 Dec 94 14:34:12 CST From: rusin (Dave Rusin) To: GSXGC@CUNYVM.CUNY.EDU Subject: Re: x^2-a mod p Newsgroups: sci.math.research In article <94339.215422GSXGC@cunyvm.cuny.edu> you write: >Is there a deterministic algorithm for computing square roots of r mod p where >p is quite large? That is, an algorithm which will run in time polynomial in >log p. Of course, I'm only interested in the case where r is already known >to be a quadratic residue mod p and p=1 mod 4 (I already know a solution for >p=3 mod 4). So that's not good enough, eh? The solution in the general case is rather similar, although there's one part I can't remember if you can do 'deterministically'. In the general case, write p = 1 + (2^r).s with s odd. Then for any x mod p, we have 1 = x^(p-1) = (x^s)^(2^r). So if you have a complete set of 2^r-th roots of 1, namely {1, -1, ..., z} then x^s is one of these elements (I'll call it z). It follows that x=z^-1 . x^(1+s) = z^(-1) . a^((1+s)/2) if a = x^2. Thus, x can be computed from a by a simple power operation (which _is_ fast). You need to know which root of unity z is, but the square of the preceding equations gives z^2= a^(1+s) / x^2 = a^s, you just compute a^s, compare that to your known 2^rth roots of unity, and pick out the others in the list whose square is z^2=a^s; then as above you have your square root, x=z^(-1). a^((s+1)/2). For example, let's take p=41, a=39. In this case, 41= 1 + 8.5, so the right power of a is a^(5+1)/2 = a^3. I get 33 mod 41. This differs from the correct square root by an 8th root of unity. Well, the 2nd, 4th, and 8th roots of 1 mod 41 are +-1, +-9, and +-3, +-27. In our case, 39^5= 9, so we adjust our first guess by dividing by the square root of 9, which is 3; so the square root ought to be 33/3=11. Indeed, 11^2=39. Now, in this sample calculation, all is fine as long as we are raising to powers or dividing. At one point I appeared to take the square root of 9, but I did that by a lookup to the list of 8th roots of 1. This you can do in general. The only real problem, then, is in the initial computation of the 2^rth roots of 1, arranged so that you know which is the square of which. [This last part of course is easy to arrange if you have all the 2^r-th roots.] This is the part I'm not sure about if you insist on doing things quickly. If you need to take lots of square roots with a fixed modulus p, then you get to spread the cost of these initial roots out over the total number of runs, making it inexpensive in any case. Here's how I would find the 2^rth roots. Consider the sequence of residues 2, 3, ... mod p. For each one, compute (by reciprocity) whether the residue is a square mod p. If some residue t is not a square, compute w=t^s; this is a primitive 2^rth root of unity. You then take the powers w, w^2, w^3, ...; these are all the other 2^r roots of unity, and it is clear as you compute them which are the squares of which. I don't know if you consider this 'deterministic', since it is not known (I think) how far you have to go before you find a non-square z. Statistically speaking, since only half of the residues z are squares, the likelihood you'll fail n times in a row is 2^-n, so you can expect a win after about n=log_2(p) trials. It seems to me that this approach is reasonably effective. I do know that modular square root algorithms are incorporated into some existing software, and they certainly seem to be fast; I don't know how far they improve the above approach. Good luck, dave (If you hear of any other approach that can, for example, find z1=sqrt(-1), z2=sqrt(z1), etc. quickly, let me know) ============================================================================== Date: Tue, 06 Dec 94 17:06:56 EST From: Greg Stein Subject: Re: x^2-a mod p To: Dave Rusin Thanks for your reply. I was already aware of the algorithm for p=3 mod 4 and I've been informed by Len Adleman at USC that there is no known poly time algorithm (in log p) for the general case without ERH, although there are apparently very efficient probabalistic techniques. Tahnks for the reply!! -- Greg Stein ============================================================================== From: cet1@cus.cam.ac.uk (Chris Thompson) Newsgroups: sci.math Subject: Re: x^2-a mod p Date: 6 Dec 1994 21:53:26 GMT In article <1994Dec6.022755.9223@timessqr.gc.cuny.edu>, gsx@CUNYVMS1.GC.CUNY.EDU (Cracker Jack) writes: |> Does anyone out there know of a deterministic algorithm which computes square |> roots mod p (p prime). It is assumed that we are dealing with a quadratic |> residue to begin with and that p is quite large, so I need an algorithm which |> runs in time polynomial in log p. If you know of such an algorithm, or know |> that none exists, please e-mail me at gsxgc@cunyvm.cuny.edu Have a look at the answers to exercise 4.6.2/15 in Knuth ACP 2 "Seminumerical Algorithms" for several methods. Tonelli-Shanks is probably the most commonly used. Strictly, all these algorithms are random polynomial time, although in Tonelli-Shanks, for example, the random-ness is only needed to find one non-QR mod p (one could do this in deterministic polynomial time if GRH were true). There is a hypothesis-free deterministic polynomial time algorithm for taking square roots mod p due to Schoof, a side-product of his algorithm for determining the number of points on elliptic curves mod p. This isn't a practical method, though. Also e-mailed as requested. Chris Thompson Internet: cet1@phx.cam.ac.uk JANET: cet1@uk.ac.cam.phx ============================================================================== From: brock@ccr-p.ida.org (Bradley Brock) Newsgroups: sci.math.research Subject: Re: x^2-a mod p Date: 6 Dec 1994 21:49:55 -0500 In article <94339.215422GSXGC@CUNYVM.CUNY.EDU>, wrote: >Is there a deterministic algorithm for computing square roots of r mod p where >p is quite large? That is, an algorithm which will run in time polynomial in >log p. Of course, I'm only interested in the case where r is already known >to be a quadratic residue mod p and p=1 mod 4 (I already know a solution for >p=3 mod 4). If it makes any difference I'm really only interested in the case >where p has order (r-1)/2 mod r. Rene' Schoof had an article in Math. Comp. a few years ago (late '80s?) that proved just this using elliptic curves over F_p. If you can't find it let me know and I'll look it up. -- Bradley W. Brock | "Football exemplifies the worst features of American IDA/CCR-P, Thanet Road | life: it's violence punctuated by committee meetings." Princeton, NJ 08540 | --George Will brock@ccr-p.ida.org,brock@alumni.caltech.edu,609-279-6350(w),609-924-3061(fax) ============================================================================== From: Leif.Nilsen@alcatel.no (Leif Nilsen) Newsgroups: sci.math.research Subject: Re: x^2-a mod p Date: 7 Dec 1994 08:10:38 GMT In article <94339.215422GSXGC@CUNYVM.CUNY.EDU>, writes: |> Is there a deterministic algorithm for computing square roots of r mod p where |> p is quite large? That is, an algorithm which will run in time polynomial in |> log p. Of course, I'm only interested in the case where r is already known |> to be a quadratic residue mod p and p=1 mod 4 (I already know a solution for |> p=3 mod 4). If it makes any difference I'm really only interested in the case |> where p has order (r-1)/2 mod r. |> |> Thanks!! -- Greg Stein (gsxgc@cunyvm.cuny.edu) |> Take a look at Adleman, Manders and Miller: "On taking roots in finite fields", Proceedings of the 20th Annual Symposium on the Foundations of Computer Science (1979), p. 175-178. Their algorithm is "almost" deterministic, but you need to find a quadratic non-residue mod p. This is normally done by testing a few numbers. However, Ankeny has showed that such numbers can be found in polynomial time assuming the extended Riemann hypothesis! This means that the Adleman, Manders, Miller algorithm is deterministic under this assumption. Se also: R. Schoof: "Elliptic Curves over Finite Fields and the Computation of Square Roots mof p", Mathematics of Computation, Vol 44, No. 170, April 1985 Leif Nilsen, Alcatel Telecom Norway ==============================================================================