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

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

$\displaystyle 16243^{77}$ 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$\displaystyle 77 = 1×2^6 + 0×2^5 + 0×2^4 + 1×2^3 +1×2^2 + 0×2^1 + 1×2^0$

so that the decimal number 77 is written in binary as 1001101 (notice that we reverse the

list of remainders). So

$\displaystyle x^2$ ≡ 65

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

$\displaystyle x^{4}$≡ 493

$\displaystyle x^{8}$ ≡ 469

$\displaystyle x^{16}$ ≡ 395

$\displaystyle x^{32}$ ≡ 525

$\displaystyle x^{64}$ ≡ 79$\displaystyle x^{64+8}$ ≡ 79×469 ≡ 353

Now refer to the 1’s in the binary expansion of 77, and multiply together the corresponding powers of x modulo n, thus:

$\displaystyle x^{64+8+4}$ ≡ 353×493 ≡ 491

$\displaystyle x^{77}$ = $\displaystyle x^{64+8+4+1}$ ≡ 491×71 ≡ 29 mod 622