Plain text -> Encipherment -> Transmission -> Decipherment -> Plain text Interception results in cryptanalysis (attempting to determine the = content without having the secure key used in encryption/decryption) 2 methods - Secret key - Public key ---------- SECRET KEY ---------- Note: Interception of the key itself results in failure Simple encipherment ------------------- A =3D 0, B =3D 1, C =3D 2, ... Z =3D 25 Working modulo 26 Shift cipher ------------ Perform a letter-shift before numbering A -> D =3D 3, B -> E =3D 4, ... Z -> C =3D 2 26 shifts (including the non-shift) Affine cipher ------------- Pick some a with 0 =B2=CAa =B2=CA25 and (a, 26) =3D 1 Pick some b with 0 =B2 b =B2=CA25 E(x) =3D ax + b (mod 26), where x is a letter's number (A =3D 0, B =3D = 1, etc.) To decode, pick some a* such that aa* congruent to 1 (mod 26), D(y) =3D = a*(y-b) There are 12*26 =3D 312 possible arrangements of a and b Substitution cipher ------------------- Permute the letters so that each letter has a shift to another Breaking the code is done via word rules (e.g. triplets have a vowel) There are 26! possible substitutions Vignere cipher -------------- Break text into blocks of length M Pick a word of length M Add, letter-by-letter, letter codes of the broken text and the added = word This way, frequency of use cannot determine the key There are 26^M possible additions ---------- PUBLIC KEY ---------- r[1], r[2], ... r[phi(m)] is a reduced residue system mod m, (k,phi(m)) = =3D 1 r[1]^k, r[2]^k, ... r[phi(m)]^k is also a reduced residue system If k*k congruent to 1 (mod m), then (r[i]^k)^k* congruent to r[i] (mod = m). Let p[1], p[2] be large primes (>100 digits), m =3D p[1]p[2] phi(m) =3D (p[1] - 1)(p[2] - 1) Choose k with 0 =B2=CAk =B2=CAphi(m) and k semi-close to phi(m) but = (k,phi(m)) =3D 1 Make m and k public but keep p[1] and p[2] secret Convert message to ASCII representation ('A' =3D 065, 'B' =3D 066, etc.) E(message) =3D (message)^k, receiver does D(message) =3D (message)^k* Example ------- Message: "HELP" m =3D 1109, p[1] =3D 101, p[2] =3D 109 phi(m) =3D 100*108 =3D 10800 k =3D 6311 k* obtained by Euclidean algorithm 10800 =3D 1*6311 + 4489 6311 =3D 1*4489 + 1822 4489 =3D 2*1822 + 845 1822 =3D 2*845 + 132 845 =3D 6*132 + 53 132 =3D 53*2 + 26 53 =3D 2*26 + 1 k* congruent to -409 (mod 10800), which is congruent to 10391 (mod = 10800) Cannot transmit in couplets as 2 ASCII numbers appended would be too = long HELP -> 072 069 076 080 -> 07573 08920 05374 00458= --Apple-Mail-2-980760688 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]7-20-04.txt" Content-Disposition: attachment; filename="[MA490]7-20-04.txt" Will proceed to ch.8, may go back to ch.7 if time allows 7-20 Read: p.221-226 HW: p.263 #1, 2, 4, 5, 6 7-21 Read: p.226-229 HW: p.264 #8, 9, 12, 14, 17 Final will be take-home (handed out on Friday 7-30 and due Tuesday 8-3) = --------------------------------------------------------------------------= ---- Diophantine equation - An equation of the form P(x[1], x[2], ... x[n]) =3D 0 with P a = polynomial in x[1], x[2], ... x[n] with integer coefficients - Pythagorean triplets yield a Diophantine equation (x^2 + y^2 - z^2 =3D= 0) - Definition: (x,y,z) is primitive if (x,y)=3D1, (y,z)=3D1, and = (x,z)=3D1 Theorem - x =3D st - y =3D (s^2 - t^2)/2 - z =3D (s^2 + t^2)/2 - s =B3=CAt =B3=CA1, s and t are odd integers, (s,t) =3D 1 - Therefore, (x,y,z) is primitive Alternatively, any primitive Pythagorean Triple with y even is of the = form: x =3D a^2 - b^2 y =3D 2ab z =3D a^2 + b^2 (a,b) =3D 1, a > b > 0, one of a and b is even (the other odd) Fermat's Last Theorem: If n=B33, x^n + y^n =3D z^n has no non-trivial = solutions= --Apple-Mail-2-980760688 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]7-21-04.txt" Content-Disposition: attachment; filename="[MA490]7-21-04.txt" Which positive integers can be represented as the sum of two squares? = =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D If m =3D a^2 + b^2, a^2 congruent to 0 or 1 (mod 4), b^2 congruent to 0 = or 1 (mod 4), so m congruent to 0, 1, or 2 (mod 4), meaning that m = cannot be the sum of two squares if it is congruent to 3 (mod 4). Theorem ------- Suppose q | m, with q congruent to 3 (mod 4). (i) If m =3D a^2 + b^2, q | a and q | b (ii) If m =3D a^2 + b^2, m =3D (q^2r)m' with integer r and q not = dividing m' Proof ----- (i) Suppose that q doesn't divide a. That means that (a,q) =3D 1, so = there exists some s such that sa congruent to 1 (mod q). q | m, so q | = (a^2 + b^2), so a^2 + b^2 congruent to 0 (mod q), meaning that (sa)^2 + = (sb)^2 congruent to 0 (mod q), or (sb)^2 congruent to -1 (mod q). This = means that q | a, which is a contradiction. Repeat the same with b. (ii) q | a, q | b, so q^2 | (a^2 + b^2), so q^2 | m. m[1] =3D m/q^2 =3D = (a/q)^2 + (b/q)^2. If (m[1],q) =3D 1, then we're done. If not, = iterate. Eventually, we get m/q^2r =3D (a/q^r)^2 + (b/q^r)^2, with q = not dividing m/q^2r. Theorem ------- If p is prime and p congruent to 1 (mod 4), then p can be represented as = the sum of two squares (p =3D a^2 + b^2). Proof ----- Since (-1\p) =3D 1, there is an s with s^2 congruent to -1 (mod p). = Consider the following set of ordered pairs (in curly braces to = distinguish between them and greatest common divisor), with 0 =B2=CAx,y = < =C3p. There are floor(=C3p) + 1 choices for x and y, so this = collection has (floor(=C3p)+1)^2 > p integers. So, there are ordered = pairs {x[1],y[1]}, {x[2],y[2]} such that sx[1]-y[1] congruent to = sx[2]-y[2] (mod p). Let X =3D x[1]-x[2], Y =3D y[1]-y[2]. sX-Y =3D = (sx[1]-y[1]) - (sx[2]-y[2]) congruent to 0 (mod p). So, sX congruent to = Y (mod p), or (s^2)X^2 congruent to Y^2 (mod p), meaning that X^2 + Y^2 = congruent to 0 (mod p). 0 =B2=CA|X| =B2 =C3p, 0 =B2=CA|Y| =B2=CA=C3p, = so we have 0 < X^2 + Y^2 < 2p and p | (X^2 + Y^2), so p =3D X^2 + Y^2. Lemma ----- If m and n can be represented as sums of two squares, then so can their = product (mn). Proof ----- m =3D a^2 + b^2, n =3D c^2 + d^2, mn =3D (ac + bd)^2 + (ad - bc)^2, so e = =3D ac + bd, f =3D ad - bc, mn =3D e^2 + f^2. Note: 2 =3D 1^2 + 1^2, so all powers of 2 are representable as a sum of = squares Theorem (either Fermat or Euler) -------------------------------- Let m > 0. m can then be represented as the sum of 2 squares if and = only if every odd prime q congruent to 3 (mod 4) with q | m appears in = the factorization of m with an even exponent. Proof ----- All odd primes dividing m that are congruent to 1 (mod 4) are writable = as the sum of two squares (from 2nd listed theorem here). All odd = primes dividing m that are congruent to 3 (mod 4) must have even powers = in order to themselves be sums of two squares. All even primes can be = represented as 2*q, where q is a prime, which can be handled above. m = is the product of all of its component primes, so if they all are sums = of squares then it must be a sum of squares. Note: If n =3D a^2 + b^2 for some a and b, we call this a = "representation" of n Let N(n) be the number of representations of n. 5 =3D 1^2 + 2^2 =3D = (-1)^2 + 2^2 =3D (-1)^2 + (-2)^2 =3D 1^2 + (-2)^2, plus reversed of each = (2^2 + 1^2, etc.). Therefore, N(5) =3D 8. 25 =3D (=B13)^2 + (=B14)^2 =3D= (=B14)^2 + (=B13)^2 =3D (0)^2 + (5)^2 =3D (5)^2 + (0)^2, so N(25) =3D = 12. Theorem (8.11) -------------- Suppose n =3D 2^a (=B9[i=3D1;r] p[i]^a[i])(=B9[j=3D1;r] q[j]^b[j]) with = all p[i] and q[j] distinct primes and all p[i] congruent to 1 (mod 4), = all q[j] congruent to 3 (mod 4). Then, N(n) =3D 4 =B9[i=3D1;r] (a[i] + = 1). Note: If p congruent to 1 (mod 4) is prime, then N(p^m) =3D 4(m+1). Lemma 1 ------- Let n=3D(q^2)m with q congruent to 3 (mod 4) a prime or q=3D2. Then, = N(n)=3DN(m). Proof ----- A representation n =3D x^2 + y^2 corresponds to a representation m =3D = X^2 + Y^2, with X =3D x/q, Y =3D y/q. Since they correspond, N(n) =3D = N(m). Lemma 2 ------- Let n =3D 2m with m odd. Then, N(n) =3D N(m). Proof ----- Again, by correspondance. x^2 + y^2 =3D m, then (x+y)^2 - (x-y)^2 =3D = 2m =3D n.= --Apple-Mail-2-980760688 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]7-22-04.txt" Content-Disposition: attachment; filename="[MA490]7-22-04.txt" Take-home exam, pick up next Friday (7-30-04), return on Tuesday = (8-3-04) p.264 #9 -------- Is 646^41 a sum of 2 squares? Theorem (from yesterday) states that n is the sum of squares iff it's of = the form 2^a =B9[i=3D0;r] p[i]^a[i] =B9[j=3D0;s] q[j]^2b[j] with all = p[i] congruent to 1 (mod 4) and all q[j] congruent to 3 (mod 4). 646 =3D = 2*17*19, 17 is congruent to 1 (mod 4), 19 is congruent to 3 (mod 4). = Since 19 will be raised to the 41st power (and not an even), 646^41 will = not be of the right form so it will not be a sum of 2 squares. MAPLE = can factor an integer quickly by the "ifactor(n);" function. = --------------------------------------------------------------------------= ---- Lemma 3 ------- Let n =3D p[1]^k[1] * p[2]^k[2] * ... p[r]^k[r] be any integer. Then, = the number of ordered pairs {x,y} such that (x,y) =3D 1 and xy =3D n is = 2^r. Proof ----- Once we know x, there is no choice for y. If xy =3D n and (x,y) =3D 1, = then for each i either p[i]^k[i] | x or p[i]^k[i] | y. There are r = choices made, each time for either x or y (but not both), so there are = 2^r possibilities. = --------------------------------------------------------------------------= ---- Definition: =BD(n) is the number of distinct primes dividing n Lemma 4 ------- Suppose that n > 0, d > 0, d^2 | n. The number of ordered pairs {x,y} = such that (x,y) =3D d and xy =3D n is 2^(=BD(n/d^2)). Proof ----- If (x,y) =3D d and xy =3D n, then (x/d,y/d) =3D 1 and (x/d)*(y/d) =3D = n/d. So, by Lemma 3, the number of such {x,y} is 2^(=BD(n/d^2)). Definition: =A0(n) is the total number of positive divisors for n. Corolary -------- =A0(n) =3D =B7[d^2|n] 2^(=BD(n/d^2)). Proof ----- If x | n, then x*y =3D n, y =3D n/x and (x,y) =3D d for some d (and d^2 = | n). So, summing over all d^2 | n, we get =A0(n). Lemma 5 ------- Suppose m =3D =B9[i=3D1;r] p[i]^a[i], p[i] congruent to 1 (mod 4). = Then, N(m) =3D 4 =B7[d^2|m] 2^(=BD(m/d^2)). Proof ----- Suppose d^2|m, m =3D x^2 + y^2, (x,y) =3D d. If X =3D x/d, Y =3D y/d, = then (X,Y) =3D 1 and X^2 + Y^2 =3D m/d^2. So, by Theorem 8.18, N(m) =3D = 4 =B7[d^2|m] 2^(=BD(m/d^2)) =3D 4=A0(m). Theorem 8.18 ------------ The number of {x,y} such that (x,y) =3D 1 are x^2 + y^2 =3D m is = 4*2^(=BD(m/d^2)). Proof ----- By Lemmas 1 and 2, N(m) =3D N(n) where n =3D =B9[i=3D1;r] p[i]^a[i]. By = Lemma 5, N(n) =3D 4=A0(n). x | n, then x =3D p[1]^c[1] p[2]^c[2] ... = p[r]^c[r] with 0 =B2=CAc[i] =B2=CAa[i]. For each i, there are a[i] + 1 = choices for each exponent c. Therefore, N(n) =3D 4 =B9[i=3D1;r] (a[i] + = 1). Definition: A representation is "positive" if a>0 and b>0 Definition: A positive representation is "primitive" if (a,b) =3D 1. Theorem ------- For every primitive representation there is a unique solution s of x^2 = congruent to -1 (mod n) such that sa congruent to b (mod n). = Furthermore, distinct representations correspond to distinct s. = Conversely, if s^2 congruent to -1 (mod n), there is a unique primitive = representation with sa congruent to b (mod n). Proof ----- Suppose that n =3D a^2 + b^2 with (a,b) =3D 1. Therefore, (a,n) =3D 1, = so there's a unique solution to sa congruent to b (mod n). a^2 + b^2 congruent to 0 (mod n) a^2 congruent to -b^2 (mod n) a^2 congruent to -(sa)^2 (mod n) a^2 congruent to -(s^2 * a^2) (mod n) s^2 congruent to -1 (mod n) Note that if t^2 congruent to -1 (mod n) and ta congruent to b (mod n), = then ta congruent to sa (mod n), or t congruent to s (mod n).= --Apple-Mail-2-980760688 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0644; name="[MA490]7-23-04.txt" Content-Disposition: attachment; filename="[MA490]7-23-04.txt" Theorem ------- A positive integer n has primitive representations iff 4 doesn't divide = n and q doesn't divide n for any prime q congruent to 3 (mod 4). Proof ----- If n has primitive representations, then x^2 congruent to -1 (mod n) is = solvable. If 4 | n, then x^2 congruent to -1 (mod n) is not solvable, = so it cannot be divisible by 4. Similarly, divisibility by q would = prevent the congruence from being solvable, so it can't be divisible by = q. Theorem ------- By restatement, let n>1 and S be the number of solutions to x^2 = congruent to -1 (mod n)... there are 4S primitive representations of n. Theorem 8.17 ------------ If n > 2, then n has an essentially unique primitive representation if = and only if n =3D 2^a p^m for a =3D 0 or 1 and p congruent to 1 (mod 4). Theorem 8.18 ------------ Suppose n has a primitive representation, n =3D 2^a p[1]^a[1] = p[2]^a[2]...., p[i] congruent to 1 (mod 4). Then n has 2^(r+2) = primitive representations and 2^(r-1) essentially distinct (including = order) positive primitive representations. Proof ----- x^2 congruent to -1 (mod n) has 2^r solutions since a =3D 0 or 1, so S =3D= 2^r, 4S =3D 2^(r+2), and (2^(r+2))/8 =3D 2^(r-1) essentially distinct = positive primitives. Theorem (sum of 4 squares) -------------------------- Every positive integer is the sum of 4 squares, though some of them may = be 0. Euler's Lemma ------------- If m and n are both representable as the sum of 4 squares, then so is = mn. Proof ----- m =3D a^2 + b^2 + c^2 + d^2, n =3D A^2 + B^2 + C^2 + D^2, mn =3D r^2 + = s^2 + t^2 + u^2 where r =3D aA + bB + cC =3D dD, s =3D aB - bA + cD - = dC, t =3D aC - bD - cA + dB, u =3D aD + bC - cB - dA. Therefore, it's = enough to show that all prime divisors of something are representable as = the sum of 4 squares. Sylvester's Lemma ----------------- Suppose that 3m is a sum of 4 squares. Then so is m. Lemma ----- If n is square free, then there exist integers a and b with a^2 + b^2 = congruent to -1 (mod n). Proof of Theorem ---------------- If n =3D k^2 m and m =3D r^2 + s^2 + t^2 + u^2, then = n=3D(kr)^2+(ks)^2+(kt)^2+(ku)^2, so we may assume that n is square free. = We know by Lemma 2 that a^2 + b^2 congruent to -1 (mod n). Consider = ordered pairs {as+bt-u,bs-at-v} for 0 =B2 s,t,u,v =B2=CA=C3n. There are = (1 + floor(=C3n))^4 such pairs and this is greater than n^2. Therefore, = there are two sets of s,t,u,v which are congruent (mod n), with the = difference between like terms labelled as s[0], t[0], u[0], v[0]. as[0] = + bt[0] congruent to u[0] (mod n), bs[0] - at[0] congruent to v[0] (mod = n). Thus, s[0]^2+t[0]^2+u[0]^2+v[0]^2 congruent to 0 (mod n). 1 = =B2=CAs[0]^2+t[0]^2+u[0]^2+v[0]^2 < 4n. If it's n we're done. If it's = 3n, Lemma 1 states that we're done. If it's 2n, either 0, 2, or 4 of = the terms are even. If it's 2, assume that s and t are even. Then, s=B1t= and u=B1v are both even, so we can divide through by 2.= --Apple-Mail-2-980760688--