Note that we verified Fermat's "Little Theorem" in the previous cell, for the prime $p=11$ and input $a=2$. We can use the basic programming construct called a loop to do this for all $a$ in the integers modulo $p$. Here, instead of looping over an explicit list, we loop over a Sage object.
{{{id=110| for a in Integers(11): print 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.
{{{id=117| p=random_prime(10^200,proof=True) Zp=Integers(p) # Here we give ourselves shorthand for the modular integers a=Zp(2) # Here we ask for 2 as an element of that ring p; a; a^(p-1); a^(10^400) /// 71057602168421278009631273527759344984381280766249066987648942116872099371344590929172388921514478456905270869247550115227700583810475797255093805599942532999717291696330486179224707592166286784781189 2 1 42088215482650592397914853166952811389085402427499831009134605856762881416783581603512396492471539520306764576082935149973964994912138072969437619000683970722198054906787520363148506770399841466065192 }}}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!).
{{{id=121| Zp. /// }}}Here's one that sounds interesting.
{{{id=124| Zp.zeta? ///File: /usr/local/sage-prep/devel/sage/sage/rings/ring.pyx
Type: <type ‘builtin_function_or_method’>
Definition: Zp.zeta(n=2, all=False)
Docstring:
Return an n-th root of unity in self if there is one, or raise an ArithmeticError otherwise.
INPUT:
- n – positive integer
- all – bool, default: False. If True, return a list of all n-th roots of 1.
OUTPUT:
element of self of finite order
EXAMPLES:
sage: QQ.zeta() -1 sage: QQ.zeta(1) 1 sage: CyclotomicField(6).zeta() zeta6 sage: CyclotomicField(3).zeta() zeta3 sage: CyclotomicField(3).zeta().multiplicative_order() 3 sage: a = GF(7).zeta(); a 3 sage: a.multiplicative_order() 6 sage: a = GF(49,'z').zeta(); a z sage: a.multiplicative_order() 48 sage: a = GF(49,'z').zeta(2); a 6 sage: a.multiplicative_order() 2 sage: QQ.zeta(3) ... ValueError: no n-th root of unity in rational field sage: Zp(7, prec=8).zeta() 3 + 4*7 + 6*7^2 + 3*7^3 + 2*7^5 + 6*7^6 + 2*7^7 + O(7^8)
And we use it to find the fifth roots of unity in this field.
{{{id=125| Zp.zeta(5,all=True); [root^5 for root in Zp.zeta(5,all=True)] /// [54794526505934238389449689102583664664952113664493107280273972977159336751007560164002533398166066997781239987131137486395673921454196666457995698036573011098502479919620301605228045390276887011423925, 43331996871167574854893072866149880061957637862597016305579314571386358509207858342616934836925861829245288554060226109826019101116874160093614781563649477867891325036450259891336230960213685032212116, 20762845126791212682371979762722290762141019683130329292875056588743362249814096550344688303863522077226623997901764415138691664706289805781591193518532813428687810740143187417494983351582421282930891, 10511146450364786624484129724463025479159573026267110009097700254950374372082055752912682041544045951731236564440632545399482527647689360974323410561493688389686603224620469934215613531710493597632829] [1, 1, 1, 1] }}}Luckily, it checked out.
Similarly to the situation in linear algebra, there is much more we can access, such as primitive roots, ways to write a number as a sum of squares, 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 one attempts to prove them.
{{{id=62| p = 13 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.
{{{id=128| p=random_prime(10^20,10^30) # a random prime between these numbers q=mod(primitive_root(p),p) # makes the primitive root a number modulo p, not an integer n=randint(1,p) # Alice's random number m=randint(1,p) # Bob's random number x=q^n; y=q^m x; y; x^m; y^n /// 72542337723868272604 30520442862765725663 39746311719791547937 39746311719791547937 }}}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? (The second column gives the colors for the numbers modulo the given prime, and the columns are the powers.)
{{{id=135| @interact 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) /// }}}One more very useful object is the prime counting function $\pi(x)$. This comes with its own custom plotting.
{{{id=119| prime_pi(100); plot(prime_pi,1,100) /// 25
}}}
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 $x$ to a variable, since above it was a key!)
{{{id=127| var('x') plot(prime_pi,2,10^6,thickness=2)+plot(Li,2,10^6,color='red')+plot(x/ln(x),2,10^6,color='green') ///
}}}
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 $\QQ(\sqrt{-14})$, where the symbol 'a' plays the role of $\sqrt{-14}$; we discover several basic facts about $K$ in the next several cells.
{{{id=111| K. = NumberField(x^2+14); K /// Number Field in a with defining polynomial x^2 + 14 }}} {{{id=113| K.discriminant(); K.class_group().order(); K.class_group().is_cyclic() /// -56 }}}Various zeta functions are also available; here is a complex plot of the Riemann zeta.
{{{id=132| complex_plot(zeta, (-30,30), (-30,30)) ///
}}}
Sage supports various more advanced cryptographic procedures as well as some basic pedagogical ones natively. This example is adapted from the documentation.
{{{id=116| from sage.crypto.block_cipher.sdes import SimplifiedDES sdes = SimplifiedDES(); sdes /// Simplified DES block cipher with 10-bit keys }}} {{{id=133| bin = BinaryStrings() P = [0,1,0,0,1,1,0,1] # our message K = sdes.random_key() # generate a random key C = sdes.encrypt(P, K) # encrypt our message plaintxt = sdes.decrypt(C, K) # decrypt it plaintxt # print it /// [0, 1, 0, 0, 1, 1, 0, 1] }}}