Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm trying to implement modular exponentiation in Java using Lagrange and the Chinese remainder theorem.

The example we've been given is:

Let $N = 55 = 5 · 11$ and suppose we want to compute $27^{37} \pmod N$.

He doesn't give us the answer, but says:

The most efficient way to do it is is using Lagrange's theorem, a few multiplications modulo 5 and 11 and CRT to combine both results.

Using Lagrange / Euler totient I get $\varphi(N) = 40$, which it seems I'm supposed to use calculate the congruences needed for putting into the Chinese remainder theorem.

I know I can calculate the congruences using the Extended Euclidean algorithm, but the answers need to be reduced or the run time will still be unfeasible (maybe not in this case, but for the 1024 bit numbers I'm working with, this is a huge problem).

I know they can be reduced, from a document I found while researching this, which states:

$$a^k \equiv a ^ { k \pmod{\varphi(n)}} \pmod n.$$

I've tried and tried and tried to follow how he does the reduction but I just don't get it. He also doesn't mention what $m$ is when he says $k = m · \varphi(n) + k'$.

As you can probably gather, my math is not so hot, so if possible maybe give a "for dummies" answer.

The example given – Let $N = 55 = 5 · 11$ and suppose we want to compute $27^{37} \pmod N$ – is not homework, so if anyone could step me through it, in particular the reductions to get to the simplified Chinese remainder theorem congruences, I would be VERY grateful.

I originally placed this question on Stack Overflow.

share|improve this question
    
After reading your question, I honestly have no idea what you are asking. Perhaps the best thing you could do for now would be to simplify. Remove all the code and just post some simple mathematical equations on what you are trying to do. Also, please post a link to the StackOverflow question so we can keep track of both. –  mikeazo Nov 8 '12 at 12:29
    
Does this question and answer help: crypto.stackexchange.com/questions/2575/… –  mikeazo Nov 8 '12 at 12:33
    
Hey mikeazo, I've edited it, hopefully it's much clearer now. The link you posted for the CRT is certainly helpful, but again, I have trouble following the math near the end of the answer. –  Saf Nov 8 '12 at 13:53
add comment

1 Answer 1

up vote 5 down vote accepted

To step through it simply:

  • Step 1: we first compute compute $M^e \bmod p$ (where $p$ is one of the factors of the modulus. By Fermat's Little Theorem, this is the same as $M^{e \mod p-1} \bmod p$ (and that's where the real savings are), and so in your example ($p=5$), we get:

$M^e \bmod p = 27^{37 \bmod 4} \bmod 5 = 2^1 \bmod 5 = 2$

  • Step 2: we do the same for the other prime $q$:

$M^e \bmod q = 27^{37 \bmod 10} \bmod 11 = 5^7 \bmod 11 = 3$

  • Step 3: using the Chinese Remainder theorem, we reconstruct $M^e \bmod pq$ from $M^e \bmod p$ and $M^e \bmod q$:

$C_p = M^e \bmod p = 2$

$C_q = M^e \bmod q = 3$

$M^e \bmod pq = C_q + q \cdot (q^{-1} (C_p - C_q) \bmod p) = 3 + 11 \cdot (1 \cdot (2-3) \bmod 5) = 3 + 11 \cdot 4 = 47$

share|improve this answer
    
Wow, thank you so much, that makes so much sense. I don't understand, however, how (1 * (2 - 3) mod 5) is 4. 2-3 is -1, multiply by 1 is still -1, mod 5 of -1 is -1? –  Saf Nov 8 '12 at 16:41
    
Well, that's depends on how the mod operator is interpreted when given negative numbers. The traditional mathematical approach (which the above formula uses) is to say 'the value of $a \bmod b$ is the value $0 \le c < b$ such that $a \equiv c (\bmod b)$. With this interpretation, $-1 \bmod 5$ can't be -1, as -1 is not in the range $[0, 5)$. Now, some computer languages don't use this interpretation; those languages were typically not designed by mathematicians. –  poncho Nov 8 '12 at 19:01
1  
To do the computations, you use what is the most efficient: -1 or 4. For instance, I'd compute the $5^7 \mod 11$ above as $5^{-3} \mod 11$ instead. (As $5^3=4\mod 11$ and $4\cdot 3=1\mod 11$, $4^{-1}=3\mod 11$.) For a mathematician, there's an equivalence class, the label does not really matter, although common practice is indeed to use non negative numbers. –  bob Nov 8 '12 at 19:15
    
@bob: Yeah, you're correct; the most mathematical way of thinking about it is equivalence classes. I should have phrased my explanation better. –  poncho Nov 8 '12 at 19:24
    
Poncho if you also have a stack overflow account and would like to maybe answer by linking to this page I'll mark that the answer too. –  Saf Nov 8 '12 at 21:43
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.