1. Prove the following: If P and q are primes, p t q. p|d, and q|d, then pq|d.
(I stated this fact without proof in the RSA notes.)
6. Recall our discussion of partial information on RSA. We defined the
parify(2° mod n) =
if I mod n is even
if I mod n is odd
half(2" mod n)
if x mod n < n/2
if x mod n > n/2
Here e and n are the usual RSA public key parameters, and I is an RSA
plaintext message, which means that it's an integer less than n.
Prove the following:
if half(2° mod n) = 1, then parify((2x) mod n) = 1.
7. Let p be prime. Prove that if I2 III 1 mod P and I # (p - 1) mod p. then
III 1 mod p. [Note that (p - 1) III (mod p)]
8. Suppose that p is prime, l' > 0, a III 1 mod p. and god(r.p - 1) = d.
Prove that ad III 1 mod p.
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.