This is a worksheet to introduce Sage and Python to undergraduates taking a first cryptography course, and not necessarily having any programming background. Students should know the concepts of prime factorization, caesar cipher and modular arithmetic, for the purposes of examples.
Created by Katherine E. Stange
(I release this work to the public domain; feel free to use and adapt. I don't mind if you let me know it was useful, though, or provide feedback.)
Section 1: Overview of Interacting with Sage
This is a "notebook" where you type commands and see the results. Sage runs on the underlying programming language Python. To get started, ask Sage what is 2+2 by clicking on the cell and hitting shift+enter. This "evaluates" the cell.
4 4 
Your turn. Find out what is $(5 \cdot 2^{10}+3)/47$. In Python, exponents are typed like this: 2^3 = 8, and multiplication is typed like this: 2*3 = 6.
(Hint: the answer should be 109.)

An important thing to know about Sage is that it has variables which are stored throughout the notebook. To save a value into a variable name (to "assign a value to the variable"), e.g. save the value 3 into the variable "mynumber", you do this:

Sage doesn't actually print out anything in response to that, but now the name "mynumber" will return 3 if you use it. Ask Sage, what is mynumber+3?
6 6 
Sage is full of inbuilt number theory functions. Here are some selfexplanatory examples (please always evaluate each example cell as we work through this notebook):


It's important to know the alternate format for calling a function on an object:

Another important thing to know is how to check equalities or inequalities. Try these out:




Did you notice the double ==? That is for "comparison" (meaning the answer is true or false, they are equal or not equal). (You used a single = to assign a value to a variable when you defined mynumber. Don't forget the difference.)
Now please determine whether $\gcd(36,54)$ is larger than $19$, or not. Write something which will evaluate to True or False. The syntax for $\gcd$ is just gcd(36,54). (If you need a refresher, gcd = greatest common divisor, the biggest integer dividing both numbers.)

Section 2: Figuring out Sage Functions
Oftentimes, you will want to find a function you know should exist. There are a few really good strategies:
(1) Tab completion for functions. If you type the beginning of the name of a function, then hit tab, the possible functions that start that way appear.
Try it now here. Note, you can hit "escape" to get out of the menu that appears.

(2) Tab completion for objects. Once you have defined something, it has all kinds of things you can do to it. Type the thing's name, followed by a period, and hit tab to see your options.
Try it now here. Note, you can hit "escape" to get out of the menu that appears.

Now experiment with using some of the functions that appeared on mynumber, and see if you can guess what they do.

(3) Question mark. If you have a function, and you want to see the documentation for that function, type a question mark after the function, shiftenter, and Sage will pop up info.
Try it here:
File: /usr/local/sage8.4/sage/local/lib/python2.7/sitepackages/sage/arith/misc.py Type: <type ‘function’> Definition: factor(n, proof=None, int_=False, algorithm=’pari’, verbose=0, **kwds) Docstring:

(4) Google search. Make sure to use the words "sage math" in the search if you are having trouble. If what you are searching is really about programming, not math, then use the keyword "python" (the underlying programming language for Sage).
Okay, now that you have some strategies for figuring out how to discover Sage's inbuilt functions, use them to figure out how to compute the list of divisors of mynumber. (Hint: the answer should be [1,3].)
[1, 3] [1, 3] 
Section 3: Modular Arithmetic
You can do modular arithmetic in Sage, which looks like this:

That's fine for a oneoff computation. But what if we really want to play with integers modulo 7 a lot? We can work in the integers modulo 7 by defining the ring (number system) itself as an object. Here's how I would do that, and assign it to the name "R":

From now on, Sage knows the name "R" refers to the integers considered modulo 7.
Now I just wrap my integers in R (by this I mean write R(3) instead of just 3 etc.) and Sage will know that I want them to be thought of as integers modulo 7. Then I can do all kinds of math, just using those!


I can even take the inverse of something Mod 7.

Let's double check that last result is correct. Multiply the answer you got by 2 (working in R) and make sure you get 1.

Section 4a: Basic Intro to Programming  For Loop
Sage can do programming. The simplest thing you might want to do as far as programming is to repeat something a bunch of times. See if you can parse the following code and guess what it will do. Then, run it and see.

Now, using the same idea, make Sage print the inverse of every possible value Modulo 7. Use a "for loop" like the last example.

Next challenge: use a for loop to do the following for every n in the range 10 to 20:

Section 4b: Basic Intro to Programming  If
Here's an example of the syntax for checking with an if statement, as well as printing a result.

Use a for loop with an if statement to print out all the primes in the range from 1 to 30.

Now here's your next challenge: find all the twin primes up to 1000, and print them out. A twin prime is a prime number p such that p+2 is also prime.

Section 4c: Basic Intro to Programming  Using a variable
Now remember we learned we can create variables. Create a program that will compute i(i+1)(i+2) for each integer i from 1 to 5, and assign the result to a variable called product, and then print product. It should print out five numbers (they should be 6, 24, 60, 120 and 210).

Now copy the program above and modify it as described here. Create a program that will compute i(i+1)(i+2) for each integer i from 1 to 5, and then print the result modulo n for each n from 1 to 5. To accomplish this, as before, assign the product i(i+1)(i+2) to a new variable product, so that you only need to write out the formula for it once and afterward can call (meaning, reference or use) that variable as you print out all its residues mod n. Hint: the result, if you've done it correctly, should print 25 numbers, all 0's except one 2. (Weird!)

Section 5: Creating Functions (and rational numbers)
You can create your own functions. Here's an example.


Here's a more complicated example, which computes the mediant of two fractions. The mediant of a/b and c/d is (a+c)/(b+d). (This is not the correct way to add fractions! But it has its uses.)


Your challenge: create a function adds_to_zero( x, y ) which returns True if x and y add to 0 and False otherwise.

Section 6: Lists
One of the most useful things in Python is lists. A list is a list of objects, e.g. a list of numbers. You can manipulate lists to do all manner of things. Here's how you define a list:

Here's how you get the an element from a list. The first element is "element 0", the second element is "element 1" and so on (weird, I know). After running this code, modify it to pull out the element "3" instead.
1 1 
You can even pull out a range of your list (remember, the notation is inclusive on the left and not on the right). After running the code below, modify it to pull out the sublist [3,4,5].
[2, 3] [2, 3] 
You can define lists very compactly (avoiding making for loops). For example:


Side tip: The syntax range(a,b) which we've been using actually just returns a list: the list of all the integers starting with a and ending with b1. Try it:
[1, 2, 3, 4, 5, 6, 7, 8, 9] [1, 2, 3, 4, 5, 6, 7, 8, 9] 
Your turn. Make a list of the values of x modulo $11$, for x in the range of 1 to 100. Assign it to the variable name mymodlist.

Now print out the 11th term of your list.

Section 6b: Graphing
You can graph data easily in sage by sending a list to the function list_plot.

Now draw a graph of mymodlist, the list you made in the last section. Don't create it again; just reference the variable.

Section 7: Lists and Strings
String are treated a lot like lists in in Python. Here's a string and how you can pull out any one character or substring.

Your turn! Create a string that has a hidden word in it, and then print out that substring using the method demonstrated above.

A pretty useful trick is to look up the first occurrence of a character or entry in a string or list.

You can also make an empty list with []. You can add things with append().

You can make an empty string with "" or ''. You can add things to it with +=.

The "+=" thing also works for numbers.

Make an empty string and use += in a loop to create the string "0123456789". Hint: you can use str() to change a number into a string.

Now use the "index" function demonstrated above to look up the first occurence of the character "4" in your string.

One more useful thing: the length of a string or list.

Section 8a: Matrices
Here's how you can make matrices. They don't look great when printed, so there's a command "show".

You can add matrices.

Figure out how to multiply matrices.

You should think of a vector just as a matrix with only one column (or one row). For example, to evaluate a matrix on a vector, you might do the following:

You can also define matrices over a ring of integers modulo n. Notice how the syntax for the matrix provides Sage the information that you want it to consider the entries in the appropriate ring. Two of these are matrices with entries mod 26. One of them has just integer entries. You can't tell the difference with show(). (Hint: if you really want to know the difference sometime, try parent().)

Now figure out how to compute the inverse of M.

What's the inverse of N? (Hint: this won't work! Why?)

Now the inverse of P? Notice this is asking a different question than the inverse of N, because we are working in a different ring.

Now compute and print the determinants of N and P. Why are the answers what you expect?

Section 8b: Matrices and Matrix Plots
Another really useful graphical method is matrix_plot, which will plot data from an array. First, I'll show you how to make a matrix (this one is 7x7 with entries in the integers, which Sage refers to as ZZ). This matrix is just full of zeroes by default.

Here's how you get one entry of your matrix:

Now I will populate my matrix with an addition table modulo 7.

First, let's print the matrix:

And now let's "plot" it.

Section X: Challenges
Here's a series of challenges for you to practice the skills you learned above and learn new ones. Read through them first and pick the ones that interest you.
Challenge 1:
Create a list of all the primes up to 100 which are 1 modulo 12. Hint: you could use is_prime() or you could use primes().

Challenge 2:
Find all the 3character substrings of the string "toboldlygowherenoonehasgonebefore" that begin with the character "o".

Challenge 2:
Lists can be useful for storing the results of a computation. Use a loop to create and store all the caesar shifts of the word "fuzzy".

Challenge 3:
Create a function that, given $n$, will return those residues modulo $n$ which are squares.

Challenge 4:
Find all the primes up to 100 which are sums of two integer squares (e.g. $5 = 1^2 + 2^2$ but 7 has no such expression).

Challenge 6:
Use matrix_plot to show, in a square grid 100x100, which pairs of integers are coprime (coprime means gcd=1).

Challenge 7:
Make Sage output a LaTeX table suitable for cutting and pasting into your homework (there are inbuilt functions for this!), showing the multiplication table for integers modulo 13.

Challenge 8:
Given the beginning of "Tale of Two Cities" by Charles Dickens, given below, obtain the version of this string containing just its alphabet characters. Then, perform a frequency analysis. That is, output a list whose nth entry is the frequency of the nth letter of the roman alphabet in the string. Finally, graph the result.
It was the best of times,
it was the worst of times,
it was the age of wisdom,
it was the age of foolishness,
it was the epoch of belief,
it was the epoch of incredulity,
it was the season of Light,
it was the season of Darkness,
it was the spring of hope,
it was the winter of despair,

Bonus task on reading code:
Here's some code that creates all Caesar shifts of the word "fuzzy". Modify this copy of the code to change a few things: (1) only shift by even shifts and (2) make the alphabet exclude the letters "mnop", so the shift works on the smaller alphabet (skipping over those letters), and (3) fix the code so it won't break when we change the word "fuzzy" to "fuzz".
['fuzzy', 'gvaaz', 'hwbba', 'ixccb', 'jyddc', 'kzeed', 'laffe', 'mbggf', 'nchhg', 'odiih', 'pejji', 'qfkkj', 'rgllk', 'shmml', 'tinnm', 'ujoon', 'vkppo', 'wlqqp', 'xmrrq', 'ynssr', 'zotts', 'apuut', 'bqvvu', 'crwwv', 'dsxxw', 'etyyx'] ['fuzzy', 'gvaaz', 'hwbba', 'ixccb', 'jyddc', 'kzeed', 'laffe', 'mbggf', 'nchhg', 'odiih', 'pejji', 'qfkkj', 'rgllk', 'shmml', 'tinnm', 'ujoon', 'vkppo', 'wlqqp', 'xmrrq', 'ynssr', 'zotts', 'apuut', 'bqvvu', 'crwwv', 'dsxxw', 'etyyx'] 