Gödel Numbering

January 16, 2015

Gödel numbering is a system that assigns a natural number to each symbol and expression in a logical system, invented in 1931 by Kurt Gödel for the proofs of his incompleteness theorems. Consider the logical system where symbols are letters and expressions are words; for instance, the word PRAXIS consists of six symbols P, R, A, X, I, and S. Gödel numbering would assign numbers to the letters, say A=1 … Z=26, then assign each letter as the exponent of the next prime, so PRAXIS would be numbered 216 × 318 × 51 × 724 × 119 × 1319 =

83838469305478699942290773046821079668485703984645720358854000640

The process is reversible; factor the Gödel number and decode the exponents.

Your task is to write functions that encode strings as Gödel numbers and decode Gödel numbers as strings. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We have today our fourth essay: Building a Security Camera with a Raspberry Pi. An essay isn’t an exercise; it doesn’t present a task for you to perform, but instead provides extended discussion and complete source code. Though essays may be based on exercises, the idea is that an essay can delve more deeply into a topic than is possible in the limited space and time of an exercise.

My daughter recently had a thief enter her apartment and steal her laptop computer. Later, when I asked her what she wanted for Christmas, her answer was immediate: a security camera, so in case she is robbed again she will have pictures of the thief to give to the police. But commercial security cameras are expensive, often several hundred dollars, and many are tied to security services with expensive monthly fees, which she wasn’t interested in paying. So I built a security camera using a Raspberry Pi, and wrote this essay describing how I did it.

Please read the essay, and feel free to comment on it below; comments on the essay itself are closed. Let me know if you see any errors. And feel free to link to the essay on the internet if you know of places where it is appropriate.

One-Time Pad

January 9, 2015

In a previous exercise Ben Simon showed us how to use a trigraph for secret communication. For illustration, he used a one-time pad based on a simple random number generator, but that is not sufficient for proper cryptographic secrecy. In today’s exercise we build a secure one-time pad.

We need two things. One is a cryptographically-secure source of random bits. Solutions include counting the clicks of a geiger counter or reading the background radiation, but being a software guy rather than a hardware guy I suggest the Blum-Blum-Shub cryptographically-secure random number generator of a previous exercise. The second is a way to convert bits to letters. The method we choose is to take 26 consecutive bits from the Blub-Blub-Shum generator, form them into a number, and take the result mod 26, discarding the four largest numbers from the set in order to make all letters equally likely to be chosen, which is similar to the calculation of a previous exercise. Given those two things, it is easy to generate random letters and build a pad of any desired size.

Your task is to write a program to generate one-time pads. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Lucas-Carmichael Numbers

January 6, 2015

We start the new year with a simple task from number theory. A Lucas-Carmichael number is a positive composite integer n, odd and square-free, such that p + 1 divides n + 1 for all prime factors p of n. For instance, 2015 is a Lucas-Carmichael number because 2015 = 5 × 13 × 31 and 5 + 1 = 6, 13 + 1 = 14, and 31 + 2 = 32 all divide 2015 + 1 = 2016. The restriction that n be square-free prevents the cubes of prime numbers, such as 8 or 27, from being considered as Lucas-Carmichael numbers.

Your task is to write a program to find all the Lucas-Carmichael numbers less than a million. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Ancient Algorithms

December 23, 2014

[ Today’s exercise is a Christmas stocking stuffed with six little exercises. I wish all my readers a Merry Christmas and a Happy New Year! I’ll be taking a few days with family, so the next exercise will appear on January 6, 2015. ]

We tend to think of algorithms as procedures used by computers, but algorithms actually have a long and distinguished history. Today’s exercise discusses six algorithms that pre-date the Christian era, arranged roughly in chronological order. Despite their antiquity, all these algorithms are still in use today.

Peasant Multiplication: This algorithm has been independently invented by most societies as they progress to numeracy, so it is called the Egyptian method, the Ethiopian method, the Russian method, the Ukranian method, and so on for many different peoples; we simply call it the Peasant method. It is known that the Egyptians used this algorithm during the construction of the pyramids.

The algorithm starts by writing the two numbers to be multiplied at the heads of two columns. Then, on successive rows, the number in the left column is halved, discarding any remainder, and the number in the right column is doubled, until the left column is reduced to one. Then the sum of the numbers in the right column that correspond to odd numbers in the left column is the desired product. The ancients use pairs of pebbles to halve numbers and determine parity; we find it simpler to sum the odds as we go along.

function product(left, right)
    prod := 0
    while left > 0
        if left is odd
            prod := prod + right
        left := halve(left)
        right := double(right)
    return prod

