# Coding Theory and Cryptography

This was once posted on my USNA webpage. Since I’ve retired, I’m going to repost it here.

Coding Theory and Cryptography:
From Enigma and Geheimschreiber to Quantum Theory

(David Joyner, ed.) Springer-Verlag, 2000.
ISBN 3-540-66336-3

Summary: These are the proceedings of the “Cryptoday” Conference on Coding Theory, Cryptography, and Number Theory held at the U. S. Naval Academy during October 25-26, 1998. This book concerns elementary and advanced aspects of coding theory and cryptography. The coding theory contributions deal mostly with algebraic coding theory. Some of these papers are expository, whereas others are the result of original research. The emphasis is on geometric Goppa codes, but there is also a paper on codes arising from combinatorial constructions. There are both, historical and mathematical papers on cryptography.
Several of the contributions on cryptography describe the work done by the British and their allies during World War II to crack the German and Japanese ciphers. Some mathematical aspects of the Enigma rotor machine and more recent research on quantum cryptography are described. Moreover, there are two papers concerned with the RSA cryptosystem and related number-theoretic issues.

Chapters

• Reminiscences and Reflections of a Codebreaker, by Peter Hilton pdf
• FISH and I, by W. T. Tutte pdf
• Sturgeon, The FISH BP Never Really Caught, by Frode Weierud, pdf
• ENIGMA and PURPLE: How the Allies Broke German and Japanese Codes During the War, by David A. Hatch pdf
• The Geheimschreiber Secret, by Lars Ulfving, Frode Weierud pdf
• The RSA Public Key Cryptosystem, by William P. Wardlaw pdf
• Number Theory and Cryptography (using Maple), by John Cosgrave pdf
• A Talk on Quantum Cryptography or How Alice Outwits Eve, by Samuel J. Lomonaco, Jr. pdf
• The Rigidity Theorems of Hamada and Ohmori, Revisited, by T. S. Michael pdf
• Counting Prime Divisors on Elliptic Curves and Multiplication in Finite Fields, by M. Amin Shokrollahi pdf,
• On Cyclic MDS-Codes, by M. Amin Shokrollahi pdf
• Computing Roots of Polynomials over Function Fields of Curves, by Shuhong Gao, M. Amin Shokrollahi pdf
• Remarks on codes from modular curves: MAPLE applications, by David Joyner and Salahoddin Shokranian, pdf

For more cryptologic history, see the National Cryptologic Museum.

This is now out of print and will not be reprinted (as far as I know). The above pdf files are posted by written permission. I thank Springer-Verlag for this.

# Problem of the week, 161

A former colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his US Naval Academy students, giving a prize of a cookie if they could solve it. One of them is given below.

The residue of an integer n modulo an integer d > 1 is the remainder r left when n is divided by d. That is, if n = dq + r for integers q and r with 0 < r < d, we write $r \equiv n \pmod d$ for the residue of n modulo d. Show that the residue modulo 7 of a (large) integer n can be found by separating the integer into 3-digit blocks $n = b(s)b(s-1)\dots b(1)$.(Note that b(s) may have 1, 2, or 3 digits, but every other block must have exactly three digits.) Then the residue modulo 7 of n is the same as the residue modulo 7 of $b(1) - b(2) + b(3) - b(4) + \dots \pm b(s)$. For example,
$n = 25,379,885,124,961,154,398,521,655 \pmod 7$
$\equiv 655 - 521 + 398 - 154 + 961 - 124 + 885 - 379 + 25 \pmod 7$ $\equiv 1746 \pmod 7$ $\equiv 746 - 1 \pmod 7$ $\equiv 745 \pmod 7 \equiv 3 \pmod 7$.
Explain why this works and show that the same trick works for residues modulo 13.

# Problem of the week, 137

A former colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his US Naval Academy students, giving a prize of a cookie if they could solve it. One of them is given below.

