All posts by profstange

Your friendly professor.

Monday, October 17th

Today we’ll do examples of baby-step-giant-step and index calculus, and (maybe) talk about signatures.

The groupwork is DUE today.  There will be no mission during quiz week.

To do for class:

  • Read Sections 3.7, 7.1, 7.2.2 and 7.2.3, 7.4 and 7.5 (including 7.5.1) in the text.  This covers the discrete logarithm material we have seen recently.
  • Before the quiz on Wed, do some appropriate textbook problems:  Chapter 3 Exercise#17, Computer prob #7, 9.  Chapter 7 Exercise #1,2,5,6,7,10,11,12.
  • Check out the list of quiz material, listed under Wednesday’s daily post (in the menu bar at left).  Prepare for the quiz.

Wednesday, October 12th

To do for class:

  • 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.
  • Read Section 3.7 on primitive roots.

Monday, October 10th

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.

Friday, October 7th

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

Wednesday, October 5th

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

Monday, October 3

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.

Friday September 30

No work for today except to finish up writeup of Mission #5 and hand in today.

I plan to discuss the effectiveness of groupwork today in class, so please give it some thought:

  • Has it been helpful for you?
  • Pros and cons?
  • What are the challenges?
  • How could the system be improved?
  • Would you replace the groupwork system with something else?

I will probably finish the discussion with an anonymous survey based on the discussion.

Wednesday September 28

Second Quiz Today.

  • Be able to perform by hand the following algorithms.  I may also ask you to demonstrate understanding of why/how they work through abstract questions.
    • Basic modular arithmetic
    • Euclidean algorithm & finding inverses mod n
    • Efficient modular exponentiation (by repeated squaring)
    • 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.

Monday September 26

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.