0
$\begingroup$

How to solve a problem like this:

Let $N = 11$. What is $2^{2652557887263} \pmod N$?

As part of the questions we are given the multiplication table for $\mathbb{Z}_{11}$:

x | 1  2  3  4  5  6  7  8  9  10
---------------------------------
1 | 1  2  3  4  5  6  7  8  9 10
2 | 2  4  6  8 10  1  3  5  7  9
3 | 3  6  9  1  4  7 10  2  5  8
4 | 4  8  1  5  9  2  6 10  3  7
5 | 5 10  4  9  3  8  2  7  1  6
6 | 6  1  7  2  8  3  9  4 10  5
7 | 7  3 10  6  2  9  5  1  8  4
8 | 8  5  2 10  7  4  1  9  6  3
9 | 9  7  5  3  1 10  8  6  4  2
10|10  9  8  7  6  5  4  3  2  1

...as well as $(\mathbb{Z}_{11}^*,\times)$, the group of units of $\mathbb{Z}_{11}$ under multiplication:

exp|  0   1   2   3   4   5   6   7   8   9   10
 ------------------------------------------------
 g | g^0 g^1 g^2 g^3 g^4 g^5 g^6 g^7 g^8 g^9 g^10
 ------------------------------------------------
 1 |  1   1   1   1   1   1   1   1   1   1   1
 2 |  1   2   4   8   5  10   9   7   3   6   1
 3 |  1   3   9   5   4   1   3   9   5   4   1
 4 |  1   4   5   9   3   1   4   5   9   3   1
 5 |  1   5   3   4   9   1   5   3   4   9   1
 6 |  1   6   3   7   9  10   5   8   4   2   1
 7 |  1   7   5   2   3  10   4   6   9   8   1
 . |
 10|  1  10   1  10   1  10   1  10   1  10   1

Overall, I'm having trouble understanding how the numbers in the table are generated, and how they're used to solve the aforementioned question.

$\endgroup$
0

2 Answers 2

2
$\begingroup$

The second row of the second table gives you the values of $g^e\pmod{11}$ for $0 \le e \le 10$. Notice that $2^{10}\pmod{11} \equiv 2^{0}\pmod{11}$. This means that $2^{10}$ raised to any power is congruent to $1\pmod{11}$.

With that in mind, it shouldn't be hard to see that $2^{2652557887263}\pmod{11} \equiv 2^3\pmod{11}$. So the answer is $8$.


P.S. I suspect your question may be slightly off-topic for this site, hence the down votes.

$\endgroup$
2
  • $\begingroup$ I think I'm starting to see it, but I'm still a little unsure. So suppose I had 2^235422656452414554 (mod 11), would that be 2^4 (mod 11), or 16? $\endgroup$
    – D. Crypt
    Nov 15, 2016 at 18:57
  • $\begingroup$ There is no "$16$" in $\mathbb{Z}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\}$ $\endgroup$
    – tylo
    Nov 15, 2016 at 19:07
0
$\begingroup$

Modular exponentiation is done by Square and Multiply. And usually after each step the modulo operation is used.

And large exponents as in your example can be reduced by Euler's theorem, with the special case of $n$ being prime covered by Fermat's little theorem.

With that, you can actually calculate an equivalent exponent to $x$ as $ x' = x\mod \phi(n)$. In your example $\phi(n) = 10$ you get $2652557887263 = 3 \mod 10$

Edit: In general when dealing with modular arithmetic, you're not actually calculating with the usual integers - we just use those integers are representations for so-called congruence classes, see the chapter about that in Wikipedia on modular arithmetic.

$\endgroup$

Your Answer

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

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