2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – mikeazo
    Nov 8, 2012 at 12:29
  • $\begingroup$ Does this question and answer help: crypto.stackexchange.com/questions/2575/… $\endgroup$
    – mikeazo
    Nov 8, 2012 at 12:33
  • $\begingroup$ 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. $\endgroup$
    – Saf
    Nov 8, 2012 at 13:53

1 Answer 1

Reset to default
6
$\begingroup$

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$

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Saf
    Nov 8, 2012 at 16:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – poncho
    Nov 8, 2012 at 19:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – bob
    Nov 8, 2012 at 19:15
  • $\begingroup$ @bob: Yeah, you're correct; the most mathematical way of thinking about it is equivalence classes. I should have phrased my explanation better. $\endgroup$
    – poncho
    Nov 8, 2012 at 19:24
  • $\begingroup$ 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. $\endgroup$
    – Saf
    Nov 8, 2012 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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