Discrete Mathematics · Divisibility, modular arithmetic, and elementary number theory
RSA decryption needs Euler, and Euler needs a coprime message
Problem
Discrete Mathematics practice problemLet and , and set . Let .
1. Compute from the product formula, and prove that . Find the unique with andDo not invert modulo .
2. Prove Euler's theorem: if , then . Your proof should use that multiplication by permutes .
3. Let be an integer with , and set . Using only Euler's theorem and the congruence , proveThen, for the plaintext , compute the ciphertext and verify . Record both residues in .
4. Let . Compute and prove that Euler's theorem does not apply to modulo , by showing . Explain why quoting Euler on cannot justify RSA decryption of , even if some other argument (not requested here) might still recover . Also explain why the private exponent must be an inverse of modulo rather than modulo .
Do not treat as prime, do not replace by , and do not skip the coprime-message hypothesis.
Hint
Hint. The inverse of modulo satisfies ; try .
Check your work
Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.
The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Discrete Mathematics sample problem: Try the free sample problem.
More Discrete Mathematics practice problems
- Let p, q, and r be propositionsPropositional and predicate logic with proof methods
- Let A={1,2,3,4} and B={3,4,5,6}Propositional and predicate logic with proof methods
- Let R be a relation on a set ASets, functions, relations, and equivalence classes
- Use strong induction to prove that every positive integer n can be written as n=2^k m…Sets, functions, relations, and equivalence classes
- (Honors) Let uₙ be defined by u₀=0, u₁=1, and uₙ=4uₙ₋₁-4uₙ₋₂+n for n ≥ 2Induction, recursion, and invariants
- [Honors] Using inclusion-exclusion, find the number of permutations π of {1,2,…,9} such…Induction, recursion, and invariants
- Let n be a positive integerRecurrences, generating functions, and discrete asymptotics
- Four labs sharing ten hours cannot exceed a per-lab capCombinatorics and inclusion-exclusion
- BFS two-coloring is the certificate that no odd cycle existsGraphs, trees, connectivity, and matchings