The resources here provide an introduction to Python programming for those who have never programmed before. What makes this tutorial different from others is that the focus is on programming for number theoretic applications. So the tutorial will have very little on string manipulations, web-crawling, file I/O, etc., all of which are very important for other programming applications. But it will cover core imperative programming topics, including variables and data types, control statements, functions, and some fancier data structures (lists and dictionaries) and algorithms. The goal is to get to the point where one can carry out experimental number theory in a short time, investigating the distribution of prime numbers, implementing basic cryptosystems, etc. This Python tutorial is meant to accompany An Illustrated Theory of Numbers. Together they form an introduction to elementary number theory, with theoretical and computational techniques.
Besides the introduction you find on this page, the tutorial is composed of a series of Python (Jupyter) notebooks. These notebooks will allow you to read text, run programs, and experiment with Python, all within the comfort of your web browser (with or without internet connection). While Jupyter notebooks are not meant for extensive software development, they are excellent for experimental explorations and data science.
SAGE is an awesome open-source mathematical software system, with Python at its core. One might start programming with SAGE right off the bat, since it contains all the Python functionality we need, with the Jupyter notebook interface, and additional functionality for the research mathematician. The interested user might wish to set up an account on CoCalc to run SAGE in the cloud. Just about everything in these tutorials will run through SAGE too. You can read a bit about the relationship between SAGE and Python here, including some important differences in basic syntax.
But, we have not designed the tutorials for SAGE. Indeed, SAGE is a bit too powerful for what we want to accomplish. Instead, we build a basic number theoretic toolbox from scratch, using only vanilla Python (with a bit of Numpy). In this way, the tutorial makes the user learn to write programs rather than hunt for the appropriate SAGE command to accomplish a task. After this tutorial, the user will be well-prepared to begin programming in SAGE, and might better appreciate the incredible efforts that have created this powerful software package (as well as GAP, FLINT, and others). For those who wish to start with SAGE, there is an excellent tutorial at the SAGE homepage. William Stein, the designer of SAGE, also wrote a great elementary number theory book which takes a computational approach and uses SAGE throughout.
Our Python tutorial is composed of a series of Jupyter notebooks. Python is a programming language (like C, Java, Haskell, etc.) and Jupyter provides an interactive interface to Python that runs in your web browser.
A great way to get all this running on your computer is to download and install Anaconda. It is free, and works on Windows, Mac OS, and Linux. For these tutorials, make sure to download Python version 2.7 Python 3.x. We have included versions of these notebooks for Python 2.7 too, since it is still widely used. But let's get with the times and use Python 3 instead. For those teaching number theory, using Anaconda across the course will give students a more uniform programming experience, allowing them to work easily in groups, and preventing you from getting bogged down with tech support.
When you install Anaconda, you get Python for programming, Jupyter for the notebook interface, hundreds of other packages, and a nice "Anaconda Navigator" for starting everything up. These are the tools we will use. Among the Python packages, we will occasionally use NumPy for high-speed calculations, and matplotlib for data visualization. All of this will be installed when you install Anaconda.
After Anaconda is installed on your computer, run the Anaconda Navigator. Click the Launch button under Jupyter to launch a Jupyter notebook. This should open a tab in your web browser (and a little background window too). It's best to avoid Internet Explorer, but the other popular web browsers should be fine, e.g. Chrome, Safari, Firefox.
Once you have a tab open on your web browser for Jupyter, you can close down the Anaconda navigator if you want. In your Jupyter window, you should see a file directory. Click on directories to navigate to a convenient location, where you'll want to save your files. You can create a new folder, by clicking on New... Folder.
Use this folder for the whole tutorial. If you want to jump in and create your own Python notebook, you can go into your directory, then click on New... Python 3. This should open a new tab in your browser and you should see a prompt that looks like In [ ]:
To the right of the prompt, type 2 + 2 and then shift-Enter (hold down the shift key while you press the enter/return key). You should see a result like Out[1]: 4 and a new "cell" should appear below, ready for more input. If all this works, congratulations! Python and Jupyter are installed and you should be ready to go to the Notebooks below. You can rename your Python notebook by clicking on the "Untitled" name at the top and changing it. Then you can go to "File... Save and checkpoint" to save your notebook for later.
A Jupyter notebook is a file which contains both text and Python code. Jupyter notebooks are stored as files with the .ipynb extension. Before you begin with the notebooks, make sure that you have gone through the Getting Started steps above.
If this is your first time interacting with a Python notebook, begin by downloading the "My First Notebook.ipynb" file below and saving it in the directory where you'll be working on this tutorial. Then, launch Jupyter (through the Anaconda navigator), go to the directory of the notebook, and open it. Follow through the notebook to get used to working with Python and Markdown cells.
For learning to program, it's important to type code yourself! So a good way to proceed through later notebooks is to print out the notebooks first, and then to enter the commands in an empty Jupyter notebook. But to work with the notebooks directly, download the .ipynb files and open them in Jupyter.
Once you are used to working in a Jupyter notebook, you're ready for the Python tutorial below. If you just want to look at the notebooks, they are hosted on GitHub and you can read them online and print them through the Python Notebook Viewer. All Notebooks are free to download and edit via a GPLv3 license. If you have feedback about these notebooks, or wishes for future instructional notebooks, send me a note at weissman AT ucsc DOT edu.
Happy programming!
| Notebook | View Python 3 Notebook | Download Python 3 Notebook | View Python 2 Notebook | Download Python 2 Notebook |
|---|---|---|---|---|
| Introduction to the Jupyter notebook interface. Editing, inserting, and deleting cells. Executing code cells. A brief introduction to Markdown. Saving, loading, and printing notebooks | View/print notebook | Download My First Python 3 Notebook.ipynb | View/print notebook | Download My First Python Notebook.ipynb |
| Introduction to Python as a calculator, focusing on integer operations. Variables and basic data types (int, float, bool, string, list). The range command and for loops. | View/print notebook | Download P3wNTNotebook1.ipynb | View/print notebook | Download PwNTNotebook1.ipynb |
| Defining functions. Control statements (if/else), while loops. Basic string substitution. Implementation of the Euclidean algorithm, and the solution of linear Diophantine equations. | View/print notebook | Download P3wNTNotebook2.ipynb | View/print notebook | Download PwNTNotebook2.ipynb |
| Lists and some data analysis. List slicing and comprehension. Implementing the sieve of Eratosthenes. Optimization and the timeit tool. Data analysis (on the set of prime numbers) with a bit of matplotlib for visualization. | View/print notebook | Download P3wNTNotebook3.ipynb | View/print notebook | Download PwNTNotebook3.ipynb |
| Dictionaries and prime decomposition. Some generalities on Python objects and methods too, with examples from dictionaries and lists. Functions as objects, and the implementation of multiplicative functions. | View/print notebook | Download P3wNTNotebook4.ipynb | View/print notebook | Download PwNTNotebook4.ipynb |
| Modular arithmetic and primality testing. A closer look at algorithms and performance analysis. Pingala's algorithm for exponentiation (successive squaring) and an in-depth look at the Miller-Rabin primality test. | View/print notebook | Download P3wNTNotebook5.ipynb | View/print notebook | Download PwNTNotebook5.ipynb |
| Ciphers and Diffie-Hellman key exchange. Caesar and Vigenere ciphers. Working with strings and ASCII code in Python. An introduction to symmetric key cryptosystems. Modular exponentiation and the existence of primitive roots. Sophie Germain and safe primes. Diffie-Hellman key exchange. | View/print notebook | Download P3wNTNotebook6.ipynb | View/print notebook | Download PwNTNotebook6.ipynb |
| The RSA cryptosystem. Putting it all together -- Euler's theorem for modular exponentiation, primality testing for creating private keys, the Euclidean algorithm for modular inverses. Some issues of implementation, including random key generation and the web of trust. How to use RSA for encryption, as well as for digital signatures. | View/print notebook | Download P3wNTNotebook7.ipynb | View/print notebook | Download PwNTNotebook7.ipynb |
There are lots of online and print resources for Python programming. This is a short list.