In the United States we torment eight-year-old kids with the times tables, but school children in the rest of the world learn this method, which is simpler and, if you’ve ever taught third-grade math, more likely to be done correctly. Additionally, all computers do arithmetic in binary, and use this algorithm deep in the microcode that is stamped into the silicon chip that runs them, shifting bits to perform the halving and doubling operations. The only improvement is that computers nowadays process multiple bits at the same time, instead of just a single bit, reducing the number of steps in the loop.

Babylonian Square Roots: Mathematical historians know that the Babylonians invented a method of calculating square roots because a clay tablet with the calculations etched into it (ancient “scrap paper”) exists, but the method was first described by Hero of Alexandria in the first century after Christ. Hero (his name is sometimes spelled Heron) invented the jet engine (a hollow metal ball filled with water, heated over a fire to convert the water to steam, which exited by two nozzles on opposite sides of the globe; the rotational motion could be captured by gears or belts), the windmill (he used it to power a variety of machines, including a grain grinder), and the vending machine (you dropped a coin into a slot, which caused a balance beam to rise, opening a valve and filling a small vessel with holy water; when the vessel was full, it tipped to deliver the holy water, the coin was tipped into the safe, the balance beam fell, the valve closed, and the machine reset for the next purchase).

Hero observed that if x is an approximation of the square root of n, a better approximation is given by the average of x and n /x; we say x ′ = (x + n /x) / 2. The initial value of x can be anything on the range 1 ≤ xn, though the process converges more quickly if x is somewhat closer to n. In the version of the function given below, we bound n on the range 1 ≤ n < 4 so we can fix the number of iterations required for double-precision accuracy; an alternative is to iterate until the difference between two successive approximations is less than some desired epsilon.

function sqrt(n)
    if n < 1 return sqrt(n * 4) / 2
    if 4 <= n return sqrt(n / 4) * 2
    x = (n + 1) / 2
    repeat 5 times
        x = (x + n / x) / 2
    return x

The only improvement since the Babylonians is the initialization of x, which nowadays is done by some kind of black magic operating on the internal representation of the number (for integers, it’s generally one less than the number of bits in the binary representation of the number, for floating point it’s generally half the mantissa of the number with the exponent reduced by one), usually reducing the number of iterative steps to two or three.

Pythagorean Triples: Pythagoras, who lived about five centures before Christ, was a mathematician, philosopher and mystic. When he discovered that the square root of 2 could not be expressed as the ratio of two integers (we now say that it is irrational), he thought he had discovered some impossible flaw in the perfection of the World, and swore his followers to secrecy; legend tells us that one of his disciples, Hippasus, was murdered when he divulged the secret (another legend has it that Hippasus, not Pythagoras, who discovered the irrationality of the square root of 2).

Pythagoras proved that for any right triangle the square of the length of the hypotenuse is equal to the sum of the squares of the other two sides. He also discovered that given any coprime m and n, a primitive right triangle (all sides coprime to each other) has sides m2n2, 2mn, m2 + n2; for instance, with m = 2 and n = 1, the triangle is 22 − 12 = 2, 2 × 2 × 1 = 4, and 22 + 12 = 5.

function triple(m, n)
    return m*m - n*n, 2*m*n, m*m + n*n

An alternative method is to take any primitive Pythagorean triple {a, b, c} and generate three new primitive Pythagorean triples as {a-2b+2c, 2a-b+2c, 2a-2b+3c}, {a+2b+2c, 2a+b+2c, 2a+2b+3c}, {−a+2b+2c, −2a+2b+3c}; the process starts from {3, 4, 5}. Of course, non-primitive triples can be generated by multiplying all three elements of a primitive triple by some constant k.

Greatest Common Divisor: Euclid was either a Greek mathematician of the third century before Christ or, as some historians suggest, the conglomerate name of several mathematicians. Euclid wrote Elements, a textbook of geometry and number theory which has been in continuous publication since it was written, which is famous for its method of starting with five axioms and deriving all of geometry from them.

Euclid’s Elements, Book VII, Proposition 2, gives an algorithm for computing the greatest common divisor of two integers. Euclid’s algorithm works by repeatedly subtracting the smaller number from the larger, which reduces the magnitude of the numbers, thus guaranteeing termination of the algorithm, without affecting the greatest common divisor, since both the smaller number and the difference between the two numbers must be multiples of the greatest common divisor.

function gcd(m, n) # ancient
    if m < n return gcd(m, n-m)
    if n < m return gcd(m-n, n)
    return m
function gcd(m, n) # modern
    if n == 0 return m
    return gcd(n, m % n)

Euclid used repeated subtraction; nowadays we use modular arithmetic. Knuth calls this the “grand-daddy” of all algorithms, even though it isn’t the oldest, because it was the first to be written in rigorous form.

