Introduction to Cryptography with Open-Source Software

Random numbers and stream ciphers 353

be computed, and so on). A s quare root that is itself a quadratic residue is

called a principal square root.

In general,



y

(p+1)/4)



h+1

(mod p)

will be the principal 2

h+1

-th root of y. Since by Fermat’s theorem, z

p−1

= 1

(mod p) for any z, the exponent can be reduced

((p + 1)/4)

h+1

by p −1 before ra ising y to that power. Tha t is, the principal 2

h+1

-th root of

y modulo p can be obtained by

y

((p+1)/4)

k+1

mod p−1

(mod p).

This is easiest broken down into two steps:

1. A

p

= ((p + 1)/4)

k+1

mod p − 1.

2. a

p

= y

A

p

(mod p).

The principal 2

h+1

-th root modulo n is obtained by pe rforming these opera-

tions for both p a nd q, and applying the Chines e remainder theorem to obtain

a result modulo n. But that is exactly the sequence of ...