Math 135 Assignments

General remarks

    Legible and neat;
    Adequate detail in proofs;
    Use correct English.

Assignment 1 Solutions

Barr 1.1: 2, 6, 14, 20, 21, 22.

A1.  Let a parade of N people be an arrangement of the people
(all facing the same direction) in a rectangle so that there are
the same number of people in each rank and in each file.
   There are two three person parades: 1 x 3 and 3 x 1.

How many parades of are there of 4 people? 5? 6? 7? 8? 9?

Find a some odd numbers with exactly four parades,
counting the 1 x N and N x 1 parades.
What do these odd numbers have in common?
Among these, there are two kinds. Can you describe them?

Please do all of the problems. Problems 21, 22, and A1 will be graded.

Assignment 2 Solutions

Read Barr chapter 1 and sections 2.1-2.3 as needed.
We'll cover the mod arithmetic week for 2/9.
For some of these problems, a cipher wheel may help.

Problems.

Barr 2.3: 2, 3a, 3b, 4*, 7, 10*.

B1*.  Use induction to show that 13+23+ ...+n3 = (¼)n2(n+1)2.

B2*.  Evaluate the function f(x) = x2+x+41 at x = 1, 2, 3.
Decide whether the value of f(x) is prime for all natural numbers x.

Please do all of the problems. The starred ones will be graded.

Assignment 3 Solutions

Read Davenport section 1.6 for a treatment of Euclid's algorithm.

Problems.

Barr 2.1, p. 66, #3 a, c, f,
Barr 2.2, p. 81, #4,

C1. a. Compute 5-1 (mod 23).
b. Compute 5-1 (mod 27).

C2. a. Find the two solutions X between 0 and 7 to X2 $\equiv$ 2 (mod 7).
b. Find the four solutions Y between 0 and 15 to Y2 $\equiv$ 4 (mod 15).
c. Find all solutions Z between 0 and 27 to Z2 $\equiv$ 4 (mod 27).

C3* a. Find a positive integer A which solves all three of:
A $\equiv$ 1 (mod 3),  A $\equiv$ 3 (mod 5),  and A $\equiv$ 5 (mod 7). 

b. Find a positive integer B which solves all of:
B $\equiv$ 5 (mod 6),  B $\equiv$ 7 (mod 10),  B $\equiv$ 2 (mod 15).

c. Why are there no integers C which solve both C $\equiv$ 7 (mod 10) and C $\equiv$ 8 (mod 16)?

C4* a. Use Euclid's Algorithm to determine the G.C.D. (greatest common divisor) of 98944 and 184747.
b. Compute 989452 mod 184747.
(Use a calculator if you want, but please write out the calculations you punch in.)

Food for thought (coming attractions).
Find two positive solutions, both less than 49385059, to
W2 $\equiv$ 1 (mod 49385059).
What's so hard about finding the other two?

