Thread: modular exponentiation example

I'm trying to follow along this example of modular expression. I have a few questions.

1. Where does the 71 come from
2. What does this mean exactly? x = 16243 ≡ 71 mod 622

************************************************** ************

mod 622.
We first compute the binary expansion of 77 using repeated division by 2:

2 | 77
2 | 38 r 1
2 | 19 r 0
2 | 9 r 1
2 | 4 r 1
2 | 2 r 0
2 | 1 r 0
0 r 1

so that the decimal number 77 is written in binary as 1001101 (notice that we reverse the
list of remainders). So



or simply
77 = 64+8 + 4 + 1.

Now start with x = 16243 ≡ 71 mod 622 and square six times modulo n (six being one
less than seven, the bit-length of 1001101):

x ≡ 71 mod 622
≡ 65
≡ 493
≡ 469
≡ 395
≡ 525
≡ 79

Now refer to the 1’s in the binary expansion of 77, and multiply together the corresponding powers of x modulo n, thus:
≡ 79×469 ≡ 353
≡ 353×493 ≡ 491
= ≡ 491×71 ≡ 29 mod 622

Hello,

Your two questions are one and the same. The expression (read: "a is congruent to b mod n") by definition means that a-b is a multiple of n or equivalently n divides a-b, written respectively as and . This may be hard to remember; it's probably easier to think of it this way: a and b have the same (non-negative) remainder when divided by n. When we specify non-negative remainder, we want the integer in [0,n), also called the common residue. Using the common residue can keep the numbers smaller, making our calculations easier.

You can verify that 71 is the remainder when 16243 is divided by 622.

Formally, we can write



No matter whether we start with 16243, or 71, or 71+622, or 71+2*622, we will get the same result after applying the steps for modular exponentiation, so we might as well choose the smallest.

Also, you can use \cdot in LaTeX for multiplication, it looks like .

Hope this helps.