MATH2068 Number Theory and Cryptography

General Information

This page contains information on the Intermediate Unit of Study MATH2068: Number Theory and Cryptography.

This unit is offered in Semester 2.

The lecturer for this unit of study is Bob Howlett.

For further information on Intermediate Mathematics and Statistics, refer to the Intermediate Handbook.

You may also view the Faculty Handbook entry for MATH2068 from the central units of study database.

Credit point value: 6CP.
Classes per week: Three lectures, one tutorial and one computer laboratory session.

Textbook

"Number Theory and Cryptography: lecture notes for MATH2068" can be purchased from KopyStop. The price is $14.00.

Misprints in the lecture notes

Page 7, halfway down, Euclidean Algorithm example: change "We first apply the basic Euclidean Algorithm to find the gcd of 78 and 15" to "We first apply the basic Euclidean Algorithm to find the gcd of 78 and 21". And after the calculation, change "so gcd(78,15) = 3" to "so gcd(78,21) = 3".
Page 75, line 12. The formula ∑e|dφ(e) = d is wrong: the "e|d" should be a subscript to the summation sign. That is, it should read ∑_e|dφ(e) = d.

Please tell me of any other misprints you find.

Reference book

I have asked the Co-op bookshop to obtain thirty copies of the following book:

Elementary Number Theory
and its applications
by Kenneth H. Rosen, published by Pearson/Addison Wesley (5th ed. 2005).

This book covers everything in MATH2068 and is pitched at the right level; so if you want to have a book I suggest that this is the one you get.

An old but still wonderful book on Number Theory is An introduction to the theory of numbers by G. H. Hardy and E. M. Wright. (Of course it has much more in it than we will study in MATH2068, and it is pitched at a more advanced level.)

There are many good books, however, and you can just visit the Number Theory section of the library and take your pick.

Lecturer consultation times

Tuesdays and Thursdays between 12:00 and 2:00 in Carslaw Room 709.

You may knock on my door at other times if you wish. Check my timetable first to see the best times to try.

Assessment Information

So that assessment for this unit will not be too dependent on the final exam, it has been decided to have two assignments. These will both count for 10% of the final mark. There will also be a tutorial participation mark, counting 5%. The final exam will therefore be worth 75%.

The due dates for the assignments will be September 11 and October 9. The questions will be released a week before the due dates.

No rolls will be kept in the computer tutorials. Your attendance at these tutorials will be determined from the computer login records.

Magma download

It is possible for a student enrolled in MATH2068 (or indeed for a student enrolled in any Mathematics unit) to download the student version of magma to install on a home computer. To do so, go to the page http://www.maths.usyd.edu.au/u/claus/loc and follow the appropriate links. You will need to login using your unikey.

If you have any problem getting magma to work on your home computer, please email me describing the problem. Be sure to tell me your computer's operating system.

To do computer tutorials at home you will also need to download the MATH2068 Magma startup file MagmaProcedures.txt. (For Windows users: I suggest that you create a new folder for MATH2068 and save MagmaProcedures.txt into this folder. Then paste a shortcut to Magma into this folder. Right-click the shortcut, select "properties" and change the "start in" field to be the name of your newly created MATH2068 folder.) When you start Magma, type

load "MagmaProcedures.txt";

as your first command. (An alternative, if you know how to do it, is to define an environment variable called MAGMA_STARTUP_FILE, the value of which should be filename (including the path) for the file MagmaProcedures.txt.)

New feature! A new version of the file MagmaProcedures.txt has been installed. It now includes a list of the thousand most commonly used words in the English language. Moreover, in a Magma session, if xxxx is a piece of ciphertext then you can use the command

Score(xxxx,Common);

to find out whether or not xxxx contains many of these common words. This should be useful when attempting to crack a substitution cipher.

Students who have installed magma at home will be permitted to do the computer tutorials at home and still be credited with attending these tutorials, provided they send me their magma log files. This can be via the Computer Tutorial Log File Upload page.

Extra files to download for the computer tutorials

Computer Tutorial 3: tut3texts.txt
Computer Tutorial 4: tut4texts.txt
Computer Tutorial 5: tut5texts.txt
Computer Tutorial 6: hagmach.m and abede.txt

Computer Tutorial 7: tut7texts.txt
Computer Tutorial 8: tut8.m
Computer Tutorial 11: tut11.m
Computer Tutorial 12: tut12.m

On-line Material

Lectures

Copies of the notes for individual lectures will be released here progressively. These will usually be scanned copies of the lecturer's handwritten notes.

Lecture 1 (powerpoint): 4 on 1 or 1 to 1
Lecture 2 (scanned)
Lecture 3 (scanned)
Lecture 4 (powerpoint): 4 on 1 or 1 to 1
Lecture 5 (scanned)
Lecture 6 (scanned)
Lecture 7 (powerpoint): 4 on 1 or 1 to 1
Lecture 8 (powerpoint): 4 on 1 or 1 to 1
Lecture 9 (scanned)
Lecture 10 (powerpoint): 4 on 1 or 1 to 1
Lecture 11 (powerpoint): 4 on 1 or 1 to 1
Lecture 12 (scanned)

Lecture 13 (powerpoint): 4 on 1 or 1 to 1
Lecture 14 (powerpoint): 4 on 1 or 1 to 1
Lecture 15 (powerpoint): 4 on 1 or 1 to 1

Question sheets and solutions

Here is the ASSIGNMENT 1 QUESTION SHEET.

Here is a1ciphertext.txt the ciphertext for Question 4 of the assignment.

Computer Tutorial 1 (Week 1)
Computer Tutorial 2 (Week 2) and Computer Tutorial 2 Solutions – and Question 7 separately
Computer Tutorial 3 (Week 3) and Computer Tutorial 3 Solutions
Computer Tutorial 4 (Week 4) and Computer Tutorial 4 Solutions
Computer Tutorial 5 (Week 5) and Computer Tutorial 5 Solutions
Week 6: set aside for completing unfinished things from earlier weeks and/or the assignment.

Recreation

Hagelin Machine

The M-209 cipher machine, used by the US in WWII, is essentially the same as the "Hagelin Machine" described in lectures. To better understand its workings you may find it useful to download the M-209 Simulator, from http://users.telenet.be/d.rijmenants/index.htm.

(Dirk Rijmenants also has other cipher machine simulators, e.g. the Hagelin BC-52.)

Vigenère cipher cracker

We will study Vigenère ciphers in the Computer Tutorials in Weeks 3 and 4. See also the notes for Week 5.

Three samples of ciphertexts are available here: ct2.txt, ct3.txt, ct5.txt. See if you can find the keys by using the javascript vigenère cipher cracker.

This javascript was written by Fred Richman of Florida Atlantic University, and modified by David Kohel.

Timetable

Last revised 19/08/08

All rooms are in the Carslaw building unless otherwise indicated.

MATH2068	Monday	Tuesday	Wednesday	Thursday
10am		Computer Lab 610/611 Howlett RB	Computer Lab 610/611 Howlett RB	Tutorial 454 (Wks 2-13) Molev AI
11am		Tutorial 454 (Wks 2-13) Koonin J
noon	Computer Lab 610/611 Howlett RB
1pm	Lecture 175 Howlett RB
2pm		Lecture 175 Howlett RB	Lecture 175 Howlett RB
3pm	Tutorial 454 (Wks 2-13) Koonin J