.. -*- coding: utf-8 -*-
.. linkall
.. _prep-quickstart-number-theory:
Sage Quickstart for Number Theory
=================================
This `Sage <http://www.sagemath.org>`_ quickstart tutorial was developed
for the MAA PREP Workshop "Sage: Using Open\-Source Mathematics Software
with Undergraduates" (funding provided by NSF DUE 0817071). It is
licensed under the Creative Commons Attribution\-ShareAlike 3.0 license
(`CC BY\-SA <http://creativecommons.org/licenses/by-sa/3.0/>`_).
Since Sage began life as a project in algebraic and analytic number
theory (and this continues to be a big emphasis), it is no surprise that
functionality in this area is extremely comprehensive. And it's also
just enjoyable to explore elementary number theory by computer.
Modular Arithmetic
------------------
Conveniently, the ring of integers
modulo :math:`n` is always available in Sage, so we can do
modular arithmetic very easily.
For instance, we can create a number in :math:`\ZZ/11\ZZ`. The
``type`` command tells us that :math:`a` is not a regular integer.
::
sage: a = mod(2,11); a; type(a); a^10; a^1000000
2
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>
1
1
Note that we verified Fermat's "Little Theorem" in the previous cell,
for the prime :math:`p=11` and input :math:`a=2`.
Recalling the basic programming construct called a *loop* , we can
verify this for all :math:`a` in the integers modulo :math:`p`. Here,
instead of looping over an explicit list like ``[0,1,2,3,...8,9,10]``,
we loop over a Sage object.
::
sage: for a in Integers(11):
....: print("{} {}".format(a, a^10))
0 0
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
Notice that ``Integers(11)`` gave us an algebraic object which is the
ring of integers modulo the prime ideal generated by the element 11.
This works for much bigger numbers too, of course.
.. skip
::
sage: p=random_prime(10^200,proof=True)
sage: Zp=Integers(p) # Here we give ourselves shorthand for the modular integers
sage: a=Zp(2) # Here we ask for 2 as an element of that ring
sage: p; a; a^(p-1); a^(10^400)
83127880126958116183078749835647757239842289608629126718968330784897646881689610705533628095938824110164366160161355539845499311180100402016248362566463907409939681883876411550651284088712896660589151
2
1
21428062940380156097538386722913390559445420264965409656232714664156136144920173818936415427844953758774658350253363113516712541610660591925149144205368271119123211091215746697984955519927521190733305
Whenever you encounter a new object, you should try tab\-completion to
see what you can do to it. Try it here, and pick one (hopefully one
that won't be too long!).
.. skip
::
sage: Zp.
Here's one that sounds interesting.
.. skip
::
sage: Zp.zeta?
And we use it to find the fifth roots of unity in this field. We use
the *list comprehension* (set\-builder) notation from the programming
tutorial this time.
.. skip
::
sage: root_list = Zp.zeta(5,all=True); root_list
[80199770388563324100334548626345240081294273289109866436996652525328268652922508892946068538641538316054373187019168781211876036849531337824832226216684677717580165592175377569174402189281574130719978, 69839783895572286297568834485025073557885364348071061715465477061873400359794989367423407683971299361817245213947182344090739843367076197016322541936552333837227080274674865687645877633828974738751695, 57407444219199061498801298672323590163238592201574572482836619025676869537007609315386800852204337587805249250896651467970585450518157701115893749407382500580682168292929753154872678880962261809848942, 41936641877539676652531567723249367917108638987131879521606243741814402095343724540844607212999297064816230828621064026263296602805535970091696570138772210094329631491849238240260893562065879302446837]
Are these really fifth roots of unity?
.. skip
::
sage: [root^5 for root in root_list]
[1, 1, 1, 1]
Luckily, it checked out.
(If you didn't get any, then your random prime ended up being one for
which there *are* no fifth roots of unity -- try doing the sequence
over again!)
More basic functionality
------------------------
Similarly to the situation in linear algebra, there is much more we can
access at the elementary level, such as
- primitive roots,
- ways to write a number as a sum of squares,
- Legendre symbols,
- modular solving of basic equations,
- etc.
A good way to use Sage in this context is to allow students to
experiment with pencil and paper first, then use Sage to see whether
patterns they discover hold true before attempting to prove them.
::
sage: p = 13
sage: primitive_root(p); two_squares(p); is_prime(p)
2
(2, 3)
True
This makes it easy to construct elementary cryptographic examples as
well. Here is a standard example of a Diffie\-Hellman key exchange, for
instance. If we didn't do the second line, exponentiation would be
impractical.
.. skip
::
sage: p=random_prime(10^20,10^30) # a random prime between these numbers
sage: q=mod(primitive_root(p),p) # makes the primitive root a number modulo p, not an integer
sage: n=randint(1,p) # Alice's random number
sage: m=randint(1,p) # Bob's random number
sage: x=q^n; y=q^m
sage: x; y; x^m; y^n
66786436189350477660
77232558812003408270
45432410008036883324
45432410008036883324
The final line of the cell first requests Alice and Bob's (possibly)
public information, and then verifies that the private keys they get are
the same.
It is hard to resist including just one interact. How many theorems do
you see here?
.. skip
::
sage: @interact
sage: def power_table_plot(p=(7,prime_range(50))):
....: P=matrix_plot(matrix(p-1,[mod(a,p)^b for a in range(1,p) for b in srange(p)]),cmap='jet')
....: show(P)
This is a graphic giving the various powers of integers modulo :math:`p`
as colors, not numbers. The columns are the powers, so the first column
is the zeroth power (always 1) and the second column gives the colors
for the numbers modulo the given prime (first power).
One more very useful object is the prime counting function
:math:`\pi(x)`. This comes with its own custom plotting.
::
sage: prime_pi(100); plot(prime_pi,1,100)
25
Graphics object consisting of 1 graphics primitive
A very nice aspect of Sage is combining several aspects of mathematics
together. It can be very eye\-opening to students to see analytic
aspects of number theory early on.
(Note that we have to reassign :math:`x` to a variable, since above it
was a cryptographic key!)
::
sage: var('x')
x
sage: plot(prime_pi,2,10^6,thickness=2)+plot(Li,2,10^6,color='red')+plot(x/ln(x),2,10^6,color='green')
Graphics object consisting of 3 graphics primitives
Advanced Number Theory
----------------------
For those who are interested, more advanced number\-theoretic objects
are easy to come by; we end with a brief sampler of these.
In the first example, `K` is the field extension
:math:`\QQ(\sqrt{-14})`, where the symbol ``a`` plays the role of
:math:`\sqrt{-14}`; we discover several basic facts about :math:`K` in
the next several cells.
::
sage: K.<a> = NumberField(x^2+14); K
Number Field in a with defining polynomial x^2 + 14
::
sage: K.discriminant(); K.class_group().order(); K.class_group().is_cyclic()
-56
4
True
Various zeta functions are also available; here is a complex plot of the
Riemann zeta.
::
sage: complex_plot(zeta, (-30,30), (-30,30))
Graphics object consisting of 1 graphics primitive
Cryptography
------------
Sage supports various more advanced cryptographic procedures as well as
some basic pedagogical ones natively. This example is adapted from the
documentation.
::
sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES(); sdes
Simplified DES block cipher with 10-bit keys
::
sage: bin = BinaryStrings()
sage: P = [0,1,0,0,1,1,0,1] # our message
sage: K = sdes.random_key() # generate a random key
sage: C = sdes.encrypt(P, K) # encrypt our message
sage: plaintxt = sdes.decrypt(C, K) # decrypt it
sage: plaintxt # print it
[0, 1, 0, 0, 1, 1, 0, 1]
See also the cryptography example in the :ref:`discrete math quickstart
<CryptoEd>`.