Maths & Stats / Teaching program / Intermediate / MATH2988

MATH2988 Number Theory and Cryptography (advanced)

General Information

This page contains information on the Intermediate Unit of Study MATH2988 Number Theory and Cryptography (advanced).

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 MATH2988 in 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/2988" can be purchased from KopyStop. Price: $14.00.

Reference book

I have asked the Co-op bookshop to obtain some 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/2988 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.

Exam Information

The MATH2068 exam will follow a similar format to exams of previous years: five questions, with the last question much harder than the others (to determine if anyone deserves a high distinction). The MATH2988 exam consists of the MATH2068 exam plus one extra advanced level question.

You may view the front cover of the exam paper.

Pre-exam consultations

I will be available on any week-day before the exam; you are welcome to come and knock on my door (Carslaw Room 709). I may not arrive until late in the morning. You may email me to make an appointment if you wish.

Everyone should collect their marked assignments from me. (Carslaw Room 709 – any week-day before the exam.)

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%.

Magma download

It is possible for a student enrolled in MATH2068/2988 (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.

I think that installing magma at home is a GOOD IDEA, especially for students in the advanced unit, though of course it is not necessary.

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.

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 done via the Computer Tutorial Log File Upload page.

Although installing magma at home is a good idea, not attending the actual computer tutorials is probably not such a good idea!

To do computer tutorials at home you will also need to download the MATH2068 Magma startup file, and usually a data file specific to the tutorial in question. These files will be made available for download from this page.

Magma Documentation is available on-line. But it may well be more efficient to ask me how to do it rather than searching through the on-line help.

Magma files to download for home use

Most important is our MATH2068/2988 magma startup file MagmaProcedures.txt. Tutorial-specific files will be posted here week by week.

People doing the computer tutorials at home will have to type 

   load "MagmaProcedures.txt";

as the first command in each magma session.

Magma installation suggestions (Windows users)

(Users of other operating systems: if you have a problem, ask me. We may have to get the expert assistance of someone from the magma group, but that will be readily forthcoming.)

I suggest that you create a new folder for MATH2988 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 MATH2988 folder. To start magma, double-click the shortcut icon. Note that for each tutorial you should type 

load "MagmaProcedures.txt";

as your first magma 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.)

Check your marks

You may check your marks for Assignment 1 and Assignment 2, as well as your Tutorial Participation mark, by entering your 9 digit SID into the box below and then pressing the "Check marks" button.

SID:              

If you believe that your marks are recorded incorrectly, please report the fact without delay.

If you consider that your tutorial particpation mark is lower than it should be, you must contact your lecturer about it no later then November 13th.

In calculating the final mark, the marks for both parts of both assignments will be scaled to marks out of 5 and then added to the tutorial participation mark. This total (out of 25) will be added to the exam mark (out of 75).

 

On-line Material

Anyone who has not yet collected from me their marked scripts for Assignment 1 and/or Assignment 2 is urged to do so without delay.

To retrieve the marked version of the electronically submitted part of either assignment, log in to a lab computer and click the "handout" icon on the desktop.

Alternatively, it is possible retrieve the marked version of the electronically submitted part by selecting either Assignment 1 or Assignment 2 below and clicking the "Download" button.

Use your browser's "save page" feature to save the marked assignment as a text file.

Question sheets and solutions

Past exam papers

  • Sample exam 2005
  • 2005
  • 2006
  • 2007
  • 2008

    • MATH2988 students:

    There is no past exam paper or sample exam. Use the last question of previous MATH2068 exams, as well as the starred tutorial exercises, as a guide to the kind of thing that may be asked,

Assignment 2, and Solutions to Questions 1, 2 and 3.

Assignment 1, and Solutions to Questions 1, 2 and 3.

Lectures

Recreation

There are now 47 known Mersenne primes!

Recall from Tutorial 2 that a Mersenne number is a number M of the form 2k−1 for some prime number k. If a Mersenne number happens to be prime then it is called a Mersenne prime. (For example, 25−1 = 31 is a Mersenne prime.) Mersenne primes have some interesting and/or amusing properties: for example, if 2k−1 is a Mersenne prime then 2k−1(2k−1) is a perfect number, which means that it is equal to the sum of all its proper divisors. (You may check that 496 is a perfect number.)

The nine largest known prime numbers are all Mersenne primes, and they were all found by people participating in the Great Internet Mersenne Prime Search (GIMPS). The latest to be discovered is 242,643,801−1, the 47th known Mersenne prime. (There used to be $100000 prize for the first person to find a ten million digit prime, but GIMPS won that last year – so bad luck! The above Mersenne prime has 12837064 digits.)

The nine largest known prime numbers are as follows: 243,112,609−1 (proved prime on August 23, 2008), 242,643,801−1 (April 12, 2009), 237,156,667−1 (September 6, 2008), 232,582,657−1 (September 4, 2006), 230,402,457−1 (December 15, 2005), 225,964,951−1 (February 18, 2005), 224,0365,83−1 (May 15, 2004), 220,996,011−1 (November 17, 2003) and 213,466,917−1 (November 14th 2001).

