Read Section 6.4 and review the factorization methods we’ve been working on (Pollard’s p-1 and quadratic sieve). Implement Pollard’s p-1 on a small example for practice. Read the Quadratic Sieve handout to fill in any blanks in your understanding from class.

We’ll be back to our regularly scheduled programming. I have posted solutions to the programming workshop in the menu bar at left, and you can find solutions to the proofs here. For Monday, my suggestion is to take a look at solutions and work on your group homework.

Today we will continue the workshop in ECCR 235. I’ll give you more time to work and ask me questions, a continuation of today. If you feel the time is better spent working on your individual component of the group project, I’m happy to help with that too!

Also today, you can hand in an updated version of one problem on your quiz. You can do this no matter what you scored, and I will re-grade it, for a maximum of 3/4 of the credit of the original problem (i.e. a maximum score of 6 points). (This is aimed to help you out if you totally missed one problem.)

The plan is to have a coding & proof workshop today. That means, for those who don’t have coding background, you will work through a coding introduction, and for those who don’t have proof background, we’ll do some proof activities aimed at giving you some expertise. We will be in ECCR 235.

With regards to the above, you should decide what is most useful to you. Here is the proofs practice sheet we’ll use; you might want to try some at home first and use the in-class time to get feedback and compare with others. For coding, you might want to revisit the Intro to Sage page and Programming Basics page in preparation for the workshop.

Also, please check out Mission #6, which is a two-week long mission, and discuss with your group how to break up the work. (Note: new groups were assigned on Monday, Oct 3rd, so if you missed the class, be in contact with me.)

Also, please check Friday’s post for some information on how to optionally hand in a supplement to the quiz, correcting your errors on one of the questions.

PS: D2L ate your quiz grades, so you can’t see them; this will be remedied soon

PS: Do you know Math Club has fun math lectures? The next one is tonight.

I’m going to take a day or two to think about the groupwork/design of the course. It sounds like it’s been a busy week, so the only suggestion over the weekend is to read about Enigma in The Code Book if you haven’t already — very interesting.

Chinese Remainder Theorem to solve a pair of congruences

Fermat primality test

Fermat factorization

Miller-Rabin primality test

RSA creating public and private keys

RSA encryption/decryption using keys

Computing Euler phi function as in Mission #4

Given n an phi(n), where n is an RSA modulus, compute a factorization of n using quadratic formula

Given a public key, and the factorization of the modulus, compute the private key

Be able to give well-written proofs of:

The multiple square root principle

Fermat’s Little Theorem (including the fact that multiplication by invertible elements is bijective)

Chinese Remainder Theorem (using ax+by=1)

novel statements involving basic definitions of modular arithmetic, or variations on the proofs just mentioned, or variations on the proofs of Mission #4

Things to know about:

divides, gcd, lcm, prime, composite, factor

statement of Euler’s Theorem

The multiple square root principle

Dangers of choosing primes close to each other in RSA

big O notation and runtimes of algorithms we’ve discussed (e.g. gcd, successive squaring)

multiplicative order of an element mod n

What “probably prime” means in theory and practice, pseudoprimes and strong pseudoprimes

Note: I’ve stayed pretty close to the textbook, so you’ll find all these things in there (except maybe big O notation and runtimes?) if your course-notes are lacking.

Please come to class having studied/reviewed these topics:

RSA — how to set up public/private keys and encrypt/decrypt

Fermat primality test

Multiple square root concept and Fermat factorization

Mini Sage Introduction (page at left)

Modular arithmetic in Sage (page at left)

Programming Basics (page at left)

If you are missing course notes from this material, phone a friend and get them!

In class, we will be working on Mission #5, with the aim of finishing during the class period so you don’t need to meet outside class. Please click on Mission #5 above to see the tasks, and look through them and think about them in preparation for the day’s work.

Monday’s work should serve as a review of the material for the Wednesday’s quiz, and as your Mission #5 assignment, so attendance is crucial.