Approximation of Pi: Archimedes of Syracuse (on the island of Sicily) was a famous inventor of the third century before Christ: the screw pump, block-and-tackle pulley, odometer (it dropped a ball every time the wheel completed a turn), and numerous devices of war were among his inventions. He didn’t invent the lever, but was the first to explain how it worked, and he famously stated “Give me a lever and a place to stand, and I can move the world.” His most famous discovery was that objects float when they weigh less than the water they displace, which he used to prove that the king’s crown, thought to be pure gold, was actually an amalgam with silver; it is said that he discovered the principle while bathing, whereupon he ran naked through the street shouting “Eureka!”

The ratio of the circumference of a circle to its diameter is the mathematical constant known as π, which is approximately 3.141592654. Archimedes bounded the value of π in the range 223/71 < π < 22/7 by calculating the perimeters of two hexagons, one inscribed inside a circle and one circumscribing it, then successively doubling the number of sides of the inscribed and circumscribed regular polygons through the series 6, 12, 24, 48, and 96.

function pi(n) # archimedes used 6
    outer := 3 * sqrt(3)
    inner := outer / 2
    for i from 1 to n
        outer = 2 / (1/outer + 1/inner)
        inner = sqrt(outer * inner)
    return inner, outer

Archimedes’ approximation 22/7 is still frequently used today, but his method of computing the approximation has been replaced by a series expansion due to Srinivasa Ramanujan, or some similar series expansion, which converges in just a few steps; by contrast, Archimedes’ algorithm requires 27 steps for double-precision accuracy.

Prime Numbers: Eratosthenes, who measured the circumference of Earth, the distance from Earth to Sun, and the tilt of Earth’s axis, devised a system of latitude and longitude and was third chief librarian of the great library at Alexandria, succeeding Ptolemy and Apollonius, invented a method of enumerating prime numbers about 200BC; his writing has been lost, but we know of his invention through the writings of Nicomachus two centuries later.

The Sieve of Eratosthenes identifies primes by striking out multiples and keeping what’s left; the image is that composites fall through the sieve but primes remain. Initialize a list of numbers, from 2 to the desired limit n all marked as prime, then consider each number in turn; if it has not been marked as composite, report it as prime, then mark all its multiples as composite, starting from the square of the prime (since all smaller multiples will have already been marked composite by smaller primes).

function primes(n)
    sieve := makeArray(2..n, True)
    for p from 2 to n
        if sieve[p]
            output p
            for i from p*p to n step p
                sieve[i] = False

Modern mathematicians have optimized the basic Sieve of Eratosthenes shown above by eliminating the small primes that, because they have so many multiples, take most of the time; eliminating multiples of 2 is easy, and “wheels” can be used to eliminate multiples of 3, 5, 7, and so on, though increasingly large wheels quickly become cumbersome to operate. Still, an optimized Sieve of Eratosthenes is faster than any of its many modern alternatives.

Your task it to translate these seven programs into your favorite programming language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Diana Cryptosystem

December 19, 2014

[ Today’s exercise comes from the blog of long-time reader Ben Simon, after he declined my offer to guest-author the exercise and told me to steal it. The code and most of the text is his, so he gets the credit, not me. ]

It’s been a while since we had an exercise from our cryptography topic. Today’s exercise is the Diana Cryptosystem, also known as the trigraph cipher, which was used militarily by US forces during the Vietnam War and is theoretically unbreakable when used properly.

There are two pieces to the system: the trigraph itself, which is pictured at right, and a one-time pad, like this:

WHTVI AUCFU RETFK OMSAL
MYMNE ZIEGP UKVTF WZHOK
GORWY WETFR COYET OOWHY
ZPDDA CMMXT VYTJI RRQGU

To use the cipher, a section of the one-time pad is chosen and the two five-character groups that begin the section are transmitted unchanged. Thereafter, the key character is looked up on the trigraph, the next plaintext character is on the top row, and the corresponding ciphertext character is read off the bottom row. Decryption is the inverse operation. For instance, the message ATTACK AT DAWN is encoded like this, starting from the third group on the second row of the one-time pad:

UKVTF WZHOK GORWY WETFR COYET
            ATTAC KATDA WNXYZ
UKVTF WZHOK TSPDZ TVNRI BYEXH

Then UKVTF WZHOK TSPDZ TVNRI BYEXH is transmitted by Morse code. The recipient looks up the first two groups on the one-time pad then decrypts as follows:

UKVTF WZHOK GORWY WETFR COYET
UKVTF WZHOK TSPDZ TVNRI BYEXH
            ATTAC KATDA WNXYZ

