Chapter 8 Number Theory228
(b)Conclude that 4 dividesx.(c)Show that if gcd.r;n/D 1 , thenrx1 .modn/:
Asquare rootofmmodulonis a nonnegative integers < nsuch thats^2 m
.modn/. Here is a nice fact to know: whennis a product of two odd primes, then
every numbermsuch that gcd.m;n/D 1 has 4 square roots modulon.
In particular, the number 1 has four square roots modulon. The two trivial ones
are 1 andn 1 (which is 1 .modn/). The other two are called thenontrivial
square roots of 1.
(d)Since you knowx, then for any integer,r, you can also compute the remainder,
y, ofrx=2divided byn. Soy^2 rx .modn/. Now ifris relatively prime ton,
thenywill be a square root of 1 modulonby part (c).
Show that ifyturns out to be anontrivialroot of 1 modulon, then you can factor
n.Hint:From the fact thaty^2 1 D.yC1/.y 1/, show thatyC 1 must be
divisible by exactly one ofqandp.
(e)It turns out that at least half the positive integersr < nthat are relatively
prime tonwill yieldy’s in part (d) that are nontrivial roots of 1. Conclude that if,
in addition tonand the public key,e, you also knew the secret keyd, then you can
be sure of being able to factorn.