Probabilistic arguments suggest that on average one should expect to find 1.78 Mersenne primes between 22k and 22k+1 (for any k); so it is remarkable that five of the exponents above lie between 224 = 16777216 and 225 = 33554432. For k less than 24 there are never more than three Mersenne primes between 22k and 22k+1. Three occurs five times. (But I see that they have already got three between 225 and 226. Maybe those probabilistic arguments are dodgy!)

The GIMPS Home Page is a good starting place for learning more about Mersenne primes.

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.)

Primality testing in Magma

Let n be a large integer. How can Magma determine whether or not n is prime? The following excerpt from the Magma documentation, somewhat expanded, outlines what it does.

We may as well assume that n is odd, because the question is trivial if it is even! So n − 1 is even, and dividing it by 2 will give an integral answer. If this answer is still even we can divide by 2 again, and keep on like this until we get an odd number r. In this way we can express n − 1 as r2k for some positive integer k.

If n is composite, it is possible to quickly prove that it is composite by exhibiting a "witness" to this fact. A witness for the compositeness of n is a positive integer a less than n with the property that ar is not congruent to 1 modulo n, and ar2i is not congruent to −1 (mod n) for all i from 0 to k − 1. (Recall that n − 1 = r2k.)

We shall show below that a witness never lies: if there exists a witness to the compositeness of n then n is certainly not prime. Moreover, it has been shown – although this proof is too hard for us here – that if n is composite then a fraction of at least 3/4 of all a in the range from 2 to n − 1 will witness the fact. Thus randomly choosing a will usually quickly expose compositeness. This is called the Miller-Rabin compositeness test. However, unless more than 3/4 of all possibilities for a are checked – which in practice will be impossible for reasonably large n – failure of the Miller-Rabin compositenss test will not suffice to prove the primality of n. Nevertheless, failure of Miller-Rabin lends credibility to the claim that n is most likely prime: if among K (say 20) random choices for a no witness for compositeness has been found then n is called "probably prime of order K", and in some sense the probability that n is composite is less than 4−K.

A slight adaptation of this idea can be used for primality proofs in a bounded range. There are no composites smaller than 34×1013 for which a witness does not exist among a = 2, 3, 5, 7, 11, 13, 17 (G. Jaeschke, "On strong pseudoprimes to several bases", Math. Comp. 61, 1993). Using these values of a for candidate witnesses it is certain that for any number n less than 34×1013 the test will either find a witness or correctly declare n prime.

Even for large integers it is usually easy to identify composites without finding a factor; however, to be certain that a large probable prime is truly prime, a primality proving algorithm must be used. Magma uses the ECPP (Elliptic Curve Primality Proving) method, as implemented by François Morain (Ecole Polytechnique and INRIA). The ECPP program in turn uses the BigNum package developed jointly by INRIA and Digital PRL. This ECPP method is both fast and rigorous, but for large integers (of say more than 100 decimal digits) it will still be much slower than the Miller-Rabin compositeness test. The method is too involved to be explained here; we refer the reader to the literature (A. O. L. Atkin and F. Morain, "Elliptic curves and primality proving", Math. Comp. 61, 1993).

We now present the promised proof that witnesses are trustworthy. This is something that all MATH2068 students should be able to understand, and something that we shall return to in Computer Tutorial 11. Suppose, for a contradiction, that a is a witness to the compositeness of n but that n is actually prime. To make the idea of the proof more transparent we shall assume first that the number k above is 4, meaning that n − 1 is divisible by 24 but not 25. Thus n − 1 = 16r, where r is odd. The statement that a is a witness to the compositeness of n says that ar is not congruent to 1 modulo n, and ar, a2r, a4r and a8r are not congruent to −1 modulo n.

Note first that since n is prime, Fermat tells us that a16r = an−1 ≡ 1 (mod n). But a16r is the square of a8r, and the fact that n is prime also means that x2 ≡ 1 (mod n) implies that x ≡ ±1 (mod n). (You should be able to prove this!) But we are given that a8r is not congruent to −1 modulo n, and so it follows that a8r ≡ 1 (mod n). Now we can repeat the argument. Since a8r = (a4r)2 it follows that a4r ≡ ±1 (mod n), and since we are given that a4r is not congruent to −1 it follows that a4r ≡ 1 (mod n). Now repeat the argument again. Since a4r = (a2r)2 it follows that a2r ≡ ±1 (mod n), and since we are given that a2r is not congruent to −1 it follows that a2r ≡ 1 (mod n). And again: since a2r = (ar)2 it follows that ar ≡ ±1 (mod n). But we are given that ar is not congruent to −1 modulo n, and we are also given that ar is not congruent to 1 modulo n, and so we have obtained the contradiction we were seeking.

The assumption that k = 4 was, of course, unnecessary, and we leave it to the reader to extend the argument to deal with all positive integer values of k.

Vigenère cipher cracker

We studied Vigenère ciphers in the Computer Tutorials in Weeks 3 and 4. They are also described in "Number Theory and Cryptography: lecture notes for MATH2068/2988", in the chapter for Week 5, and in the file for Lecture 15.

Three samples of ciphertexts are available here: ct2.txt, ct3.txt, ct5.txt. Try to find the keys using the javascript vigenère cipher cracker!

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

Timetable