# Applied Algebra

Homework solutions not on the TA's course page:

Errata for the text by Childs.

Complex demos:

### Factorization of an integer into primes

(requires Java installed and enabled)
n =

### Power calculator

b = , n = , m = => bn (mod m)

### Daily notes

I'll put course announcements here rather than in Virtual Office Hours. Please check here frequently during the quarter, clicking on Reload to make sure you see a current copy of this page.
• 6/8/04 Office hours previously announced for Thursday, June 10 have been changed; they will be 11:00-11:30 and 12:00-12:30. Sorry for the late notice; I was asked to attend a meeting.
• 6/8/04 Solutions to the non-text homework problems of Assignment 7 are linked above. If you notice any errata, please let me know.
• 5/27/04 One of you points out that in Problem M-7 part (c), the integer given is not the product of two primes as it is supposed to be. So do only parts (a) and (b) this week; I'll put a different version of (c) for next week.
• 5/26/04 On p. L 3, in Step 2(a) the rows were supposed to be rotated by different amounts. (This part was not relevant for homework.)
• 5/26/04 In Rijndael, the bits are numbered so that a7 is the coefficient of α7, and so on. So when you see a0, a1,...,a7 as a column vector, the bits are in the opposite order from when they are listed in a byte. Then after you do the matrix multiplication and get a column vector out, you need to put its bits back in the correct order for the byte.

For finding the inverse, people are having trouble interpreting the suggestion. Just take the equation α8 = α4 + α3 + ... + 1, multiply through by α-1, to get α7 = α3 + α2 + ... + α-1, and then solve for α-1, remembering that in the two-element field -1 = 1 so minus an expression is the same as plus the expression. (Of course, α is just one element of the field and this method of inverting applies only to α itself.)

• 5/24/04 Erratum: p. L3, Step 1(a): should say simply "mapped to its inverse".
• 5/23/04 Office hours this week (May 24-28): Monday, May 24, 11:00-12:00; Wednesday 11:00-12:00 as usual; Thursday 1:30-2:00 (and I can't be available informally after discussion section).
• 5/21/04 I said Assignment #7 will be due in ten days, but I forgot that that's a holiday (Memorial Day)--so I'll give a shorter assignment due this coming Friday. If you're working over this weekend then you can read the Rijndael handout. (If you don't have it, see the on-line version.)
• 5/20/04 p. 206, Ex. 1 is listed as both to hand in and as not to hand in. Let's say you don't need to hand it in. Do try it, though.
• 5/20/04 In Problem H-3(b), stick to the cases where a a unit or is divisible by m.
• 5/20/04 In Problem H-4, it should say generators rather than units .
• 5/18/04 In Problem H-6, (iii)-(b): should say Z 151 .
• 5/18/04 In Problem I-3, if you want to use a group of three people or more, you can send messages cyclically, e.g., A to B to C to A. Each two would need to establish a shared secret key.
• 5/18/04 Also in Problem I-3, please hand in a record of the numbers you calculated or observed.
• 5/17/04 In Problem I-3, in the table that says A is 1, etc., of course that should be expanded to two digits, so A is 01, B is 02, etc.
• 5/13/04 For problem 2(a) on the midterm, if you didn't give a reason for your answer and I asked you to supply one (which could be, for example, that you used trial and error), do see me about it.
• 5/13/04 Advice: For E8 p. 138, there are really two issues: (1) Two congruences x ≡ y (mod r) and x ≡ y (mod s) are equivalent to the single congruence x ≡ y (mod rs) if r and s are coprime (= relatively prime); (2) if a list 1, a, a2,..., 1, a, repeats every d terms and a similar list repeats every e terms, how often do they repeat simultaneously?
• 5/13/04 Advice: For E10 p. 123, you are going to need some additive property of 0 to start from.
• 5/13/04 In E7 p. 126-7, 1 + i is intended in place of i + i. (See the errata link above.)
• 5/9/04 Assignment 5 has been posted (see Handouts). Notice that for pp. 144-145 it's E13, rather than the E18 that I wrote on the board during the exam.
• 5/6/04 For Assignment 3, the solution to p. 53 E18 was omitted. The idea is like the solution of E13 in the same section: List the primes in a, the primes in b (which don't overlap those for a) and then any additional primes that are in n. Write the prime factorizations of a, b, and n "in parallel" with exponents, some of which will be 0. Then compute the prime factorizations of gcd(a,n), gcd(b,n), and gcd(ab,n) "in parallel" also. (Thanks to ASA.)
• 5/6/04 In problem C-13 and its solution, notice that the formula in (d) involves ρ bar to a positive power n rather than ρ to a negative power. The typesetting is a little confusing. (Thanks to ASA.)
• 5/6/04 Here is a link to errata for the text by Childs.
• 5/5/04 at 5:52p.m. Here are links to solutions to Assignment 3 and solutions to Assignment 4 . (Both have been improved from the original postings.) For solutions to Assignments 1 and 2, see the TA's Math 117 pages, for which a link is given above.
• 4/28/04 In D-2, it should be π(108) = 5,761,455 and π(109) = 50,847,534. Use either one in your work. (Thanks to WCC.)
• 4/28/04 In D-2, log means natural log, which is the usual notation in advanced math and in computer languages. Engineering, some calculators, and some calculus books use ln.
• 4/26/04 A few people had trouble with Java on their browser. In case you do: Check your browser version by going to the Help menu and clicking on About.... If it's Internet Explorer 6, try this: On the Tools menu, select Internet Options and then click on the Advanced tab. Pull the slider half way down and look for the box JIT compiler for virtual machine enabled. If it's not already selected, that's your problem; select it, click OK at the bottom, and restart your PC.
• 4/26/04 Office hours for Thursday, April 29 will be 11:00-12:00. (Office hours for Wednesday, April 28 will be 11:00-12:00 as usual. I can be there past 12:00 on request.)
• 4/22/04 Here is a link to the website mentioned in D-1: Mamikon's Pascal-Sierpinski. The link given in D-1 seems not to be working. As mentioned by the TA, you can postpone this problem for a week.
• 4/21/04 A misprint early in the text: p. 26, should be gcd(15,42) = 3. (Thanks to AC.)
• 4/21/04 An additional misprint on Handout D: The problem on p. 55 was supposed to be E1. (Thanks to JL.)
• 4/19/04 There were several misprints in the first posting of Assignment 3 (Handout D); corrections have been made here and in the paper handout. (Thanks to VS.)
• 4/16/04 Office hours Monday 4/19 will be 11:30-12:30.
• 4/16/04 Assignment 3 should be posted soon and will be handed out Monday.
• 4/14/04 On Assignment 2, C-3, the symbols for 1 choose n should be n choose 1 in both parts.
• 4/7/04 On Assignment 1, p. 18, Ex. 2 was done in lecture, so you don't need to hand it in.
• 3/15/04 Enrollment is now closed.