CLASSICAL CRYPTOGRAPHY COURSE BY LANAKI June 12, 1996 Revision 0 COPYRIGHT 1996 ALL RIGHTS RESERVED LECTURE 14 LEDGE'S INTRODUCTION TO CRYPTARITHMS II SUMMARY It is my pleasure to present our guest lecturer LEDGE's (Dr. Gerhard D. Linz) second lecture on the interesting topic of Cryptarithms. In this lecture, he covers Multiplication, Multiplicative Structures, Base 11 and Base 12 calculations. LEDGE has a natural writing style, and a talent for making understandable some difficult concepts. LEDGE has already produced one of our better references on novice cryptography, and I appreciate his assistance in our course. Enjoy. [LEDG] UNIQUE SOLUTION Another Rule. Cryptarithms must meet another rule not stated in the first Lecture 8. There must be only one solution to the problem. That means that the solution must be unique. For ease in reading we will now use "mod" for "modulo. See the previous cryptarithm lecture for the meaning of the term. MULTIPLICATION Let's start our analysis of reconstructing multiplication problems by looking at a typical multiplication of whole numbers as we learned it in grammar school: 478 x52 --- 956 2390 ---- 24856 For convenience in talking about this problem, we need to introduce some nomenclature. The number being multiplied, here 478, is called the "multiplicand." The number by which the multiplicand is multiplied, here 52, is the "multiplier." The result of the multiplication, here 24856, is the "product." If we analyze the parts or steps of this process, we find we have two separate multiplications and one addition in what we usually consider a single multiplication problem. The problem contains substeps: 2 x 478 = 956; 5 x 478 = 2390 and an addition to which we will turn in a moment. Notice in the second multiplication of the multiplicand by a digit in the multiplier, instead of 5 x 478 we really have 50 x 478. We don't write it that way because we moved the product of 5 x 478 one decimal place to the left and left a blank space for the product of 0 x 478 (which equals 0). If the multiplier had more digits, we would have continued to move the subsequent partial products another space to the left. We have done multiplications like this so often that we don't usually recognize what we are doing. Now we can look at the addition: 956 2390 ----- 24856. OBSERVATIONS Each of these steps can give us different and valuable information. 1. The highest order digit of the multiplicand, multiplier, and product cannot be zero. In other words, by convention, no number starts with zero since no decimals are involved. If we had used letters in this example, the letters representing the 4 in 478, the 5 in 52, the 9 in 956, the 2 in 2390, and the 2 in 24856 could not represent 0. 2. The product of any sized multiplicand by a single digit multiplier can never contain more digits than the number of digits in the multiplicand plus one. If you need convincing, try it out with examples of your choice. In this case we have one such example: 5 x 478 = 2390. The multiplicand has three digits, the product four. 3. If a product has more digits than the multiplicand, the highest order digit of the product is less than or equal to the lower of the multiplier or the highest order digit of the multiplicand. Here, 5 x 478 = 2390. The highest order digit of the product is 2, smaller than the 4 of the multiplicand which in turn is smaller than the multiplier, 5. 4. The addition step is subject to the kinds of analyses we saw in the first lecture. When solving multiplication cryptarithms, you may want to write out the separate parts of the problem as CROTALUS has suggested. In this lecture we will use the understandings we have developed, but leave the problem intact. [CROT] The units digits of the products (the digit on the right end of each product) also can produce useful information which we will address later. Example 1. Now let's tackle an example that should not be too difficult. This one is a C-6 from the March-April, 1995, issue of The Cryptogram by DYETI. The key is two words (9-0). LARK xCAR ----- OOYRR ORLOA LEECC ------- LOSBRLR SOLUTION OF EXAMPLE 1 By now you should be able to see the various parts of the problem: three multiplications of the multiplicand by R, A, and C; and the addition of the three partial products, each one after the first shifted an additional space to the left to give the final product, LOSBRLR. Let's start with something familiar, the addition. We can notice that the leftmost digit of LEECC, the L, is carried to the final product without change; hence the sum of O and E, the next digits on the right, is less than 10 as there was no carry to the L. Finally, O + E + (0, 1 or 2) = O without a carry to the L. The (0, 1, or 2) are the possible carries from the previous addition of O + R + E plus a carry. But the only way for O + E = O mod 10 without a carry is for O + E = O not O + 10. As a result E = zero. Now let's take a look at the partial products. The products of C, A, and R times LARK is in no case LARK. Hence none of C, A, and R = 1. However, the product of R x K = R mod 10. The product of A x K = A mod 10, and the product of C times K = C mod 10. There is only one value of K that would make that true. K must = 1. Furthermore, there is no carry in any of those multiplications. That takes care of the information we can gather from the examination of the units digits. With a carry of 0 from the first multiplications, we can look similarly at the result of multiplying each of the digits in the multiplier by the tens digit of the multiplicand, the R: R x R = R mod 10 (the tens digit in the first partial product). A x R = O mod 10 and C x R = C mod 10. Looking at the first product, R x R, the only digits that give themselves as the units number of their products when multiplied by themselves are 0 x 0 = 0; 1 x 1 = 1; 5 x 5 = 25 or 5 mod 10; and 6 x 6 = 36 or 6 mod 10. We already know what letters represent 0 and 1 so R = 5, or 6. Both 5 and 6 are interesting numbers when considered from a multiplication standpoint. 5 x an even number = 0 mod 10. 5 x an odd number = 5 mod 10. Hence any product of 5 must end in either 5 or 0, two choices. Here we have three different products of R, not two. So R = 6. Let's take a look at the products of 6 mod 10 since we have the product C x R = C: 6 x 2 = 2; 6 x 4 = 4, 6 x 8 = 8, all mod 10. The general rule is that R must be even for 6 x R = R. Furthermore, since R is even, the product of R x n is even for any digit value of n. The only way to get an odd numbered product is to multiply two odd numbers. Try it out. So C = 2, 4, or 8. Can we narrow that down? It turns out that we can. Each of the partial products is 5 digits long, one more than the multiplicand. From fact 3 above, we know that the highest order digit in each case cannot be larger than the lower of the single digit multiplier and the highest order digit of the multiplicand. The highest order digits of the partial products are O, O, and L. Since L is the highest order digit of the multiplicand, C x LARK must yield the largest product. The highest possible value of C is 8. The next one is 4. Almost certainly C = 8. Let's put our number-letter equivalents into a table: 9 8 7 6 5 4 3 2 1 0 C R K E. We're supposed to find two words at the end of this process. The letters we have make a promising beginning. The product C x LARK = LEECC or, since we know many of the values of the letters, 8 x LA61 = L0088. Let's go through that multiplication step by step. 8 x 1 = 8, no carry. 8 x 6 = 48, carry the 4. 8 x A + 4 (the carry) must = 0 mod 10; so 8 x A must = 6 mod 10 since 6 + 4 = 0 mod 10. The products of 8 that end in 6 are 16 and 56; so A = 2 or 7. The addition section will give us the clue we need. At the tens digit of the addition R + A = L mod 10. We know R is 6. If A = 2, then R + A = 8, not possible since C = 8 already. So A = 7. R + A = 6 + 7 = 3 mod 10 or L = 3. Dividing the product LEECC or 30088 by 8 (C) gives 3761 for LARK. O could = 1 or 2, but only 2 is available (why?). Multiplying LARK x R will give us Y in the first partial product = 5. Only B has not been determined. By default it must be = 4. The key tableau is 9 8 7 6 5 4 3 2 1 0. S C A R Y B L O K E The final result : 3761 x876 ----- 22566 26327 30088 ------- 3294636 Example 2. Let's try another. If you feel brave, try it on your own before reading the explanation. It's not any more difficult than the first problem, only different. On the third page of Lecture I we presented this multiplication problem by APEX DX: OTTAWA xON ------ HNNTLIL IIIEHE ------- TOOINRL SOLUTION OF EXAMPLE 2 In Lecture 8, we determined that the only candidates for the representation of zero were L, W and R. We carried the solution no further at that point. We can do better than that with the tools we now have. The problem contains two partial products, N x OTTAWA = HNNTLIL and O x OTTAWA = IIIEHE, plus the addition of those products to give the final product. TOOINRL. We now note that the second partial product and the multiplicand have the same number of digits, six. Further, the highest order digit of the multiplicand and multiplier are the same, namely O. O x O + carry = I. The highest digit O can represent is 3 as 3 x 3 = 9. Any higher digit when multiplied by itself gives a two-digit result, adding a digit to that partial product. If O = 3, then I = 9. The partial product become 999EHE. Dividing by the multiplier value, 3 produces 333??? for OTTAWA. That cannot be since we have only one digit per letter. O also is not one, for multiplying any number by one results in that number. Therefore O must be = 2. 2 x 2 = 4 and the partial product would 444EHE. Again, dividing by 2 give 222???. As before I cannot equal T. Since 2 x 3 is 6 and I is less than that, I = 5, and the partial product is 555EHE. Dividing by O or 2, the multiplier, gives 277??? for OTTAWA; hence T = 7. In lecture I we were left with L, W, and R as the only possible candidate for the digit, 0. At that time we could not unambiguously select one of these as representing zero. We can now eliminate L from consideration. Look at the problem to see if you can spot how. L comes from the product of N x A mod 10. For L to be = zero, either N or A must be = 5. We have already determined that I = 5. Neither N or A are five, so L cannot be zero. We are left to choose between R and W. Our letter-number equivalent table now is: 0 1 2 3 4 5 6 7 8 9 O I T At the moment we can make no progress with the second partial product so let's examine the first, N x OTTAWA = HNNTLIL. Substituting the identified digits we have N x 277AWA = HNN7L5L. This product has seven digits, one more than OTTAWA. We have learned that the highest order digit of such a product must be less than or equal to the lower of the multiplier or the highest order digit of the multiplicand, i.e, O or N. Since O = 2, H can only = 1. We add that to the letter-number equivalent table. The partial product becomes N x 277AWA = 1NN7L5L. Dividing the product by OTTAWA or 277AWA, we learn that N could be 4,5, or 6. Since I = 5, N must be 4 or 6. Still working with the first partial product, N x A = L mod 10. A is multiplied by N again when we reach the hundreds digit of OTTAWA. Again the result is L mod 10. How could this be? It can only happen if there is no carry from the product of N x W. In the second partial product 2 x A = E mod 10 two times, as before. Thus 2 x W cannot have a carry here as well. Neither 4 x W, 6 x W, nor 2 x W > 9. W can only be 0 or 1. Because H = 1, W = 0. We could have gone another route. In the addition I + E = R. If R were = 0, since I = 5, E would have to be 5 also. That's not allowed, so R cannot be 0 and only W is left to = zero. Still a third way of determining whether R or W = zero is by anagraming. If R = zero, we look at the equivalent table and the keyword would have to start RHO, not impossible, but not encouraging. If W = zero, the keyword starts WHO, a word, very encouraging. Just like in K1 and K2 Aristocrats, reconstructing the equivalent table (instead of the equivalent alphabets) can give us useful clues. I generally use anagraming only as a last resort if I am otherwise stymied, however. With W = 0 we know that O x A = HE and N x A = IL. Replacing known letter values, we have 2 x A = 1E and N x A = 5L. The only products in the 50's produced by multiplying two single digit numbers are 54 and 56 or 9 x 6 or 7 x 8. Since T = 7, we cannot use N = 7 to yield N x A = 56; hence N and A are 9 and 6 and L = 4. We know that N is 4 or 6 (see above). So N = 6, A = 9, and, since 2 x 9 = 18, E = 8. The results are consistent; they produce no redundancies. The equivalent table becomes: 0 1 2 3 4 5 6 7 8 9 W H O L I N T E A. Only the R needs to be placed. What are the three words? Whorl in tea (Tempest in a teapot???). PROBLEMS IN BASES OTHER THAN TEN Our number system is based on the number 10, perhaps because normally humans have ten fingers and ten toes. So having ten for a base makes counting easier. We generally write our numbers as a series of digits with or without a decimal point, but we read the real value of a digit by its position in relation to the decimal point, either provided or tacitly understood. So we read 5,678 as five thousand, six hundred, seventy eight. Translating the English into number it becomes 5 x 1000 + 6 x100 + 7 x 10 + 8 x 1. That process is pure convention, but we don't usually think about it. Notice also that we have ten different characters for the ten different digits. When we count from zero up in whole numbers we use all ten (0-9) to get to 9 and then we move on to two digits, using a one in the tens place and starting anew with zero in the units place. It takes a lot of words to explain it, but we're so used it; we just spout the number and go on. Yet it is pure convention that we use ten as the base. We call it decimal, using the Greek word for ten. In fact we could use any whole number as the base except, of course, 0 alone as we can't count with it. Whatever number we use as a base, that's how many characters we need. If we were to want to count base 2 (like a series of switches that are either on or off), we'd need only the digits 0 and 1. That's called the binary system. Counting would go as follows: Base 2: 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 Base 10: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Notice that in binary 1101 = 1 x 8 + 1 x 4 + 0 x 2 + 1. In decimal we would read as 1 x 1000 + 1 x 100 + 0 x 10 + 1 x 1. Just as 1000 is 10x10x10, so 8 is 2 x 2 x 2. 100 is 10x10; 4 is 2 x 2. Binary 1000 translates to decimal 8, etc. Binary 1101 = Decimal 13. Naturally with only two symbols, binary representation of numbers are much longer than base 10 representations. We used base two as an illustration only. Cryptarithms, if not in decimal or base 10 form, use bases that are larger than ten, most often 11, called undecimal, or 12, called duodecimal. For undecimal we need to create a new character to replace decimal 10. Usually, "x" is used. Since we are using x as the multiplication symbol, we will use "t" for ten. We need another symbol for decimal 11. Usually, "e" is used. Counting in undecimal goes like this: 1, 2, 3, 4, 5, 6, 7, 8, 9, t, 10, 11, 12 etc. What we are used to reading as 10 is really 11 base 10. 11 is really 12 base 10, etc. In duodecimal counting proceeds 1, 2, 3, 4, 5, 6, 7, 8, 9, t, e, 10, 11, 12, etc. Looks are deceiving and you have to be careful. What looks like ten is read as 12, 11 is really decimal 13. If you have a number like 378 in duodecimal, think 3 x 12 x 12 + 7 x 12 + 8 or 3 x 144 + 7 x 12 + 8. If you wish, you can think three hundred seventy eight, but you must remember that in our ordinary notation 100 base 12 = 144 base 10 and 10 base 12 = 12 base 10. Arithmetical problems are solved as always, taking note of the different notation. If you find the following explanations which involve arithmetical manipulations in base 11 and 12 confusing, consult the multiplication and addition tables in the Appendix. [Tables 14-1 - 14-4] DUODECIMAL Now let's look at some duodecimal examples. Example 1. Addition 497 +876 ---- 1151. It looks odd, but it's duodecimal. 7 + 6 = 13. Divide by 12 and you get a quotient of 1 and a remainder of 1. Put down the remainder and carry the quotient of 1. 9 + 7 + 1 (carry) = 17. Divide by 12 giving a quotient of 1 and a remainder of 5. Put down the remainder of 5 and carry the quotient of 1. 8 + 4 + 1 (carry) = 13. Divide by 12 giving a quotient of 1 and a remainder of 1. Put down the remainder of 1 and, because the next column adds to 0 + 1 (the carried quotient), put down another 1. If we had an addition of 4 + 6 = ten, we would not divide by twelve but merely put down the ten as t. So in duodecimal 4 + 6 = t. Example 2. Subtraction. 67 -39 -- 2t. To subtract 9 from 7 we must borrow 12 from 6, making it 5. 12 + 7 - 9 = 10 or t. We put that down. 6 - 1(borrow) - 3 = 2. Hence the answer is 2t. Example 3. Multiplication. 67 x39 --- 4e3 179 ---- 2083 The process in words: 9 x 7 = 63, divide by 12 giving quotient of 5 and remainder of 3. Put down the 3 and carry the quotient of 5, just as in addition. 9 x 6 + 5(carry) = 59. Divide by 12 giving 4 as quotient and 11 or e as the remainder. Put down the remainder of e and, since there are no more digits to multiply by 9, put down the quotient of 4. Let's check this last one: 4 x 12 + 11 = 48 + 11 = 59. Work through the rest of this example on your own. Example 4. Division. 2e --- 17/48t 32 -- 16t 155 --- 15 First, we choose a trial quotient, here 2, and multiply the divisor, here 17, by it. 2 x 7 is 14, divide by 12 getting a remainder of 2 and a quotient of 1. Put down the 2 and carry the 1. 2 x 1 + 1(carry) = 3. Put it down. Bring down the next digit of the dividend, here t. Now go on your own and check out my work. Undecimal works the same way, except that instead of dividing by 12, we would divide by 11. If all that dividing and translating is too much to remember, use the proper multiplication table in the Appendix. Just as in the base 10 or decimal multiplication table the product of one digit by another is a one-digit or a two digit number, so it is in undecimal and duodecimal. In fact that's true of any base greater than 2. Be careful about reading and manipulating an undecimal or duodecimal number as a decimal number. The occasional t and e will remind you, but it's easy to forget momentarily, even after you've been at it for a while. MULTIPLICATIVE STRUCTURES FIRE-O in the May-June, 1970, issue of The Cryptogram introduced the concept of multiplicative structures [FIRE-O]. In 1977, in a two part article on base 11 and 12 arithmetic, I expanded on FIRE-O's work by extending the multiplicative structures to the higher bases [LEDG1] and [LEDG2]. The concept is simple, but often very useful. [FIRE] Let's take a digit, like 7, multiply it by 1 and then multiply it successively by the resulting product, i.e., when we multiply again we use the latest product. All the multiplications will be mod 10 as we are only interested in the units digit of the product. With using 7 we get: 1 x 7 = 7 7 x 7 = 9 9 x 7 = 3 3 x 7 = 1 Notice that the last product in the series in this case results in the multiplier we started with, 1. For 7 we have found a circular structure: (= 1 => 7 => 9 => 3 =). I am using the symbols =) and (= as indicators to return to the other end of the series. We could also diagram it as: 1 => 7 ^ | | V 3 <= 9. You can read the series as 1 to 7 to 9 to 3 to 1 to 7 etc. Because of the lack of printable characters in ASCII, I'll be using the first kind of diagram. Notice that all the digits in the diagram are odd. We can start another diagram by starting with an even number, say 2. 2 x 7 = 4 4 x 7 = 8 8 x 7 = 6 6 x 7 = 2 or (= 2 => 4 => 8 => 6 =). That leaves 5 x 7 = 5 or 5 <=, and 0 x 7 = 0 or 0 <=. In other words, multiplying 7 by 5 or 0 gives the multiplier as the units digit of the product. The last is true for any odd number. As we will see shortly, 3 diagrams out in a similar fashion to 7, two circles, one of odd numbers and one of even ones. If n is odd, then 5 x n => 5. Diagram: 5 <=. If n is even, then 5 x n => 0. Diagram 5 => 0 <= In both cases, 0 x n => 0 and 0 x 0 => 0. Diagram 0 <=. Now let's look at the other diagrams. BASE 10. O: n x 0 <= 1: n x 1 => n <=. In other words, successive multiplications by 1 always yield n. 2: 1 7 9 3 2 X 2 = 4 4 X 2 = 8 etc. | | | | 1 x 2 = 2 7 x 2 = 4 etc. V V V V and 5 => 0 <=. (= 2 => 4 => 8 => 6 =) 3. (= 1 => 3 => 9 => 7 =) 5 <= and 0 <= (= 2 => 6 => 8 => 4 =) 4. 1 => 4 <==> 6 <= 9; 3 => 2 <==> 8 <= 7; 5 => 0 <= 5. odd x 5 <=; even x 5 => 0 <= 6. 1 => 6 <=; 3 => 8 <=; 5 => 0 <=; 7 => 2 <=; 9 => 4 <=. 7. (= 1 => 7 => 9 => 3 =) 5 <= and 0 <= (= 2 => 4 => 8 => 6 =) 8. 1 3 9 7 5 => 0 <= | | | | V V V V (= 8 => 4 => 2 => 6 =) 9. 1 <==> 9; 2 <==> 8; 3 <==> 7; 4 <==> 6 5<= 0 <=. Remember that in each case, each resulting product (mod 10) is multiplied by the original multiplier given at the beginning of each set, e.g., " 6.". BASE 11 (UNDECIMAL) 0. n x 0 => 0 <= 1. n x 1 => n <= 2. (= 1 => 2 => 4 => 8 => 5 => t => 9 => 7 => 3 => 6 =) 0 <= 3. (= 1 => 3 => 9 => 5 => 4 =); (= 2 => 6 => 7 => t => 8 =); 0 <= 4. (= 1 => 4 => 5 => 9 => 3 =); (= 2 => 8 => t => 7 => 6 =); 0 <= 5. (= 1 => 5 => 3 => 4 => 9 = ; (= 2 => t => 6 => 8 => 7 =); 0 <= 6. (= 1 => 6 => 3 => 7 => 9 => t => 5 => 8 => 4 => 2=); 0 <= 7. (= 1 => 7 => 5 => 2 => 3 => t => 4 => 6 => 9 => 8 =); 0 <= 8. (= 1 => 8 => 9 => 6 => 4 => t => 3 => 2 => 5 => 7 =); 0 <= 9. (= 1 => 9 => 4 => 3 => 5 =); (= 2 => 7 => 8 => 6 => t =); 0 <= t. 1 <==> t; 2 <==> 9; 3 <==> 8; 4 <==> 7; 5 <==> 6; 0 <= BASE 12 (DUODECIMAL) 0. n x 0 => 0 <= 1. n x 1 => n <= 2. 1,7 => 2 => 4 (==> 8 <= t <= 5,e; 3,9 => 6 => 0 <= 3. 1,5 => 3 <==> 9 <= 7,e; 2,t => 6 <=; 4,8 => 0 <= 4. 1,7,t => 4 <=; 2,5,e => 8 <=; 3,6,9 => 0 <= 5. 1 <==> 5; 2 <==> t; 4 <==> 8; 7 <==> e; 3,6,9 0 <= 6. 1,3,5,7,9,e, => 6 => 0 <= 0,2,4,8,t 7. 1 <==> 7; 3 <==> 9; 5 <==> e; 0 <=; 2<=; 4 <=; 6 <=; 8 <=; t <=; 8. 1,7,t => 8 <==> 4 <= 2,5,e; 3,6,9 => 0 <= 9. 1,5 => 9 <=; 2,7 => 6 <=; 7,e => 3 <=; 4,8 => 0 <=; t. 1,7 => t => 4 <=; 5,e => 2 => 8 <=; 3,9 => 6 => 0 <=; e 1 <==> e; 2 <==> t; 3 <==> 9; 4 <==> 8; 5 <==> 7; 6 <=; 0 <= Notes: 1) In each system 1 x n = n and 0 x n = 0. 2) In each system the two digits involved in each structure for the highest digit (base - 1) add up to the base. Another way to look at that is to realize that the digits in the product of n x (base - 1) add up to base - 1. Thus, in decimal 8 x 9 = 72 and 7 + 2 = 9 (10 - 1). In undecimal, 6 x t = 55 and 5 + 5 = t. Finally, in duodecimal, 9 x e = 83 and 8 + 3 = e. 3) The structure for 5 (which = base/2) in decimal has the same form as for 6 (which also = base/2) in duodecimal. Undecimal, being odd, has no equivalent for 5 and six. DUODECIMAL MULTIPLICATION EXAMPLE To begin to put some of these findings together, let's tackle a duodecimal multiplication example. In the process we will discover the usefulness of the multiplicative structures for at least some of the more difficult or complicated mult- plication problems and, by extension, division problems as well. You remember that division problems have one or more partial multiplications in them. Here's the problem: It's by MORDASHKA and appeared as C-11 in the November-December, 1994, issue of The Cryptogram. YOUR TAB ---- IYATR UOYLN PYPRR ------- YCRORTR The problem contains three partial products and one addition with three addends shifted as per usual for multiplication. It could be helpful if we can locate zero. We could use a process of elimination. Neither Y, T, A, B, I, U, P, nor R can be zero. That leaves four letters as possibilities: C, O, N, and L. Fortunately for us, in the addition section we find T + N = T. Hence N = zero. Also from the addition section at the left end, Y > P. U + Y must be greater than e, giving a carry of 1, so Y = P + 1. That should be useful later. Again from the addition section, A + L + R = R mod 12. There is no carry from the previous column: T + N as N = 0. We can subtract R from both sides of the first equation giving us A + L = 0 mod 12. But A and L are both greater than 0 so A + L = 10 or decimal 12. That means if we can determine the value of A, we can compute the value of L from the equation, and vice versa. >From the partial products, all of which are 5 digits long whereas the multiplicand is 4 digits long, Y > I, U, P > 0. Therefore Y must more than 3. Now let's look at the partial products to see whether we can uncover a recognizable multiplicative structure, remembering that we are dealing with a duodecimal or base 12 problem. We get these equations from the product of the last digit of the multiplicand by each digit of the multiplier: R x B = R R x A = N or zero R x T = R all mod 12 The multiplicative structure becomes: B,T => R and A => zero. There are only two places that yield the appropriate relations, when R = 4 or R = 8. Since none of R, B, and T equal 1 and R does not equal zero, here are the results: R = 4 then B and T are 7 and t or t and 7. A = 3, 6, or 9. R = 8 then B and T are two of 7, t, and 4. A = 3, 6, or 9. That's not very many possibilities, simplifying our search. The first partial product ends with TR. The third ends with RR. If we identify T and B, we should be able to calculate U in the multiplicand and check it in both partial multiplications. So here's our table: B T R U 7 t 4 t 7 4 7 t 8 t 7 8 4 t 8 t 4 8 Those are the only possible values of B, T, and R, all the permutations. In each instance we have to calculate U to discover what value of U is consistent in both multiplications. Now let's check these possibilities. B x YOUR = IYATR. 1) B = 7, T = t, R = 4, TR = t4. B x R = 7 x 4 = 28 base 10 or 24 base 12. Carry the 2. B x U + 2 => T or t. 7 x U + 2 => 4, U = 8. Check: 7 x 8 + 2 = 58 base 10 or 4t base 12 or t mod 12. Our trial value for U is 8. Let's check that with the third partial product T x YOUR = PYPRR. T = t etc. as before. RR = 44. t x 4 = 40 base 10 or 34 base 12. Carry the 3. t x 8 + 3 = 83 base 10 or 6e base 12 or e mod 12, but we needed a 4 for 44. It doesn't work. 2) We have to continue the process until we get a combination that is consistent. Try the second one. You may find that no value of U can be found from the first partial. Similar problems beset the next three combinations on the table. 3) Let's check the 5th combination. B = 4, T = t, R = 8, TR = t8. B x R = 4 x 8 = 32 base 10 or 28 base 12 or 8 mod 12. Carry the 2. B x U + 2 = t mod 12. 4 x U + 2 = t. U could be 2 or 5. Try them with the second product. RR = 88. T or t x 8 = 80 base 10 or 68 base 12 or 8 mod 12. Carry 6. For U = 2, t x 2 + 6 = 26 base 10 or 22 base 12 or 2 mod 12. But we need an 8 for 88. That's a conflict. Let's try U = 5. t x 5 + 6 = 56 base 10 or 48 base 12 or 8 mod 12. Eureka! U = 5 checks out. We now also know that B = 4, T = t and R = 8. You can check the last combination also to make sure it produces no alternate value of U that stays consistent. The letter-number equivalent table is 0 e t 9 8 7 6 5 4 3 2 1 N T R U B We can now determine the value of A using fact 4) A + L = 12 with the middle partial product. A x YOUR = UOYLN or A x ..58 = (12 - A)0. A can have the value of 3, 6 or 9. If A is 6, then L = 6 (A + L = 12, remember?). That's not possible. If A = 3 L = 9. If A = 9, L = 3. Try 3. 3 x 8 = 24 base 10 or 20 base 12. Carry the 2. 3 x 5 + 2 = 17 base 10 or 15 base 12 or 5 mod 12. But we needed a 9. Try A = 9. It better work or we've done something wrong. 9 x 8 = 72 base 10 or 60 base 12. Carry the 6. 9 x 5 + 6 = 51 base 10 or 43 base 12 or 3 mod 12. So L = 3. That's the value of L we were looking for. Success! We can add that to the equivalent table. With A = 9 and T = t, T x YOUR = A x YOUR + YOUR. Since we know that T x YOUR = PYPRR and A x YOUR = UOYLN, we can put the addition into normal form: UOYLN +YOUR ----- PYPRR >From this addition we deduce that P = U + 1 or 5 + 1 = 6. Looking at the multiplier, TAB = t93. The first product must be the smallest, followed by the second, with the third the largest. Their leftmost digits must be in the same order. Hence, I < U < P < Y.or Y > P > U > I. The only letters about which we have no information yet are C and O. At this point our equivalent table reads: 0 e t 9 8 7 6 5 4 3 2 1 N T A R U B L Replacing letters of known value in the above addition by their respective digits yields 5OY30 +YO58 ----- PYP88 We note that Y + O = P and O + Y = Y. 3 + 5 = 8, no carry. Y + O must yield a carry of 1 which makes Y = P + 1. Since I < U, the only place in the table for two numbers that are adjacent in value is 7 and 6; thus Y = 7 and P = 6. Y + O = P mod 12. That means 7 + O = 16 base 12 or 18 base 10. Thus, O = e. The addition of all three partial products will give us the remaining values for I and C without resorting to anagraming. (Just a nicety here.) I79t8 5e730 +67688 -------- 7C8et8 9 + 3 + 8 = 18 base 12. Carry 1. 7 + 7 + 8 + 1 = 1e base 12. Carry 1. I + e + 6 + 1 = 8 or 18 base 12. Solving for I gives I = 2. Carry 1. 5 + 7 + 1 = 11 base 12. Thus C = 1. The keyphrase for the equivalent table becomes NOTARYPUBLIC. Although this problem was given the number C-11, for someone familiar with duodecimal arithmetic it is of medium difficulty. There are problems in the Cryptarithm section that provide far fewer clues and necessitate trying out many more possibilities. In the next lecture we will take a look at organizing that process so as not to get lost in the bookkeeping aspect of finding a solution. We may also find a few more relationships that can be helpful at times. REFERENCES [CROT] Winter, Jack (CROTALUS), "Solving Cryptarithms," American Cryptogram Association, 1984. [FIDD] FIDDLE, Lynch, Frederick D., "An Approach to Cryptarithms," ACA Publications, 1974. [FIRE] FIRE-O, "A Tool for Mathematicians: Multiplicative Structures," The Cryptogram, Volume XXXVI, No 3, 1970. [LED1] LEDGE, "Basic Patterns in Base Eleven and Twelve Arithmetic (Part 1)," The Cryptogram, Volume XLIII, No 5, 1977. [LED2] LEDGE, "Basic Patterns in Base Eleven and Twelve Arithmetic (Part 2)," The Cryptogram, Volume XLIII, No 6, 1977. APPENDIX Table 14-1 Undecimal Multiplication Table 1 2 3 4 5 6 7 8 9 t 1 | 1 2 3 4 5 6 7 8 9 t 2 | 2 4 6 8 t 11 13 15 17 19 3 | 3 6 9 11 14 17 1t 22 25 28 4 | 4 8 11 15 19 22 26 2t 33 37 5 | 5 t 14 19 23 28 32 37 41 46 6 | 6 11 17 22 28 33 39 44 4t 55 7 | 7 13 1x 26 32 39 45 51 58 64 8 | 8 15 22 2x 37 44 51 59 66 73 9 | 9 18 25 33 41 4t 58 66 74 82 t | t 19 28 37 46 55 64 73 82 91 Table 14-2 Duodecimal Multiplication Table 1 2 3 4 5 6 7 8 9 t e 1 | 1 2 3 4 5 6 7 8 9 t e 2 | 2 4 6 8 t 10 12 14 16 18 1t 3 | 3 6 9 10 13 16 19 20 23 26 29 4 | 4 8 10 14 18 20 24 28 30 34 38 5 | 5 t 13 18 21 26 2e 34 39 42 47 6 | 6 10 16 20 26 30 36 40 42 50 56 7 | 7 12 19 24 2e 36 41 48 53 5x 65 8 | 8 14 20 38 34 40 48 54 60 68 74 9 | 0 16 23 30 39 46 53 60 69 76 83 t | t 18 26 34 42 50 5x 68 76 84 92 e | e 1t 29 38 47 56 65 74 83 92 t1 Table 14-3 Undecimal Addition Table 1 2 3 4 5 6 7 8 9 t 1 | 2 3 4 5 6 7 8 9 t 10 2 | 3 4 5 6 7 8 9 t 10 11 3 | 4 5 6 7 8 9 t 10 11 12 4 | 5 6 7 8 9 t 10 11 12 13 5 | 6 7 8 9 t 10 11 12 13 14 6 | 7 8 9 t 10 11 12 13 14 15 7 | 8 9 t 10 11 12 13 14 15 16 8 | 9 t 10 11 12 13 14 15 16 17 9 | t 10 11 12 13 14 15 16 17 18 t |10 11 12 13 14 15 16 17 18 19 Table 14-4 Duodecimal Addition Table 1 2 3 4 5 6 7 8 9 t e 1 | 2 3 4 5 6 7 8 9 t e 10 2 | 3 4 5 6 7 8 9 t e 10 11 3 | 4 5 6 7 8 9 t e 10 11 12 4 | 5 6 7 8 9 t e 10 11 12 13 5 | 6 7 8 9 t e 10 11 12 13 14 6 | 7 8 9 t e 10 11 12 13 14 15 7 | 8 9 t e 10 11 12 13 14 15 16 8 | 9 t e 10 11 12 13 14 15 16 17 9 | t e 10 11 12 13 14 15 16 17 18 t | e 10 11 12 13 14 15 16 17 18 19 e |10 11 12 13 14 15 16 17 18 19 1t LECTURE 13 SOLUTIONS 13-1 Beaufort ABRVJ UTAMP YPLHZ OZYAP YPJNP KNXUG QRDPC ELPNC BVCEF NLLSJ LGOWC VYCGA EVGIX XNDKY U. (butter) (INWVQH) Key = AGRICULTURE, A fantastic glut ... 13-2 Vigenere. DWNIT KGEWZ ENJQZ WXLLZ WZOKC ETOWI NXVQS DQGAK MGGBH NAMWE OWVAM UJDVQ IMDSB VCCTR YUIQX. (making, UHVW) Key = LIBERTY, Some criminals in .... 13-3 Vigenere Running Key YPOSC DWVWY CCHZT AKALF I. (tolls -2) Key = Never send for whom the be (continues bell tolls ) 13-4 Vigenere Progressive key. "Fungi" IPGPUPX GTIAKNP AMEHLAW SJSTROZ TCGYUND STNPJZM OESWAXG VLHSPZC GNEIWHP EKHNOWW PMEQFVV PDQAWCA GGFRKSO RCHZVKL NBWHYBV CUNBBBB AVGCJFA FLTMKUV K. Key = PICTURE (3), The way to identify.... LECTURE 14 PROBLEMS Some time ago, CROTALUS cooked up some goodies: 14-1. Multiplication (Two words, 0-1) original by EDNASANDE WOMEN X MEN = UTNNLM + NWTWNN = NLSMTUWM 14-2. Division (Two words, 0 -9) MORDASHKA ATOM / ASK = N; - GNC = IS 14-3. Multiplication. (No word, 0-1) FOMALHAUT ASAP X MAB = RITMT + TMPRY + PDBYD =PAYDIRT 14-4. Unidecimal multiplication. (Two words 0-X) WALRUS TOUGH X DIG = IDIGDN + NYYDNG + UIHDOU = DDCUUILN