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

≡ 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

≡ 493

≡ 469

≡ 395

≡ 525

≡ 79≡ 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:

≡ 353×493 ≡ 491

= ≡ 491×71 ≡ 29 mod 622