Math
RSA on small numbers
One message travels through two modular powers on a wood-and-brass desk. Execute the actual integer steps, inspect small permutations or large sampled maps, and find a divisor with a counted search.
What happens
One message travels through two modular powers on a wood-and-brass desk. Execute the actual integer steps, inspect small permutations or large sampled maps, and find a divisor with a counted search.
Wood and brass are an illustration, not a historical cipher machine. Right-drag rotates the workshop.
Textbook arithmetic on small integers. No OAEP/PSS encoding or secure message format. Trial division does not measure real RSA security.
Equations used in the module
Equations textbook key p = 61, q = 53: n = 3233, phi = (p−1)(q−1) = 3120, e = 17, d = e^(−1) mod phi = 2753, e·d mod phi = 1 65 -> 2790 -> 65 encryption is a PERMUTATION of Z_n for distinct primes p,q and gcd(e, phi) = 1: m -> m^e gives exactly n distinct images (3233 of 3233), and EVERY message comes back including the 113 messages that share a factor with n - that is the Chinese remainder theorem, NOT Euler's theorem, which says nothing about them messages that encrypt to themselves: exactly (1 + gcd(e−1, p−1))·(1 + gcd(e−1, q−1)) (61, 53, 17) -> 25; (11, 13, 7) -> 21; (17, 19, 5) -> 15; (31, 37, 11) -> 33; never fewer than four, and that is arithmetic, not a flaw trial-division counts until a factor is found (not the best known factoring attack): n = 3233 -> 52 plain, 16 over primes (through factor 53) n = 1022117 -> 1008 plain, 169 over primes (through factor 1009) sqrt(n) is only a reference scale for trial division; counts depend on the smallest factor. These counts do not measure real RSA security. Raw RSA is educational; real encryption/signatures use schemes such as OAEP/PSS. Teaching-key domain: distinct primes p,q; 3 <= e < n; gcd(e,phi(n)) = 1; 0 <= m,c < n. Out-of-range representatives are rejected, not silently reduced.
