Question

Notes 2.5 1 is a square (mod 35). Two of its square roots are 1 and (‐1 ≡ 34 (mod 35)). What are the other two?

Notes 2.6 Consider all the possible sets of two square roots s, t of 1 (mod 35) where s ≢ t (mod 35) (there are six of them, since addition is commutative (mod 35).

For all possible combinations, compute gcd(s + t, 35). Which combinations give you a single prime factor of 35?

Notes 2.7 Using CRT notation, show what is going on for all the combinations you considered in Notes 2.6. Explain why gcd(s + t, 35) sometimes gave you a factor, and it sometimes did not

Notes 2.8 Explain how you can make a digital signature that is mathematically equivalent to factoring using the results you considered in this Notes.

Answer 1

2.5.1)

So that

Thus,

Solving each of these equations pairwise we get

So the other two roots are

Hope this was helpful. Please do leave a positive rating if you liked this answer. Thanks and have a good day!