Explain a toy RSA round trip

Try

Use the distinct primes five and eleven to make modulus 55. Choose public exponent three and private exponent 27, since 3·27=81 is one modulo 40=(5−1)(11−1). A toy message seven becomes 7³=343, which reduces to 13 modulo 55. The claim is that raising 13 to exponent 27 recovers seven modulo 55. These deliberately small values teach the arithmetic; they provide no practical security.

Predict

Predict whether the proof requires the message to be coprime to 55. Euler’s theorem alone would impose that condition, but a CRT proof works for every residue, including messages divisible by five or eleven. This is an important example of changing the proof rather than silently adding a restriction to the advertised behavior. Exponents are positive integers, and the two prime factors must be distinct in this version.

Experiment

Compute the encryption by repeated squaring and inspect the retained residues.

Power	Exact residue modulo 55	Use
7¹	7	First binary digit
7²	49	Square
7³	13	Multiply 7·49 and reduce

For decryption, work separately modulo five and eleven: 13 is three modulo five and two modulo eleven. Since 27 is three modulo four, 3^27=3³=2 modulo five. Since 27 is seven modulo ten, 2^27=2^7=7 modulo eleven. The unique residue with these values is seven modulo 55.

Understand

In general let n=pq for distinct primes and choose positive e, d with ed=1 modulo lcm(p−1, q−1). Encryption followed by decryption produces m^(ed). Modulo p, if p divides m both sides are zero. Otherwise Fermat gives m^(p−1)=1, and ed=1+k(p−1) yields m^(ed)=m. The same reasoning holds modulo q. Since p and q are coprime, CRT proves equality modulo n. This proof handles all messages in the residue ring. To compute powers efficiently, maintain a result r, base b and remaining exponent k with r b^k congruent to the original target power. If k is odd multiply r by b and reduce, then subtract one from k. When k is even, square b and halve k. The invariant persists, and k eventually reaches zero.

Apply

The number of squaring stages grows with the binary length of the exponent rather than its value. That observation counts arithmetic operations; it is not a constant-time or side-channel security claim, and large-integer multiplication also has a cost. A paper implementation should test exponent zero, a zero message, a message sharing a prime factor, and ordinary units. Reduce after each multiplication to bound intermediate values, but use integer arithmetic capable of representing the products exactly. Floating-point rounding can invalidate a congruence even if the displayed final residue looks plausible.

Continue

Correctness is not secrecy. Factoring 55 is immediate, and even a large deterministic raw RSA map exposes repeated messages and preserves multiplicative relationships. Practical encryption requires standards, padding, randomness, carefully audited implementations and threat models outside this unit. Treat this as a proof and algorithm exercise, not a recipe for deploying cryptography. The next extensions examine primality certificates, modular square-root algorithms and other number-theoretic constructions with equally explicit distinctions between mathematical guarantees and computational evidence.

Return to the number theory unit to choose a targeted retry. Continue with distinguish primality proofs from probable-prime tests.