(I would like you to know: What a prime number is, and What mathematical induction is and What an equivalence relation is. Helpful, but not required, is knowing how to “add/multiply two numbers mod-N, and the definition of the Euler phi function.)
See Useful NT Texts, below, for self-study suggestions.
Cryptography (or cryptology; derived from Greek κρυπτός kryptós "hidden," and the verb γράφω gráfo "write") is the study of message secrecy. In modern times, it has become a branch of information theory, as the mathematical study of information...
... Steganography (i.e., hiding even the existence of a message so as to keep it confidential) was also first developed in ancient times. An early example, from Herodotus, concealed a message - a tattoo on a slave's shaved head - by regrown hair. More modern examples of steganography include the use of invisible ink, microdots, and digital watermarks to conceal information .
Ciphertexts produced by classical ciphers always reveal statistical information about the plaintext, which can often be used to break them. After the Arab discovery of frequency analysis (around the year 1000), nearly all such ciphers became more or less readily breakable by an informed attacker. ... Essentially all ciphers remained vulnerable to cryptanalysis using this technique until the invention of the polyalphabetic cipher by Leon Battista Alberti around the year 1467. Alberti's innovation was to use different ciphers (ie, substitution alphabets) for various parts of a message (often each successive plaintext letter). He also invented what was probably the first automatic cipher device, a wheel which implemented a partial realization of his invention. In the polyalphabetic Vigenère cipher, encryption uses a key word, which controls letter substitution depending on which letter of the key word is used.
In all of my courses, attendance is absolutely required (excepting illness and religious holidays). In the unfortunate event that you miss a class, you are responsible to get all Notes / Announcements / TheWholeNineYards from a classmate, or several. All my classes have a substantial class-participation grade.
Authors: | Jeffrey Hoffstein, Jill Pipher, J.H. Silverman | ISBN: | 978-0-387-77993-5 |
Year: | 2008 | Publisher: | Springer |
Marston: | QA268 .H64 2008 | Electronic: | Chap. 1 and Chap. 2, Diffie-Hellman, etc. (Free for UF students) |
A Computational Introduction to Number Theory and Algebra, by Victor Shoup. The author has made freely available a PDF copy of his text for personal use.
In December 1932, the Polish Cipher Bureau first broke Germany's Enigma ciphers. Five weeks before the outbreak of World War II, on 25 July 1939, in Warsaw, the Polish Cipher Bureau gave Enigma-decryption techniques and equipment to French and British military intelligence. …[A]llied codebreakers were able to decrypt a vast number of messages that had been enciphered using the Enigma. The intelligence gleaned from this source was codenamed “Ultra” by the British.
[After World War II] Winston Churchill told Britain's King George VI:
It was thanks to Ultra that we won the war.Though the Enigma cipher had cryptographic weaknesses, in practice it was only in combination with other factors (procedural flaws, operator mistakes, occasional captured hardware and key tables, etc.) that those weaknesses allowed Allied cryptographers to be so successful.
The Euclidean algorithm can be presented in table-form; I call this form the Lightning-bolt algorithm (pdf), because the update-rule looks like a lightning-bolt (used thrice). Here is a practice sheet for LBolt (pdf).
The first page of
Algorithms in Number Theory (pdf)
uses LBolt iteratively to compute the GCD of a list of integers,
together with a list of Bézout multipliers.
Page 2 uses LBolt to solve linear congruences:
Find all x where 33x is mod-114 congruent to 18.
SOTSin the notes.
Various math czars who help out.
Time | Computer/Proj | Blackboard | Humor | E-Problems | Phone |
---|---|---|---|---|---|
? | ? | ? | ? | ? |
appliedapproach to cryptography.
The Project must be carefully typed, but diagrams may be hand-drawn and scanned into the PDF.
At all times have a paper copy you can hand-in; I do
NOT accept
electronic versions.
Print out a copy each day, so that you always have the latest version to
hand-in; this, in case your printer or computer fails.
(You are too old for My dog ate my homework.
)
Please follow the guidelines on the Checklist (pdf, 3pages) to earn full credit.
Diophantus of Alexandria - (Greek: Διόφαντος ὁ Ἀλεξανδρεύς , circa 200/214 – circa 284/298) was a Greek mathematician of the Hellenistic era. Little is known of his life except that he lived in Alexandria, Egypt ...
He was known for his study of equations with variables which take on rational values and these Diophantine equations are named after him. Diophantus is sometimes known as the
father of Algebra. He wrote a total of thirteen books on these equations. Diophantus also wrote a treatise on polygonal numbers.In 1637, while reviewing his translated copy of Diophantus' Arithmetica (pub. ca.250) Pierre de Fermat wrote his famous
Last Theoremin the page's margins. His copy with his margin-notes survives to this day.Although little is known about his life, some biographical information can be computed from his epitaph. He lived in Alexandria and he died when he was 84 years old. Diophantus was probably a Hellenized Babylonian.
A 5^{th} and 6^{th} century math puzzle involving Diophantus' age: He was a boy for one-sixth of his life. After one-twelfth more, he acquired a beard. After another one-seventh, he married. In the fifth year after his marriage his son was born. The son lived half as many as his father. Diophantus died 4 years after his son. How old was Diophantus when he died?
What is the answer, with reasoning? (It is in the source-file.)
Spring 2019, NT&Crypto:
Spring 2016, NT&Crypto:
Various math czars who help out.
Time | Computer/Proj | Humor | E-Problems | Phone |
---|---|---|---|---|
Tad | James S. | Chris L. | Autumn | Austin J. |
Pleasant U-Class (a mini-test of prerequisite knowledge) took place on Friday, 08Jan2016.
Previously available was a practice prereq.
The intriguing V-Home (pdf) is online, for your team-solving pleasure.
Next came the beguiling V-Class (pdf) for your posting enjoyment.Curiously, we had the chaotic X-Cl (pdf), that students accepted with good grace, since it had been typed just minutes before the exam was given. [Wedn., 06April2016.]
Spring 2014, NT&Crypto:
Spring 2013, NT&Crypto:
This was a 1-semester course interested in Mathematical Cryptography (major topic) and other aspects of Coding: Data Compression and Error-correcting codes. We also did one example of an Isomorphism code.
Here are the
Courageous Ones, who registered:
(Click for a larger version. Which student has spinach in his teeth?
[Perhaps it is visible in the photo at page-bottom?])
Various math czars who help out.
Chalk | Phone | Time | Computer/Proj | Blackboard | Humor | E-Problems |
---|---|---|---|---|---|---|
Dillon | Baker | Hannah! | Thom | everyone | me | Jackson & James G. |
Spring 2011, NT&Crypto:
This was a 1-semester course (Spring of 2011) for students who have had the rudiments of Number Theory, and would like to learn more, and to study applications of NT to Mathematical Cryptography, and to Coding in general [i.e, data-compression codes, isomorphism codes].
Our 2011g semester schedule (txt).
The Cryptography syllabus has important URLs and eddresses, and a partial topic-list It also mentions the Class photo Day, and letters-of-recommendation.
Various math czars who helped the course run smoothly.
Time | Projector | Blackboard | Chalk | Humor | E-Probs |
---|---|---|---|---|---|
Kaitlin | Julius & Jay | Kyle | Trevor | Kyle | Jay & ? |
Autumn 2007, NT & Elliptic curve Cryptography:
The prerequite material can be learned in a few weeks. It is knowledge of:
Modular arithmetic. Euclidean algorithm for the greatest common divisor of two integers. Euler phi-function and Fermat's Little Theorem. The Legendre and Jacobi Symbols. The statement of the Quadratic Reciprocity Theorem.
All of this is in any standard beginning Number Theory book, e.g,
Strayer or
Silverman (A Friendly Intro to NT
)
or Burton. It is also in chapters 1, 2, and 4.1-4.3
in Shoup's free online text
(linked further below),
together with the following Wikipedia pages:
Author: | Samuel Wagstaff | ISBN: | 978-1584881537 |
Year: | 2003 | Publisher: | Chapman & Hall |
A Computational Introduction to Number Theory and Algebra, by Victor Shoup. The author has made freely available a PDF copy of his text for personal use.
Among other nice features, Shoup's text has a description+proof of the Polynomial-time Deterministic Algorithm (AKS primality test) for testing whether a positive integer is prime.
Elliptic Curves: Number Theory and Cryptography, by Lawrence C. Washington.
Students registered for the graduate version of this course, MAT6905 and MAT6910, may want to purchase this text. I have put a copy on reserve at the Marston Science Library.
Voila ze practice Class-A (pdf) exam.
The spiffy Home-A (pdf), is available. (Was due Friday, 12Oct2007.)
General gaity and acclaim greeted the taut Class-A (pdf) with its clean lines, and minimalistic two-tone format. The critics effused over the 4-congruence problem, and were lifted to new heights by Hensel's lemma. In contrast, neither Puffman nor Huffman blew the house down…
Baby-Step Giant-Stepassignment (due Monday, 05Nov2007). Available is a typeset version of problem 4.4 (pdf).
Two paws upsays renowned math-animal critic Archimedes Salamander. A Smash Hit!
Chalk | Blackboard | Time | Phone-list |
---|---|---|---|
Jackie | Zach | Cameron | Catherine |