Chapter 8 Number Theory316
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 knowc, then for any integer,r, you can also compute the remainder,
y, ofrc=2divided byn. Soy^2 rc .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 private keyd, then you
can be sure of being able to factorn.