The cipher is unbreakable without the one-time pad.

We said earlier that the cipher was used militarily. Ben points to this description of its use:

Special Forces were one of (if not the only) units in Vietnam to utilize Morse code on a regular basis. We used a method of encryption called the Diana Cryptosystem.

The basis of these “One-Time Pads”, is that there were only two matching pads in existence, and they would only be used one time. They were booklets that contained randomly generated groups of 5-letter “words;” 30 words to a page. The person sending a message would first write the letters to the message, over these random groups of words. Included in the front of each one-time pad was a one-page encryption table. If I wanted to send the letter “P”, and the letter under the “P” was an “A”, then I would send a “K”. The person listening on the frequency at the other end, would have the other matching pad. They would write the letter they received (a “K”) over the letter in their one-time pad (an “A”), and decipher it based on the table, yielding the original letter “P”.

Each communication site in Vietnam (we had over 100 A-Camps along the Cambodian / Laotian border, and some 20 B-detachment sites spread over the country) had a different pad, depending on the location they were having the commo-check with. It obviously was very important that both people were using the appropriate matching pads, or the deciphered messages would not make any sense.

After a while, most of us became so proficient with the system, that we actually learned the deciphering matrix by heart. No matter what pads anyone had, the combinations always were the same. i.e. Any 3 letters always went together, regardless of the order; “BKO”/”KOB”/”OBK”/”BOK”. After listening to thousands and thousands of transmissions, it really got quite simple. If I was listening to code, and a letter “B” was sent (now remember, we usually sent around 20-25 “words” (5 letters per word) a minute, hence the importance of the “speed” keys!), and the letter it was associated with was an “O”, most of us would decipher as we heard it, and just write the “K”. That may sound like quite a yarn, but it is absolutely true.

Your task is to write a program that implements the trigraph cipher. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Find Two Added Integers

December 16, 2014

I saw this question at a popular interview-question site and got mad at the suggested answer:

You are given two lists containing identical sets of integers except that the first list contains two additional integers not present in the second set. For instance, with a = {1 4 9 2 7 3} and b = {9 7 4 1}, the two additional integers are 2 and 3. Write a program to find the two additional integers.

Your task is to write the requested program. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Magic Squares

December 12, 2014

Magic squares are an arrangement of consecutive counting numbers starting from 1 into rows and columns in which every row, column and the two main diagonals all sum to the same number. Magic squares are an important element of recreational mathematics, and have been known since antiquity; this magic square of order 3, with magic sum 15, was published in China in 650BC:

4 9 2
3 5 7
8 1 6

That magic square was constructed by the “start bottom, move down and right, else up” rule: Starting from either of the center cells on the bottom row, enter a 1, then move to the next square diagonally down and right (wrapping around the sides of the square if necessary), then enter the next number in sequence, 2, and so on. However, if the next square is occupied, move instead to the next square up from the current square, then continue the sequence. Various rules like “start left, move down and right, else up” and “start top, move up and right, else down” also work, but rules like “start top, move down and left, else up” don’t; I’ll let you have the pleasure of figuring out which rules work and which don’t. This method works only for odd orders; there are other methods for even orders, which we may examine at some other time.

In the example square, the starting cell is the center cell on the bottom edge, where you see 1. Moving down and right and wrapping to the top of the next column, enter 2. Then moving down and right and wrapping to the left of the next row, enter 3. The next cell down and right already contains 1, so instead move up from the current cell and enter 4. Then moving down and right, enter 5. Then moving down and right, enter 6. The next cell down and right, wrapping both the row and column, already contains 4, so instead move up from the current cell and enter 7. Then moving down and right and wrapping to the left of the next row, enter 8. Finally, moving down and right and wrapping to the top of the next column, enter 9.

Your task is to write a program that takes an odd order n, one of the four starting cells and a rule and generates the indicated magic square. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Every Possible Fraction

December 9, 2014

When I saw this web page a few days ago, I knew it would make a great exercise, simple but fascinating. Starting with x = 1, every fraction in lowest terms is generated by x ′ = 1 / (ny + 1), where n = ⌊ x ⌋ and y = x − n. The underlying math is known as the Stern-Brocot tree, and has been known since the ancient Greeks, who used terms of the Stern-Brocot tree to design the gear ratios in the Antikythera mechanism.

Your task is to write a program that generates the fractions in lowest terms. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Free Time

December 5, 2014

We have a very practical task today: Given the set of busy-time intervals of two people, as in a calendar, find the free-time intervals of both people so they can arrange a meeting.

Your task is to write a program to find free time. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the
comments below.

Pages: 1 2

Follow

Get every new post delivered to your Inbox.

Join 655 other followers