Introduction to Cryptography with Open-Source Software

Advanced computational number theory 421

and

a

y

k

(p−1)/q

= (A

k

)

(p−1)/q

k+1

(mod p).

Further details can be found in Yan [97] or Crandall and Pomerance [23].

There is also a Pollard rho method, similar in style to the method for

factoring. To find

log

a

y (mod n)

where n is not necessarily prime, the method generates pseudo-random tr iples

[x, r, s] for which

x = a

r

y

s

(mod n)

until two values are found tha t have equal x values:

a

r

i

y

s

i

= a

r

j

y

s

j

(mod n).

In that case the lo garithm is

(r

i

− r

j

)/(s

i

− s

j

) (mod n − 1)

assuming that the inverse exists. To find equal values, the following “random”

function:

ψ(x, a, y) =







(x

2

mod n, 2r mod n − 1, 2s mod n − 1) if x = 0 (mod 3)

(ax mod n, r + 1 mod n − 1, s mod n − 1) if x = 1 (mod 3 )

(yx mod n, r mod n − 1, s + 1 mod n − 1)