数论的Sage快速入门

这 Sage 快速入门教程是为MAA预备研讨会“SAGE：在本科生中使用开源数学软件”开发的(由美国国家科学基金会提供，截止日期0817071)。它是在知识共享署名-Share Alike 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
<class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>
1
1

请注意，对于素数，我们在前一个单元中验证了费马“小定理” \(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完成，看看你能对它做些什么。在这里试试，然后挑一个(希望不会太长！)。

sage: Zp.

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

sage: Zp.zeta?

我们用它来寻找这个领域中团结的第五个根源。我们使用 list comprehension (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

各种Zeta功能也可用；这里是Riemann Zeta的复杂情节。

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 。