- Zoom Meeting Links:
- Extra Homework Problems
- Homework Problems
- Canvas: important announcements, grades, calendar, etc.
- Piazza (Discussion Boards).
- Instructor Contact and General Info:
- Course Description and Information:
- Zoom -- NEW!
- Legal Issues:
- Additional Bibliography
Instructor Contact and General Information
|Office:||Ayres Hall 251|
|Phone:||974-1321 (don't leave messages! -- e-mail me if I don't answer!)|
|Office Hours:||MW 11-12, or by appointment via Zoom.|
|Textbook:||J. Hoffstein, J. Pipher, J. H. Silverman. An Introduction to Mathematical Cryptography, 2nd edition, Springer, 2014.|
|Prerequisite:||Math 251/257 or Math 200.|
|(Math 300/307 or COCS 311 recommended, but not required).|
|Class Meeting Time:||MWF 2:30-3:20
|Grade:||Simply your HW (computer projects) grade.|
|See here for letter grade ranges.|
This course is a one-semester introduction to applied and computational number theory. We will study many algorithms used in number theory and applications to, mainly, computer security.
Although number theory started as primarily abstract subject, today it has quite important applications. Although we will often discuss the theoretical aspects of it, our main focus will be in the computational problems and applications of the subject.
This is an experimental course, so the content will be shaped as we progress, with input from the students!
Chapters and Topics
We should cover:
- Math Background: Basic properties of integers. Prime numbers and unique factorization. Congruences, Theorems of Fermat and Euler, primitive roots. Quadratic Reciprocity. Finite Fields.
- Basic Number Theoretic Algorithms: Euclidean Algorithm, Modular Exponentiation. Primality testing and factorization methods. Determining squares and taking square roots modulo $p$ and $p^n$.
- Cryptography: Basic notions. Diffie-Hellman Key Exchange. Public key cryptosystems, including Elgamal, Elliptic Curve (discrete log), and RSA. Implementation and attacks. Lattice based cryptosystems (if time allows).
- Digital Signatures: RSA, Elgamal, Digital Signature Algorithm (DSA), and Elliptic Curve DSA.
Here is a likely list of sections from the textbook:
- Chapter 1: Sections 1.2 to 1.5.
- Chapter 2: Sections 2.1 to 2.9.
- Chapter 3: Sections 3.1 to 3.9. (In 3.7, quadratic sieve only). (We will also include discussions on how to take square roots modulo $p$ and $p^n$, for $p$ prime.)
- Chapter 4: Sections 4.1 to 4.3.
- Chapter 6: Sections 6.1 to 6.4 and 6.6 to 6.7. (We will also include a discussion on finite fields.)
- Chapter 7: If time allows.
If a significant number of students have taken (or intend to take) COCS 483 (Applied Cryptography), or if students interests lie outside cryptography, we might deemphasize it (although we will surely see some) and concentrate more on number theoretical algorithms, or even choose other topics to replace it.
Before the first real assignment is due, we will practice it with a "dummy assignment". I will likely show you in class how we will do it, or maybe post a video. (Likely both, as I will try to record our dry run in class.)
Most HW problems will contain some code to test the routines you wrote. Successfully running this tests will, in most cases, give you full score, unless you are breaking some rules, like using a built in function you are not allowed to use, for instance. I will also look for any other errors that might escape the tests, but in most cases, you should get full credit (usually 4 points per problem).
If your code fails to pass the test, but I cannot spot the error, you will lose only 0.5 out of 4 (unless I have any other reason to deduce points). If you do care to know what is actually wrong with it, let me know and I can spend some more time figuring it out.
In the other cases your grade will depend on how far you were from the correct solution.
Your course grade will be simply your HW grade.
I will also post extra problems, some theoretical, for those interested. These will not be collected or graded, but I strongly recommend you work on them for a deeper understanding. These will be posted on the section Extra HW Problems below. (Arrangements can be made for those to count as extra-credit also.)
Assignments are individual! You can work with someone else and ask for help, but you should be able to understand the ideas and write your own code!
Also, it should go without saying, that you cannot copy code you find in the internet. It is usually easy to spot these and you will be penalized for doing it! If you are having a hard time, ask me (or a colleague) for help instead.
Sage is a (free) open-source math software. It was started by William Stein and was built on top of many other open-source software, such as GP/Pari, Maxima, GAP, R, and many more. It's intent is to offer an open-source alternative to Mathematica, Maple, Matlab and Magma.
Since Stein is a number theorist, Sage is particular strong in number theory, and it's the most suitable to our course. Moreover, it's free and it can be used directly in Cocalc, which we will use for HW. So, students don't even have to download it (although it might be a good idea.) In fact, Cocalc was originally named "SageMathCloud", i.e., it was built to run Sage on the cloud. Also, Sage is built on top of Python, and so it has the same syntax and can load the numerous Python libraries.
Cocalc, originally called "SageMathCloud", is an online computing environment. It was first created to use Sage (and its components) online, without the need of installation, and allowing users to share and collaborate. I has expanded considerably since then, and today it can be even used for course management, as we will use here.
It has many features and it is quite powerful, but we will need only the basics. As mentioned above, it will be used to assign and collect HW sets. You can do all your work directly on Cocalc (using Sage), or you can install Sage in your personal computer and do the coding/testing there, and then just copy and paste in Cocalc.
You can use Cocalc for free, although it might be a bit slow. It should not be a problem as your work should not be very resource intensive. But, if you feel it is too slow, you can either install Sage in your personal computer (it's free and open-source) or pay for a subscription.
I truly don't expect that it will be necessary for anyone to pay for the subscription, but if it comes to that, we can discuss what would work better. Either students can buy their own personal subscriptions or I can try to set up a Small Course Package.
Piazza (Discussion Board)
We will use Piazza for online discussions. The advantage of Piazza (over other discussion boards) is that it allows us (or simply me) to use math symbols efficiently and with good looking results (unlike Canvas). It also allows anonymous posts (also unlike Canvas).
To enter math, you can use LaTeX code. (See the section on LaTeX below.) The only difference is that you must surround the math code with double dollar signs ($$) instead of single ones ($). Even if you don't take advantage of this, I can use making it easier for you to read the answers.
It also allows us to enter code in Code Blocks. Please use code blocks whenever entering code!
You can access Piazza through the link on the left panel of Canvas or directly here: https://piazza.com/utk/spring2020/math499/home. (There is also a link at the "Navigation" section on the top of this page and on the Links section.)
To keep things organized, I've set up a few different folders/labels for our discussions:
- Math: Math questions.
- Code: Questions about coding, including syntax and algorithms.
- Course Structure: Ask questions about the class, such as "how is the graded computed", "when is the final", etc. in this folder. (Please read the Syllabus first, though!)
- Feedback: Give (possibly anonymous) feedback about the course using this folder.
- Other: In the unlikely event that your question/discussion doesn't fit in any of the above, please use this folder.
I urge you to use Piazza often for discussions! (This is specially true for Feedback!) If you are ever thinking of sending me an e-mail, think first if it could be posted there. That way my answer might help others that have the same questions as you and will be always available to all. (Of course, if it is something personal (such as your grades), you should e-mail me instead.)
Note that you can post anonymously. (Just be careful to check the proper box!) But please don't post anonymously if you don't feel compelled to, as it would help me to know you, individually, much better.
Students can (and should!) reply to and comment on posts on Piazza. Discussion is encouraged here!
Also, please don't forget to choose the appropriate folder(s) (you can choose more than one, like a label) for your question. And make sure to choose between Question, Note or Poll.
When replying/commenting/contributing to a discussion, please do so in the appropriate place. If it is an answer to the question, use the Answer area. (Note: The answer area for students can be edited by other students. The idea is to be a collaborative answer. Only one answer will be presented for students and one from the instructor. So, if you want to contribute to answer already posted, just edit it.) You can also post a Follow Up discussion instead of (or besides) an answer. There can be multiple follow ups, but don't start a new one if it is the same discussion.
Important: Make sure you set your "Notifications Settings" on Piazza to receive notifications for all posts: Click on the gear on the top right of the Piazza site, the choose "Account/Email Setting", then "Edit Email Notifications" and then check "Automatically follow every question and note". Preferably, also set "Real Time" for both new and updates to questions and notes. I will consider a post in Piazza official communication in this course, I will assume all have read every single post there!
You can also use Piazza for Private Messages. I'd prefer you use e-mail to talk to me, unless it is a math question (in which either you or I would need to enter math symbols) that cannot be posted for all (such as an exam question). You can also send private messages to fellow students, but keep in mind that I can see those too! (So, not really that private...)
You should receive an invitation to join our class in Piazza via your "@tennessee.edu" e-mail address before classes start. If you don't, you can sign up here: https://piazza.com/utk/spring2020/math499. If you've register with a different e-mail (e.g., @vols.utk.edu) you do not need to register again, but you can consolidate your different e-mails (like @vols.utk.edu and @tennessee.edu) in Piazza, so that it knows it is the same person. (Only if you want to! It is recommended but not required as long as you have access to our course there!) Just click on the gear icon on the top right of Piazza, beside your name, and select "Account/Email Settings". Then, in "Other Emails" add the new ones.
Communications and E-Mail Policy
You are required to set up notifications for Piazza (as explained above) and for Canvas to be sent to you immediately. For Canvas, check this page and/or this video on how to set your notifications. Set notifications for Announcements to "right away"! (Basically: click on the the profile button on left, under UT's "T", then click "Notifications". Click on the check mark ("notify me right away") for Announcements.)
Moreover, I may send e-mails with important information directly to you. I will use the e-mail given to me by the registrar and set up automatically in Canvas. (If that is not your preferred address, please make sure to forward your university e-mail to it!)
All three (notifications from Piazza, notifications from Canvas and e-mails) are official communications for this course and it's your responsibility to check them often!
Please, post all comments and suggestions regarding the course using Piazza. Usually these should be posted as Notes and put in the Feedback folder/label (and add other labels if relevant). These can be posted anonymously (or not), just make sure to check the appropriate option. Others students and myself will be able to respond and comment. If you prefer to keep the conversation private (between us), you can send me an e-mail (not anonymous), or a private message in Piazza (possibly anonymous).
Starting on Monday 03/23 our classes and office hours will all be through Zoom. (The links are avaliable in the Syllabus on Canvas.)
Before our first lecture on 03/23, please familiarize yourself with Zoom. At the very least, read the Getting Started and Best Practices for Participants pages from OIT. See also Remote It: Just for Students.
Please login to your account and test the microphone and camera before class.
I will be online on Zoom at around 2:15pm on our first day (03/23) in case you want to login early and check if everything is working, but the actual class starts at 2:30 as usual.
The classes will be live, so you should plan to be "present" during those meetings. On the other hand, the classes will be recorded and posted on Canvas for later viewing or in case you had to miss it.
Instead of writing on the board, I will go over prepared notes or computer presentations with Sage/Jupyter Notebooks. These will be available on Canvas (or Cocalc) ahead of time, so you can download them and see them in your own computer. Revised notes might be posted (also in Canvas) if we found any mistakes or problems.
For questions you asked during lectures (for which I don't have prepared notes), I will type an answer live (using LaTeX). I am not very fast at all typing, so this might be a bit slow. I will type just enough that, together with my explanations, all can follow. After class I will edit this document (to make it more readable) and post it as a PDF in Canvas for future reference.
The notes, videos, and PDF for questions can be found in Canvas by (after selecting our course) clicking on "Pages" on the left panel and then on the link for the date's lecture.
Office Hours will also be via Zoom.
Note that office hours will not be recorded! You can record it yourself if you want to or request me to do it, but I will not do it by default (unlike our lectures).
Remember that our office hours are MW (not Fridays) from 11 to 12. (I actually teach another class until 11, so it's more likely it will be from 11:10 to 12:10). I should be logged in Zoom during those times, but keep in mind I may walk away for a bit if no one is there. I should not be away for long, so you can wait a little. If you don't see me, feel free to turn on your microphone and ask for me. (In case I fall asleep.) But please be a little patient if I don't respond, as I should be back soon.
Although not necessary in principle, if you let me know you will come to office hours (and at what time exactly), I can make sure to not be away at that time.
Also, I can take appointments for office hours at different times if necessary. In that case, please write me to make an appointment, but use the same Zoom link as for regular office hours.
Keep in mind that these office hours are shared with another course I'm teaching.
Here are some notes about how we will handle the lectures:
- Please, keep your microphones on mute! If you have a question, please raise your hand. You can turn on your mic and ask your question after I call you. Please do not forget to turn it off after I answer your questions.
- You can also ask questions via chat. (These can be private, i.e., to just me.) I've missed some of those in the past (I'm not sure I get a sound notification when I get a message), but I will try to be more careful this time. But, if I don't answer a question you sent via chat, please raise your hand.
- If possible, please turn on your cameras. It helps me to see your faces to see if you look confused or content. It's very hard to "read the room" in Zoom. But you certainly are not required to have your camera on.
- Important: For the same reason above, I beg you to please use non verbal feedback as often as possible! This will help me have a better idea if I need to explain something more carefully or slow down/speed up. Please use it!
Study, preparation, and presentation should involve at all times the student’s own work, unless it has been clearly specified that work is to be a team effort. Academic honesty requires that the student present their own work in all academic projects, including tests, papers, homework, and class presentation. When incorporating the work of other scholars and writers into a project, the student must accurately cite the source of that work. For additional information see the applicable catalog or the UT Libraries site. See also Honor Statement (below).
"An essential feature of the University of Tennessee, Knoxville, is a commitment to maintaining an atmosphere of intellectual integrity and academic honesty. As a student of the university, I pledge that I will neither knowingly give nor receive any inappropriate assistance in academic work, thus affirming my own personal commitment to honor and integrity."
You should also be familiar with the Classroom Behavior Expectations.
We are in a honor system in this course!
Students with disabilities that need special accommodations should contact the Student Disability Services and bring me the appropriate letter/forms.
Sexual Harassment and Discrimination
Please, see also the Campus Syllabus.
Here are some other books, besides out text, that you might find helpful:
- W. Trappe and L. C. Washington, "Introduction to Cryptography with Coding Theory", 2nd Ed., 2006, Pearson. Another good book! (I almost chose it as our main text.)
- H. Cohen "A Course in Computational Algebraic Number Theory", Springer, 2000, and Advanced Topics in Computational Number Theory, Springer, 2000. These are not textbooks, but more like reference books. They are way more advanced than we need, dealing with many topics that we will not even come close to touch, but are, most likely, the "bible" on the subject. (Cohen is the creator of GP/Pari.)
- W. Stein, "Elementary Number Theory". (Freely available.) This is more of traditional number theory book, but was written by the creator of Sage, and has many computations using it. It does show the RSA cryptosystem, though, and serves as a very good (and free) reference to elementary number theory and some of the more theoretical aspects we will use.
- V. Shoup A Computational Introduction to Number Theory and Algebra, 2nd Edition, Cambridge, 2008. A freely available book that many algorithms.
- S. Y. Yan, Number Theory for Computing, Springer, 2000. I am much less familiar with this book (just found it in the library), but seems interesting. Although I still prefer our text or the first reference above for our course, it seems to offer many algorithms, which I might use when teaching.
- D. Welsh, "Codes and Cryptography", 1988, Oxford. Another good reference (covering also coding theory).
This is not necessary to our class! I leave it here in case someone wants to learn how type math, for instance to type their HW. But again, you can ignore this section if you want to.
LaTeX is the most used software to produce mathematics texts. It is quite powerful and the final result is, when properly used, outstanding! Virtually all professional math text you will ever see is done with LaTeX, or one of its variants.
LaTeX is freely available for all platforms.
The problem is that it has a steep learning curve at first, but after the first difficulties are overcome, it is not bad at all.
One of the first difficulties one encounters is that it is not WYSIWYG ("what you see is what you get"). It resembles a programming language: you first type some code and then this code is processed to produce a nice document (a non-editable PDF file, for example). Thus, one has to learn how to "code" in LaTeX, but this brings many benefits.
I recommend that anyone with any serious interest in producing math texts to learn it! On the other hand, I don't expect all of you to do so. But note that there are processors that can make it "easier" to create LaTeX documents, by making it "point-and-click" and (somewhat) WYSIWYG.
Here are some that you can use online (no need to install anything and files are available online, but need to register):
- Cocalc (Previously known as "Sage Math Cloud". This one is much more than just LaTeX, and will be used in our course.)
If you want to install LaTeX in your computer (so that you don't need an Internet connection), check here.
A few resources:
- Here is a video I've made where I talk about LaTeX and producing documents with it: Introduction to LaTeX and Sage Math Cloud. (Again, note that "Sage Math Cloud" is simply the old name for Cocalc. The video does not show it in great detail, but might be enough to get you started.) Note it was done for a different course, so disregard any information not about LaTeX itself.
- TUG's Getting Started: some resources, from installation to first uses.
- A LaTeX Primer by D. R. Wilkins: a nice introduction. Here is a PDF version.
- Art of Problem Solving LaTeX resources. A very nice and simple introduction! (Navigate with the links under "LaTeX" bar on top.)
- LaTeX Symbol Lookup: Draw a symbol and the app will try to identify it and give you its LaTeX code.
- LaTeX Wikibook: A lot of information.
- LaTeX Cheat Sheet.
- Cheat Sheet for Math.
- List of LaTeX symbols.
- Comprehensive List of Math Symbols.
- Constructions: a very nice resource for more sophisticated math expressions.
- Zoom Meeting Links:
- Piazza (Math Related Forum).
- Some of my Notes on Python. (For Python 2, or Sage version before 9.0, see my Notes on Python 2.)
- UT Knoxville Home
- UTK's Math Department.
- Services for Current Students and MyUTK (registration, view your grades, etc.).
- Office of the Registrar
- Academic Calendars, including dates for add and drops, other deadlines, final exam dates, etc.
- Students Disability Services
- Office of Equity and Diversity (includes sexual harassment and discrimination).
- My homepage
Extra Homework Problems
These are not to be turned in! But they should be interesting and help you better understand the mathematical tools we use in the course.
Problems will be added as we progress.
- Let $N$ be a (possibly very large) positive integer. Prove
that there are $N$ consecutive integers $m$, $m+1$, ...,
$m+(N-1)$ such that none of them is prime. (In other words,
two consecutive primes can be very far apart!)
Hint: Use the following simple lemma. Let $a$, $b$ and $d$ be positive integers, with $d \mid a$. Then, $d \mid (a+b)$ if and only if $d \mid b$.
- Prove that
Conjecture (every even integer greater than or equal to 4 is a
sum of two primes) implies
WeakConjecture (every odd integer greater than or equal to 7 is
the sum of three primes).
(This is a very simple one.)
Section 1.2: 1.11, 1.13.
Section 1.3: 1.19, 1.20, 1.23, 1.24.
Section 1.4: 1.29, 1.31.
Section 1.5: 1.33, 1.35, 1.38.
Section 2.2: 2.3, 2.5.
Section 2.4: 2.9, 2.10.
Section 2.5: 2.12, 2.15.
Section 2.8: 2.20, 2.21(a), 2.25.
Section 2.9: 2.26, 2.27.
Section 3.1: 3.1(a), (b), 3.2, 3.5, 3.6(a).
Section 3.4: 3.14(a), (c), (d), 3.21.
Section 3.5: 3.23(c), (d), (e).
Section 6.1: 6.3.
Section 6.3: 6.9.
Section 6.4: 6.16(a).
Section 6.5: 6.9, 6.18.
Section 6.7: 6.25, 6.26, 6.27.
Section 3.9: 3.37, 3.38, 3.41.