Instructor: W. Edwin
Clark
Office Location: PHY
326 A
Phone: 974 9559
Email: eclark@math.usf.edu
( I read my email frequently.)
Homepage: http://www.math.usf.edu/~eclark/
(This information will be
on my homepage in case you lose it. You may also go there if you are curious
about my research and academic genealogy.)
Office Hours: TR 2:30-3:25
and 4:50-5:50. (Also, immediately after class or by appointment.)
Text: I will make available notes for the class. Unless the class is very large, I will hand out copies of my notes in class. I prefer that students who are not able to attend on a given day make arrangements for a classmate to pick up a copy of any handouts. The assigned text for the course is Elementary Number Theory, by James K. Strayer. This book is rather expensive and I will teach the course in such a way that purchase of the book will not be necessary. However, the material I cover will be closely related to the material in the first few chapters of this book. On the other hand there are many books in our library on the subject of number theory which you may find useful if you feel the need for material not in my lectures and notes.
Course Objectives: To cover the following material: Basic properties of the integers. Divisibility and factorization: this includes prime number, greatest common divisors, the Euclidean Algorithm and the Fundamental Theorem of Arithmetic. Congruences: this includes modular arithmetic, linear congruences, Wilson's Theorem, Fermat's Little Theorem, pseudo primes, Euler's Theorem and the Chinese Remainder Theorem. Arithmetic functions: this includes the Euler phi funtion, the number of positive divisors function, the sum of positive divisor functions, perfect numbers and Mersenne primes. Miscellaneous additional topics:This will include: the RSA public key cryptographic scheme, primitive roots, and other material as time permits.
HOMEWORK: Homework will be assigned frequently. Students will be responsible for knowing how to work correctly all assigned problems. Homework will be collected each Tuesday unless otherwise announced in class. All assigned problems will be collected, but only a few randomly selected problems will be graded. Students should ask in class about problems they are unsure of -- after the homework has been graded. If a given problem is not solved completely significant effort shown on the homework paper will count for full credit.Such effort includes writing down of all definitions involved in the statement of the problem, writing down all previous material related to the statement of the problem, and working out a number of typical examples related to the problem. I will drop the two lowest homework grades.
EXAMS and QUIZZES:
1. Tuesday Quizzes: On each Tuesday, unless there is a holiday, a quiz will be given at the beginning of class. This quiz will cover definitions and statements of named theorems presented in class any time prior to the quiz. The quizzes will also cover examples from class and simple computations that will be easy for those doing their homework. There will be no makeups for student who are late or fail to take a quiz. However, I will drop the lowest 2 quiz grades .
2. Exam 1: Tuesday, September 26.
3. Exam 2: Thursday, October 26.
4. Exam 3: Thursday, November 30.
5. Final Exam: Thursday, December 14, 3:30-5:30.
COURSE GRADES: I will calculate the average of the grades on the Tuesday Quizzes, Homework, Exams 1, 2 and 3. Your course grade will be based on the maximum of this average and your Final Exam grade. Instead of having makeup exams, the Final Exam will serve as a makeup of any of the missed other exams. I will use the following scale to assign plus/minus letter grades
98-100 = A+, 93-97 = A, 90-92
= A-,
88-89 = B+, 83-87= B, 80-82
= B-,
78-79 = C+, 73-77 = C, 70-72=C-,
68-69 = D+, 63-67 = D, 60-62
= D-,
0-59 = F.
Thanksgiving Holiday: Thursday and Friday, Nov. 23 and 24.
The last day of classes
is Friday, December 8 , 2000.
[the following was added May 2001]
RSA Security, has revamped its Factoring Challenges.
Prizes now start at US$10,000 (factorization of a 576 bit modulus) to US$200,000 (factorization of a 2048 modulus).
RSA and its predecessor companies have been sponsoring factorization challenges for many years, but until now the prize money has been nominal. It is hoped that the increased bounties will draw more people to the field, and spur new research.
For details, including the challenge numbers, see:
http://www.rsasecurity.com/rsalabs/challenges/factoring/index.html
Peter Trei, Cryptoengineer, RSA Security Inc., ptrei@rsasecurity.com
Breaking News: 233-digit SNFS factorization
The Cabal announces the completion, on November 14, 2000, of the factorization with the Special Number Field Sieve(SNFS) of the 233-digit Cunningham number 2^773 + 1 into the product the numbers 3 and 533371 and three primes of 55, 71, and 102 digits, respectively. This establishes a new record for the Special Number Field Sieve. [Note that this is somewhat easier to factor than a number of this size which is the product of only two primes of approximate equal size. In this case the 3 and 533371 factors were easy to find. And the remaining factor has the small 55-digit and 71-digit primes.]
The sieving was done on about 150 SGI workstations and Sun workstations and servers running at 180-450 MHz, and on about 100 PCs running at 266-600 MHz. The sieving took about five calendar months. It was started mid-April, 2000, and finished on September 15, 2000. Total sieving time was 57.4 CPU years.
The previous SNFS record was the 211-digit repunit number 10,211- = (10^211 - 1)/9, factored on April 8, 1999, also by the Cabal.
Factorization details are available from: ftp://ftp.cwi.nl/pub/herman/SNFSrecords/SNFS-233.
Maple Worksheets: Students may download the following Maple worksheets. To do so hold down the right mouse button (on a Mac just hold down the single mouse button) the select Download file to disk or Save file to Disk. Then you should be able to open the file with Maple. You might open Maple first and then while in Maple choose Open from the File menu item.
RSA
Examples with Maple
Maple
Introduction for Number Theory
1. Exam #3 will cover pages 99 --156. Material in Section 28, Introduction to Maple, will not be on the exam unless discussed previously in pages 99-156.
2. As usual students should make sure they can work all exercises on pages 99-156.
3. Students should be able to state all definitions and named theorems on pages 99-156.
4. Be sure you know throughly the RSA Public-Key Cryptographic Scheme and how to implement it using Maple. (You may be asked how to do something in Maple on the exam, but Maple will not be used on the exam.)
5. In additon to the proofs assigned as exercises in the notes, also be able to give the proofs of Theorems 22.5 and 24.1.
Tuesday Quiz:On Tuesday, November 28, there will not be a quiz since there have been no definitions per se in the notes since the last quiz.
Homework: Homework exercises from Section 26 to the end of the notes on page 176 will be collected on Tuesday, November 28. I will count this as two assignments for grading purposes. The Maple worksheets will be one assignment and the rest will be another assignment.
Course Evaluation:
The course evaluation forms will be administered on Tuesday, November 28.
Please think about any ideas you might have about how the course could
be improved and let me know in person, via email, or anonymously on the
back of the course evaluation form.