(In case you aren't convinced, solve W2 $\equiv$ 1 mod 879175373047213769960200463349142693495595594510738810929240370110905045614693498981115033445156427 instead.)

Assignment 4 Solutions

Read the rest of Barr chapter 2. (For section 2.8,
appreciate that Vigenere can be decrypted, understand
the strategy, but please don't memorize the equations.)

Also read an account of the German enigma cipher.
Among many you'll find on the web and in print:
http://home.earthlink.net/~nbrass1/enigma.htm
http://www.cs.miami.edu/~harald/enigma/enigma.html
http://webhome.idirect.com/~jproc/crypto/enigs2.html
http://pan.net/history/enigma/enigma15.htm
There are several good books which you'll find referenced above, too.
Most of these sources rely on the same set of primary documents.

Problems in Barr:
2.4: 2, 4
2.5: 4, 6
2.6: 5, 6, 14*
2.7: 2*

The Fibonacci numbers F(n) are defined as follows:
F(1) = 1,  F(2) = 1,  F(n) = F(n-1) + F(n-2).

The sequence of Fibonacci numbers begins 1, 1, 2, 3, 5, 8.

D1. Use an induction argument to show F(n) and F(n+1) are
relatively prime for any natural number n.

(Example: F(5) = 5 and F(6) = 8. GCD(5,8) = 1. But your
argument has to work for ALL n, and so cannot be solely a
bunch of examples.)

D2*. Use an induction argument to show F(n)2 - F(n+1)F(n-1) is either 1 or -1 for any natural number n.

(Example: F(5) = 5, F(6) = 8, F(7) = F(5) + F(6) = 13. 8x8 - 5x13 = -1.
F(2) = 1, F(3) = 2, F(4) = 3, and 2x2 - 1x3 = +1. Again, a string of examples is not enough.)

Assignment 5 Solutions

Please read the introduction to chapter 3 and section 3.1.
We might not cover it in class this week, but this assignment
shouldn't be too much heavy lifting, and is preparation
for the computer based methods coming up.

Base 16, also called hexadecimal, is common in computer applications.
The usual symbols are the ordinary digits 0 to 9, plus A, B, C, D, E, F,
representing the decimal values 10, 11, 12, 13, 14, 15.

Hexadecimal 1C is decimal 1 x 16 + 12 = 28.
Sometimes you will see the base indicated by a subscript:
1C16 = 2810 = 111002.

Some computer programs use the prefix Ox for hexadecimal, as in 0x1C = 28.
The prefix $ seems less popular now in computing. I like it for handwritten work.

Problems.

Barr 3.1: 2, 3, 10

E1* Do the following binary arithmetic.
   11002 + 10012
   11002 - 10012
   11002 x 10012

E2* Rewrite these arithmetic problems and solutions base 10.

E3* Rewrite these arithmetic problems and solutions base 16.

E4. Ditto E1-3 for 11002 / 10012

E5* Why is conversion between base 2 and base 16 especially straight forward,
compared with converting base 2 to base 10?

E6. How many bytes in a kilobyte? Why? What is this number in base 16?

Assignment 6 Solutions

Read Barr 3.2, 3.3.

Problems.

Barr p. 200: 2, 3, 4*.

F1. Checksums are similar to the boolean functions in section 3.2.
Try this one: let x1, x2, ... x10 be decimal digits.
Define f(x1x2x3x4x5x6x7x8x9x10) = (x1+2x2+3x3+4x4+5x5+6x6+7x7+8x8+9x9+10x10) mod 11.
That is, compute the sum, divide by 11, and look at the remainder.
Compute f(0121012101).
Try the ISBN numbers of your favorite books.

F2*. Suppose three programs run on a computer. They each take as input a single number N. If N is d digits long, then

program 1 takes 37d3 seconds,
program 2 takes 5 x 10(d-6) seconds,
program 3 takes 1.5 x 10(2 + √d) seconds.

a. Put the programs in order, from fastest to slowest, for d = 4.
b. Put the programs in order, from fastest to slowest, for d = 100.

F3. Two more programs.
Program E computes gcd's of numbers N1 and N2.
Let d be the number of digits in the product N1N2.
Suppose E runs in at most (27d2 + d) x 10-6 seconds.

How long (at most) will E take on two numbers of 20 digits each? 22 digits? 40 digits?

Program F factors integer N using the method of trial division.
Let d be the number of digits of N. The longest run time of program F is 10d/2 x 10-9 seconds.
How long will F take for numbers of 20 digits? 22 digits? 40 digits?

F4*. One more program.
Program D cracks a block cipher system (maybe DES!) by trying
every possible key. The key is known to be a b bit binary number.
Program D can try 238 keys per second.

How long will D take to try all possible 56 bit keys?
How long will D take to try all possible 64 bit keys?
How long will D take to try all possible 112 bit keys?

F5. What is the complexity of the above programs (1, 2, 3, D, E, F)?
Just a rough idea: polynomial, meaning O(dr) for some r,
exponential, meaning O(rd) for some r, or
something bigger than any polynomial but smaller than any exponential, or
something bigger than any exponential.

Repechage de Prelim 1, due Monday, March 8

If you got 20 or less on problem 3b of prelim 1, redo 3b brilliantly, for up to 10 points.

Otherwise, solve the bonus on prelim 1 for up to 10 points.

The problems: Let S1 = 1, S2 = 1, and Sn = 2Sn-1 + Sn-2.
This defines a sequence of numbers: S1, S2, S3, ...

3b. Show consecutive numbers in this sequence are relatively prime.
(Hint: use an induction argument.)

BONUS. Explain why Sn is never a multiple of 5.

Assignment 7 Solutions

Read sections 3.4 and 3.5 of Barr.

Do the following problems:
Barr p. 201: 8
p. 208: 2*, 5, 6.
p. 220: 3b*.

G1* What is the output of the following funny shift register:
Given register contents DCBA, output (A+C) mod 2,
and shift the register, so that C' = D, B' = C, A' = B, and D' = (A+B) mod 2. Notice D' is NOT the same as the output.

a. Start with DCBA = 1011. What is the output of this machine?
b. Find an ordinary four bit shift register and its starting value which produces the same output.

A linear congruential generator (LCG) is another kind of pseudorandom number generator.
The parameters are integers A, B, M and x0.
The value x0 is called the seed.
The computation is xn+1 = Axn + B (mod M).
(That is, set xn+1 to the remainder left when Axn + B is divided by M.)

G2* Compute the values produced by the LCG with A = 3, B = 2, M = 17, and x0 = 2. How long is the cycle?

Assignment 8 Solutions

Read Barr 5.1.

For the following problems, use the block cipher from example 3.5.1 in Barr. The encipherment function E
takes a four bit message block and a three bit key, and returns a four bit cipher block.
The decipherment function D is the inverse of E.

Let N be the number of different four bit messages.

H1. What is N?
H2. How many simple substitutions are there for an alphabet of size N?
H3* How many substitutions are theoretically possible when E is applied
twice with the same key: E(E(x1x2x3x4, k1k2k3), k1k2k3)?

H4* How many substitutions are theoretically possible when E is applied
twice with different keys: E(E(x1x2x3x4, k1k2k3), m1m2m3)?

H5* Suppose you see matched plaintext/ciphertext:
x1x2x3x4 = 0101
y1y2y3y4 = 0010

and you know the encipherment method is
y1y2y3y4 = E(E(x1x2x3x4, k1k2k3), k1k2k3).

Find k1k2k3.
Can you think of a better way than just trying keys until you get it?

H6. Suppse you see the matched plaintext/ciphertext (two blocks):
x1x2x3x4 = 0101
y1y2y3y4 = 1100

x5x6x7x8 = 1101
y5y6y7y8 = 0011

and you know the encipherment method is
y1y2y3y4 = E(E(x1x2x3x4, k1k2k3), m1m2m3),

y5y6y7y8 = E(E(x5x6x7x8, k1k2k3), m1m2m3).

What is the maximum number of guesses you need to find (both parts of) the key?

H7* Same setup as above -- cracked with the meet-in-the-middle method.
Imagine making a list of E(x1x2x3x4, k1k2k3) for every key
and a second list of D(y1y2y3y4, m1m2m3) for every key.
(Do the same for the second block as well.)

How many keys do you try to make each list?
How can you use these lists to figure out the correct key?

Why is it important to have more than one message block (or,
what is likely to happen if you have only one block of matched plain and cipher)?

H8* The DES method enciphers 64 bit blocks using a 56 bit key.
Describe the meet-in-the-middle attack on Double DES with two different keys.
How many two-part keys are there for Double DES?
How many one-part keys do you try with the meet-in-the-middle attack?

Paper topic, due March 31

Please prepare a topic, a thesis paragraph, and
at least three verifiable references, preferably
hard copy for the paper assignment.

Write an opinion on an issue of
public policy relevant to the course. Part of
the support for your argument should be based on
quantitative reasoning, for example, sound estimates
of how long, how expensive, or how likely.

Assignment 9 Solutions

This is really short, due to there being a prelim and
a paper topic this week.

Read Barr 4.3, 4.4 (and any earlier part of chapter 4
you need to understand it).

I1a*. Find an integer X such that X2 $\equiv$ 5 mod 31 as follows.
How do we also know X32 $\equiv$ 5 mod 31?

b*. X32 $\equiv$ ((X2)8)2 $\equiv$ (58)2 $\equiv$ 5 mod 31.
Compute (the smallest nonnegative) X $\equiv$ 58 mod 31.
Check 5$\equiv$ X2 mod 31.

I2. Compute Y $\equiv$ 1011 mod 43.
Explain why Y is a squareroot of 10 mod 43.

Assignment 10 Solutions

Read Barr 4.5.

Note: bring a calculator to class next week.
We'll have a practical lab one day (Wednesday most likely).
Please do the reading by then.

Problems in Barr:
4.1: *16, 17
4.3: *1d, *1e, *6 (look at #5)
4.4: 4, *6, 8

A calculator might be helpful for some of these.
Also note there is a table of primes near the back of the book.

Assignment 11 Solutions

Read Barr 4.6, 4.7, 5.3.

Do the following problems.

Barr 4.6: 1, 2.
Barr 4.7: *1, 3, *7

K1. For the Fiat-Shamir method, Why is it important to use a modulus n = pq
which is hard to factor? Would using a large prime n work as well?

*K2. Compute discrete logs for the following numbers using
modulus P = 10111, and base B = 12.

Show how you get your answers using simple addition, subtraction, and
multiplication. (You may use a calculator to actually do the basic
arithmetic you describe. Do not compute the entire discrete log table.)

The following precomputed discrete logs (dlog) will help:
dlog(2) = 4918,
dlog(3) = 275,
dlog(5) = 9226,
dlog(7) = 3640,
dlog(11) = 250,
dlog(13) = 4478.

a. 2401 = 74     b. 1001 = 7 x 11 x 13     c. 10100     d. 9889

Note: This problem suggests a faster than exponential algorithm for discrete log
which uses discrete logs of some key numbers in order to build
the discrete logs of other numbers.

Assignment 12 Solutions

Read an article about factorization from Notices of the American Math Society,
and about some people actually doing it.

L1. Make a list of fifth powers modulo 11.
(Answer: see solution to Barr problem 4.5 #1.)

L2* a. Make a list of the fourth powers modulo 15.
b. Make a list of the fourth powers modulo 35.
c. What theorem suggests that you get exactly the numbers you do?

Assignment 13 Solutions

You might want to refer to these notes for details on the algorithms.

M1. Find the prime divisors of the following numbers using Fermat's method (N + x2 = y2).

a. 437   *b. 1081   *c. 1961.

M2. Find the prime divisors of the following numbers using Pollard's p-1 method.
Choose any a you like, but I suggest a=2 is easiest.
Repeated squaring might be a helpful way to compute the powers.
Remember that to get from one step to the next, you need only
a small prime power of what you already have.

a. 3233     *b. 3977   *c. 862577

M3* The factors of 274181 are 487 and 563.
Pollard's p-1 method finds the factors, but it takes a lot longer than factoring 862577.

Why does Pollard's p-1 method perform so badly on 274181?

Paper due Wednesday, May 5.

It should be about five pages long, plus a separate title page,
and a separate references page. Please use standard margins and
typeface. See the body of the textbook for an example. Please
don't waste the expense of a fancy binder. A staple will do fine.

Please remember to be skeptical of references on the internet.
Online collections of scholarly journals and government documents
are probably genuine. But on what basis do you believe an ezine
commentary?


Back to course home page. 
lawren@math.cornell.edu

Last modified: Thu Jan 24 17:26:23 EDT 2001