commit 3e883defb0f3dc4b70804ad8522d31e1349230be
parent 366d50d1b96c53baebf425aa76bc5a955db3cc1a
Author: Jared Tobin <jared@jtobin.io>
Date: Sat, 19 Aug 2023 18:44:54 -0230
Fix typos.
Diffstat:
1 file changed, 6 insertions(+), 5 deletions(-)
diff --git a/docs/s5.md b/docs/s5.md
@@ -367,8 +367,9 @@ In any case, RSA: one finds two n-bit primes, 'p' and 'q', and uses
their product to construct a modulus N = (p - 1) (q - 1). The public
key is (N, e) for 'e' a number relatively prime to that modulus, and
the private key is (N, d), for d such that ed = 1 mod N (i.e., 'd' is
-congruent mod N to the inverse of e). "Relatively prime" means, for two
-numbers 'a' and 'b', that they have a greatest common denominator of 1.
+congruent mod N to the inverse of e). "Relatively prime" or "coprime"
+means, for two numbers 'a' and 'b', that they have a greatest common
+denominator of 1.
Encryption and decryption are then just modular exponentiation
operations using the keys. To go from Natural to ByteString and back,
@@ -418,7 +419,7 @@ functions, as well as invmod and roll & unroll.
#### 5.40
The problem behind the Chinese Remainder Theorem, as formulated by one
-孫子 and passed on to me via Wikipedia, is:
+孫子 (not *that* 孫子) and passed on to me via Wikipedia, is:
> There are certain things whose number is unknown. If we count them by
> threes, we have two left over; by fives, we have three left over; and
@@ -431,8 +432,8 @@ Remainder Theorem states that such a solution always exists given
certain conditions (notably that the moduli are pairwise coprime).
In our case, for plaintext 'm' and ciphertexts c0, c1, and c2, we have
-that m ^ 3 is congruent modulo to c0 mod n0, c1 mod n1, and c2 mod n2.
-The Chinese Remainder Theorem asserts that there exists some 'c' that is
+that m ^ 3 is congruent to c0 mod n0, c1 mod n1, and c2 mod n2. The
+Chinese Remainder Theorem asserts that there exists some 'c' that is
congruent to m ^ 3 modulo `n0 * n1 * n2`. The trick here (this is known
as Håstad's attack, apparently) is that since m is smaller than every n,
we have that m ^ 3 is smaller than `n0 * n1 * n2`, and so that 'c' is