Chain addition is a technique employed in cryptography for extending a short sequence of digits, called the seed to a longer sequence of pseudorandom digits. Quoting David Kahn (in Kahn on Codes, MacMillan, New York, 1983, p. 154), “the first two digits of the [seed] are added together modulo 10 [which means they are added and the carry is neglected] and the result placed at the end of the [sequence], then the second and third digits are added and the sum placed at the end, and so forth, using also the newly generated digits when the [seed] is exhausted, until the desired length is obtained”. Thus, the seed 3964 yields the sequence 3964250675632195… .

Periodic pattern

a. Show that this sequence eventually repeats itself.
b. Show that the sequence begins repeating itself with “3964”.
c. EXTRA CREDIT: How many digits are there before the first repetition of “3964”?

# Problem of the week, 148

A former colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his US Naval Academy students, giving a prize of a cookie if they could solve it. One of them is given below.

Suppose p and q are each monic polynomials of degree 4 with real coefficients and the intersection of their graphs is {(1, 3), (5, 21)}. If p(3) – q(3) = 20, what is the area enclosed by their graphs?

# Problem of the week, 150

A former colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his US Naval Academy students, giving a prize of a cookie if they could solve it. One of them is given below.

Let a, b, and c be real numbers and let f and g be real valued functions of a real variable such that $\lim_{x\to a} g(x) = b$ and $\lim_{x\to b} f(x) = c$.
a. Give an example in which $\lim_{x\to a} f(g(x)) \not= c$.
b. Give an additional condition on f alone and show that it
guarantees $\lim_{x\to a} f(g(x)) = c$.
c. Give an additional condition on g alone and show that it
guarantees $\lim_{x\to a} f(g(x)) = c$.

# mathematics problem 155

A colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his students, giving a prize of a cookie if they could solve it. Here is one of them.

Mathematics Problem, #155

We can represent a triangle with sides of length a, b, c by the ordered triple (a, b, c). Changing the order of the sides doesn’t change the triangle, so (a, b, c), (b, a, c), (b, c, a), (c, b, a), (c, a, b), and (a, c, b) all represent the same triangle. To avoid confusion, let’s agree to write (a, b, c) with a < b < c. We say that a triangle <I (a, b, c) is integral if a, b, and c are integers. How many integral triangles are there with longest side less than or equal to 100 ?

# Mathematics Problem 154

A colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his students, giving a prize of a cookie if they could solve it. Here is one of them.

Mathematics Problem, #154

Find the volume of the intersection of three cylinders, each of radius a, which are centered on the x-axis, the y-axis, and the z-axis. That is, find the volume of the three dimensional region

E = {(x,y,z) | x2 + y2 < a2, y2 + z2 < a2, z2 + x2 < a2}.

# Mathematics Problem, #120

A colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his students, giving a prize of a cookie if they could solve it. Here is one of them.

Mathematics Problem, #120

A calculus 1 student Joe asks another student Bob “Is the following expression correct?” and writes

$f'(x^3)=3x^2$
on the blackboard. Bob replies, “Well, it could be, but I don’t think that is what you mean.”

Find a function that makes what Joe said correct.

Solution to #119:
There are $(16!)/(2^8)$ (about 82 billion) different orders that the spider can put on shoes and socks.

# Problem of the Week, #119

A colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his students, giving a prize of a cookie if they could solve it. Here is one of them.

## PROBLEM 119

A spider puts on $8$ identical socks and $8$ identical shoes (and of course the spider has $8$ feet). In how many different ways can the spider do this, given that on each foot, the sock has to go on before the shoe?

# Problem of the Week, #118

A colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his students, giving a prize of a cookie if they could solve it. Here is one of them.

## PROBLEM 118

Suppose that you draw numbers $x_1,x_2,\dots$ from $[0,1]$ randomly until $x_1+x_2+\dots +x_n$ first exceeds $1$. What is the probability that this happens on the fourth draw? That is, what is the probability that $x_1+x_2+x_3 < 1$ and $x_1+x_2+x_3+x_4 > 1$?

## PROBLEM 118A

In the above problem, what is the expected number of draws until the sum first exceeds $1$?