Computing a^((N-1)/2) mod N
Date: 12/07/98 at 19:30:32 From: Dana Perriello Subject: How is a^((N-1)/2) mod N done? The Proth's theorem states that N (which is k*2^n+1) is prime if there is an integer a where a^((n-1)/2)=-1(mod N). I want to write a program using that formula. Is there a shortcut for doing a^((n-1)/2) mod N?
Date: 12/08/98 at 20:36:01 From: Doctor Kate Subject: Re: How is a^((N-1)/2) mod N done? Dana: I'm glad to see you're exploring so much. There are a few shortcuts for trying to do large powers in mods. The first uses the nice property that if a = b(mod n) and c = d(mod n), then ac = bd(mod n). You can work this out in the integers by using the definition of the modulus: a = b + nk and c = d + nl for some integers we'll call k and l. So then ac = (b + nk)(d + nl) = bd + nkd + nlb + n^2kl = bd + n(kd + lb + nkl) which means that ac = bd(mod n) since kd + lb + nkl is just some integer. For the rest of my letter, I'm going to write "reduced form of a mod n" to mean the remainder of a when divided by n. We call it "reduced" because it's pretty small. Now what we know, in essence, is that we can get the same answer by reducing things before or after multiplying them together, when we're working in some mod n. Since multiplying smaller things is easier, reducing before we multiply will save us work (and stop the computer from choking on huge numbers). So how can we use this for a shortcut? Well, if the exponent is really large, we can "split it up" because a^(p+q) = (a^p)(a^q) So if we can figure out a^p and a^q, we can reduce them before we multiply them together to get a^(p+q). So we never have to deal with a number as big as a^(p+q) at all. So you might suggest then that to find a^m, you could simply multiply a by itself, reduce, then multiply again by a, then reduce, and so on. However, this is still a lot of work. To save work, there's a really clever trick: Suppose we want to compute a^m, where m is some power of 2. Say a^(2^k), for some integer k. So to begin, we multiply a by a, and reduce. We now know the reduced form of a^2. So instead of multiplying by a and reducing twice more, why don't we just multiply by a^2 instead? This will save a step. So then we find (a^2)*(a^2). When we reduce this, we have the reduced form of a^4, so we can save three steps. This is a really useful trick in general. So you'll have a nice reduced form of a^(2^k) in k steps (try it!) instead of 2^k steps. That's much quicker! But what if m isn't a power of 2? Well, then we can try to write it as a sum of powers of 2. For instance, suppose you have a^21 (mod n). Then, 21 = 16 + 4 + 1 So we can write a^(21) = a^(16+4+1) = a^16 * a^4 * a So we need only figure out reduced forms for a^16, a^4 and a (well, we already have one for a). It will take four steps to find a^16, and we'll find a^4 on the way. So let's do a concrete example. Take 3^21 (mod 7) We find 3^2: 3^2 = 9 = 2(mod 7), so 2 is the reduced form of 3^2. We find 3^4: 3^4 = (3^2)^2 = 2^2 = 4(mod 7), so 4 is the reduced form of 3^4. We find 3^8: 3^8 = (3^4)^2 = 4^2 = 16 = 2(mod 7), so 2 is the reduced form of 3^8. We find 3^16: 3^16 = (3^8)^2 = 2^2 = 4(mod 7), so 4 is the reduced form of 3^4. So now we have 3^21 = 3^16 * 3^4 * 3 = 4 * 4 * 3 = 48 = 6 (mod 7). It's so easy now that we can do it by hand, without the computer! This is a bit tricky to program on a computer, but it is the most useful shortcut we have available for this sort of thing. Don't hesitate to write us again with questions, and good luck! - Doctor Kate, The Math Forum http://mathforum.org/dr.math/
Date: 03/23/2001 at 02:46:52 From: Mike Li Subject: The mistake Dr. Kate made about ac=bd(mod n) Hi - A few days ago I asked a question about modulus, but then I was lucky enough to find Dr. Kate's post in the archive section. It was a great explanation, it helped me to solve the question I asked. However, I believe there was a mistake in the reply: "a = b(mod n) and c = d(mod n), then ac = bd(mod n)". This is not right. Dr. Kate was right about: ac = (b + nk)(d + nl) = bd + nkd + nlb + n^2kl = bd + n(kd + lb + nkl) But then (kd + lb + nkl) might not be the appropriate value to give us the right remainder; in other words, ac still contains extra multiples of n. To get rid of them, we use ac(mod n); therefore the right equation should be: a = b(mod n) and c = d(mod n), then ac(mod n)= bd(mod n) which can be also expressed as a(mod n)^e(mod n)=a^e(mod n), the same equation as in my previous question. This site is great - I love it!
Date: 03/23/2001 at 09:08:13 From: Doctor Peterson Subject: Re: The mistake Dr. Kate made about ac=bd(mod n) Hi, Mike. It appears you have a slight misunderstanding about the meaning of (mod n) as used here - an error that is probably due to the misuse of the term "mod" in the computer programming world, since I see that your previous question dealt with programming. In math, (mod n) is not an operator or modifier of a number (giving its remainder), but a modifier of the whole equation, or rather of the "equals" (congruence) symbol, which tells us in what sense two numbers are "equal." When we write a = b (mod n) (properly using the triple "=" rather than the ordinary "two lines" symbol we have to use here), it means that a and b are "congruent modulo n" - that is, that they differ by a multiple of n. Nothing is said about the size of a or b. (It's worth noting that "modulo n" is actually Latin for "with respect to the modulus, or divisor, n." So "mod n" is really an adverbial phrase modifying the verb "is congruent." And, contrary to common usage, the "modulus" here is n, not a.) In computer languages, "mod" (or a symbol such as %) is used as a remainder operator, so that "b mod n" means "the remainder when you divide b by n." Since this function must give a single number as its value, this is taken to be the principal value of the remainder, 0 <= b mod n < n. (There are conflicting opinions as to what it should mean when b and/or n are negative, sometimes leading to a need for two different operators or functions, MOD and REM; but I won't go into that issue.) In that case, if I said a = b mod n I would be making a statement about the size of a (that it is less than n), not only about the relation between a and b. In these terms, if I wanted to express my congruence above, I could say a mod n = b mod n since two numbers are congruent if and only if they have the same remainder. That appears to be what you are saying; but what you mean is exactly the same as what Dr. Kate said, using proper mathematical terminology. Here are some pages I found (by doing a search for "congruent remainder modulo") that may help clarify some of these ideas: Congruences (from Beachy/Blair, Abstract Algebra) http://www.math.niu.edu/~beachy/abstract_algebra/study_guide/13.html Introduction to Modular Arithmetic - Trailpost 3 http://www.cs.usask.ca/resources/tutorials/csconcepts/numbertheory/tutorial/trail/tp03.html Congruences - Number Theory and Cryptography (Booth) (download PDF file) http://www.ma.umist.ac.uk/rb/teaching/117/part4.pdf You can find a lot more, and probably better, discussions than these if you look around; these are just the first few I found. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.