数论Sage快速入门

这个 Sage 快速入门教程是为MAA准备工作坊“Sage：对本科生使用开源数学软件”开发的（由NSF提供资金，到期日：0817071）。它是根据Creative Commons Attribution -ShareLiked 3.0许可证授权的 (CC BY-SA ）

自从Sage作为一个代数和解析数论的项目开始（这一直是一个很大的重点），这一领域的功能非常全面也就不足为奇了。用计算机探索初等数论也是一种享受。

模运算

很方便，整数环模 \(n\) 在Sage中总是可用的，所以我们可以很容易地进行模运算。例如，我们可以在 \(\ZZ/11\ZZ\) . 这个 type 指挥部告诉我们 \(a\) 不是正整数。

sage: a = mod(2,11); a; type(a); a^10; a^1000000
2
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>
1
1

注意，我们在前面的单元中验证了Fermat的“小定理”，对于素数 \(p=11\) 和输入 \(a=2\) .

调用称为 loop ，我们可以为所有人验证这一点 \(a\) 在整数模中 \(p\) . 这里，而不是在一个显式的列表上循环，比如 [0,1,2,3,...8,9,10] ，我们在一个Sage的物体上循环。

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

注意到 Integers(11) 给出了一个代数对象，它是由元素11生成的素数理想模的整数环。

当然，这也适用于更大的数字。

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

无论何时遇到新对象，都应尝试tab -completion，看看能对它做些什么。在这里试试，选一个（希望不会太久！）。

sage: Zp.

这里有一个听起来很有趣的。

sage: Zp.zeta?

我们在第五个领域找到它的统一性。我们使用 列表理解 （set -builder）本次编程教程中的符号。

sage: root_list = Zp.zeta(5,all=True); root_list
[80199770388563324100334548626345240081294273289109866436996652525328268652922508892946068538641538316054373187019168781211876036849531337824832226216684677717580165592175377569174402189281574130719978, 69839783895572286297568834485025073557885364348071061715465477061873400359794989367423407683971299361817245213947182344090739843367076197016322541936552333837227080274674865687645877633828974738751695, 57407444219199061498801298672323590163238592201574572482836619025676869537007609315386800852204337587805249250896651467970585450518157701115893749407382500580682168292929753154872678880962261809848942, 41936641877539676652531567723249367917108638987131879521606243741814402095343724540844607212999297064816230828621064026263296602805535970091696570138772210094329631491849238240260893562065879302446837]

这些真的是团结的第五根吗？

sage: [root^5 for root in root_list]
[1, 1, 1, 1]

幸运的是，检查出来了。（如果你没有得到任何，那么你的随机素数最终是其中的一个 are 没有团结的第五根--试着把这个序列再做一遍！）

更基本的功能

类似于线性代数中的情况，我们可以在初级水平上获得更多，例如

• 原始根，

• 把数字写成平方和的方法，

• 传奇符号，

• 基本方程的模解法，

• 等。

在这种情况下使用Sage的一个好方法是让学生先用铅笔和纸做实验，然后在试图证明它们之前，使用Sage看看他们发现的模式是否正确。

sage: p = 13
sage: primitive_root(p); two_squares(p); is_prime(p)
2
(2, 3)
True

这使得构造基本密码示例也变得容易。下面是Diffie-Hellman密钥交换的标准示例。如果我们不做第二行，求幂就不切实际了。

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

单元的最后一行首先请求Alice和Bob（可能）的公共信息，然后验证他们获得的私钥是否相同。

很难抗拒只包含一个交互。你在这里看到多少个定理？

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)

这是一个给出整数模的各种幂的图形 \(p\) 作为颜色，而不是数字。列是幂，所以第一列是第零次幂（总是1），第二列是给定素数模的颜色（第一次幂）。

另一个非常有用的对象是素数计数函数 \(\pi(x)\) . 这有它自己的定制绘图。

sage: prime_pi(100); plot(prime_pi,1,100)
25
Graphics object consisting of 1 graphics primitive

Sage的一个很好的方面是将数学的几个方面结合在一起。早期看到数论的分析方面对学生来说是非常有启发性的。（请注意，我们必须重新分配 \(x\) 一个变量，因为上面是一个加密密钥！）

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

高级数论

对于那些感兴趣的人来说，更先进的数论对象很容易获得；我们以这些对象的简短示例结束。

在第一个例子中， K 是字段扩展名 \(\QQ(\sqrt{{-14}})\) ，其中符号 a 扮演 \(\sqrt{{-14}}\) 我们发现了一些关于 \(K\) 在接下来的几个牢房里。

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

在这里，riezetmann的各种函数也是可用的。

sage: complex_plot(zeta, (-30,30), (-30,30))
Graphics object consisting of 1 graphics primitive

密码学

Sage支持各种更高级的加密程序以及一些基本的教学程序。此示例改编自文档。

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]

另请参阅中的加密示例 discrete math quickstart .