Friday, October 12, 2012

Primality testing and applications to cryptography

Lecture notes for lecture #17 of MATH 235, taught by Henri Darmon. These lecture notes are student-generated and any errors or omissions should be assumed to be the fault of the notetaker and not of the lecturer. To correct an error, you have to be registered and logged-in; alternatively, you can contact @dellsystem directly.

In this lecture, we continued section 13 of the notes.

1Primality testing¶

Why is this useful, why is this difficult

1.1Methods¶

• Trial division (slow)
• Wilson's theorem (slow)
• Fermat's little theorem (quick but can't always distinguish primes from composites)

1.1.1Miller-Rabin¶

Probabilistic algorithm, should use FLT first and then Miller-Rabin to weed out pseudoprimes

1.2Cryptosystems¶

Probably the significant application of number theory

Public-key cryptography, RSA, one-way functions, etc

How it works mathematically (the theorem + proof)