超椭圆曲线上的Frobenius矩阵¶
Sage对Harvey-Kedlaya算法进行了高度优化的实现，用于计算与有限域上的曲线相关联的Frobenius矩阵。这是David Harvey的一个实现，它是GPL的，只依赖NTL(Sage中的一个C库，用于在 \((\ZZ/n\ZZ)[x]\) )。
我们导入hyellFrob函数，并在上对多项式调用它 \(\ZZ\) 。
sage: from sage.schemes.hyperelliptic_curves.hypellfrob import hypellfrob
sage: R.<x> = PolynomialRing(ZZ)
sage: f = x^5 + 2*x^2 + x + 1; p = 101
sage: M = hypellfrob(p, 1, f); M
[ O(101) O(101) 93 + O(101) 62 + O(101)]
[ O(101) O(101) 55 + O(101) 19 + O(101)]
[ O(101) O(101) 65 + O(101) 42 + O(101)]
[ O(101) O(101) 89 + O(101) 29 + O(101)]
我们做同样的计算，但在 \(\ZZ/101^4\ZZ\) ，这提供了足够的精度来识别精确的特征多项式 \(\ZZ[x]\) 作为自同态环的一个元素。这种计算仍然非常快，只需要几分之一秒。
sage: M = hypellfrob(p, 4, f) # about 0.25 seconds
sage: M[0,0]
91844754 + O(101^4)
Frobenius的特征多项式为 \(x^4 + 7x^3 + 167x^2 + 707x + 10201\) ，这决定了 \(\zeta\) 曲线的函数 \(y^2= f(x)\) 。
sage: M.charpoly()
(1 + O(101^4))*x^4 + (7 + O(101^4))*x^3 + (167 + O(101^4))*x^2 + (707 + O(101^4))*x + 10201 + O(101^4)
备注
练习：明确地写下Zeta函数，在一些有限域上计算点数，看看它们是否匹配。
模数符号¶
模数符号在计算模数形式的算法中起着关键作用，模数的特殊值 \(L\) -函数、椭圆曲线和模阿贝尔簇。Sage拥有最通用的模块符号实现，这要归功于我、Jordan i Quer(巴塞罗那的)和Craig Citro(Hida的学生)的工作。此外，到目前为止，使用模符号进行计算是我最喜欢的计算数学部分。对于Sage中的模块化符号，仍然有很多调整和优化工作要做，以使其成为世界上最快的实现，因为我的Magma实现在一些重要的情况下仍然更好。
备注
我将在周五的课程中更多地讨论模数符号，这将是关于模数形式和相关对象的。
我们创造了空间 \(M\) 重量的 \(4\) 某同余子群的模符号 \(\Gamma_H(13)\) 标高的 \(13\) 。然后我们计算这个空间的基，用Manin符号表示。最后，我们计算了Hecke算子 \(T_2\) 对…采取行动 \(M\) 求其特征多项式，并对其进行因式分解。我们还计算了尖点子空间的维度。
sage: M = ModularSymbols(GammaH(13,[3]), weight=4)
sage: M
Modular Symbols space of dimension 14 for Congruence Subgroup
Gamma_H(13) with H generated by [3] of weight 4 with sign 0
over Rational Field
sage: M.basis()
([X^2,(0,4)],
[X^2,(0,7)],
[X^2,(4,10)],
[X^2,(4,11)],
[X^2,(4,12)],
[X^2,(7,3)],
[X^2,(7,5)],
[X^2,(7,6)],
[X^2,(7,7)],
[X^2,(7,8)],
[X^2,(7,9)],
[X^2,(7,10)],
[X^2,(7,11)],
[X^2,(7,12)])
sage: factor(charpoly(M.T(2)))
(x - 7) * (x + 7) * (x - 9)^2 * (x + 5)^2
* (x^2 - x - 4)^2 * (x^2 + 9)^2
sage: dimension(M.cuspidal_subspace())
10
{Cremona's Modular Symbols Library} Sage includes John Cremona's specialized and insanely fast implementation of modular symbols for weight 2 and trivial character. We illustrate below computing the space of modular symbols of level 20014, which has dimension \(5005\), along with a Hecke operator on this space. The whole computation below takes only a few seconds; a similar computation takes a few minutes using Sage's generic modular symbols code. Moreover, Cremona has done computations at levels over 200,000 using his library, so the code is known to scale well to large problems. The new code in Sage for modular symbols is much more general, but doesn't scale nearly so well (yet).
sage: M = CremonaModularSymbols(20014) # few seconds
sage: M
Cremona Modular Symbols space of dimension 5005 for
Gamma_0(20014) of weight 2 with sign 0
sage: t = M.hecke_matrix(3) # few seconds
全实数字段的枚举¶
作为枚举Shimura曲线项目的一部分，John Voight向Sage提供了用于枚举全实数字段的代码。该算法并不是非常复杂，但它涉及一些必须编码才能运行得非常快的“内部循环”。使用Cython，Voight能够精确地实现他的问题所需的牛顿迭代的变体。
该功能 enumerate_totallyreal_fields_prim(n, B, ...) 枚举而不使用数据库(！)本原(无真子域)度全实域 \(n>1\) 带有判别式 \(d \leq B\) 。
我们计算了判别式的全实二次域 \(\leq 50\) 。下面的计算几乎是即时的，是实时完成的，而不是查表。
sage: enumerate_totallyreal_fields_prim(2,50)
[[5, x^2 - x - 1], [8, x^2 - 2], [12, x^2 - 3], [13, x^2 - x - 3],
[17, x^2 - x - 4], [21, x^2 - x - 5], [24, x^2 - 6], [28, x^2 - 7],
[29, x^2 - x - 7], [33, x^2 - x - 8], [37, x^2 - x - 9],
[40, x^2 - 10], [41, x^2 - x - 10], [44, x^2 - 11]]
我们计算了所有全实五次域的判别式 \(\leq 10^5\) 。同样，这是实时完成的-这不是表查找！
sage: enumerate_totallyreal_fields_prim(5,10^5)
[[14641, x^5 - x^4 - 4*x^3 + 3*x^2 + 3*x - 1],
[24217, x^5 - 5*x^3 - x^2 + 3*x + 1],
[36497, x^5 - 2*x^4 - 3*x^3 + 5*x^2 + x - 1],
[38569, x^5 - 5*x^3 + 4*x - 1],
[65657, x^5 - x^4 - 5*x^3 + 2*x^2 + 5*x + 1],
[70601, x^5 - x^4 - 5*x^3 + 2*x^2 + 3*x - 1],
[81509, x^5 - x^4 - 5*x^3 + 3*x^2 + 5*x - 2],
[81589, x^5 - 6*x^3 + 8*x - 1],
[89417, x^5 - 6*x^3 - x^2 + 8*x + 3]]
伯努利数¶
Matharia和Pari¶
来自MATHEMICA网站：
“今天我们打破了伯努利的记录：从分析引擎到数学软件2008年4月29日Oleksandr Pavlyk，内核技术，一周前，我拿了我们最新开发的数学软件，我输入了
BernoulliB[10^7]。然后我等着。昨天--5天23小时51分37秒后--我得到了结果！
Tom Boothby在Sage中进行了同样的计算，Sage使用Pari的bernfrac命令，该命令使用 \(\zeta\) 和阶乘到高精度，花了2天12小时。
大卫·哈维的伯恩姆¶
然后大卫·哈维想出了一种全新的算法，可以很好地并行化。他给出了这些用于计算的时间 \(B_{10^7}\) 在他的机器上(在我的16核1.8 GHz皓龙盒上需要59分57秒)：
PARI: 75 h, Mathematica: 142 h
bernmm (1 core) = 11.1 h, bernmm (10 cores) = 1.3 h
“在10个内核上运行5.5天，我 [David Harvey] 已计算 [the Bernoulli number] \(B_k\) 为 \(k = 10^8\) ，我相信这是一个新的记录。从本质上讲，这是我之前在本主题中建议的多模算法，但我想出了一些技巧来优化计算中的垃圾 \(B_k \text{mod} p\) “
所以现在Sage是世界上处理大伯努利数最快的。下面的计时是在24核的2.66 GHz至强盒上进行的。
sage: w1 = bernoulli(100000, num_threads=16) # 0.9 seconds wall time
sage: w2 = bernoulli(100000, algorithm='pari') # long time (6s on sage.math, 2011)
sage: w1 == w2 # long time
True
多项式运算¶
Flint：一元多项式算术¶
Sage使用Bill Hart和David Harvey的GPL‘d Flint C库进行算术运算 \(\ZZ[x]\) 。它出名的主要原因是它是世界上多项式乘法运算最快的，例如，在下面的基准测试中，它在某些系统上比NTL和MAGMA更快(尽管这样的基准测试当然会随着软件的改进而变化)。在幕后，弗林特包含了一些精心调整的离散傅里叶变换代码。
sage: Rflint = PolynomialRing(ZZ, 'x')
sage: f = Rflint([ZZ.random_element(2^64) for _ in [1..32]])
sage: g = Rflint([ZZ.random_element(2^64) for _ in [1..32]])
sage: timeit('f*g') # random output
625 loops, best of 3: 105 microseconds per loop
sage: Rntl = PolynomialRing(ZZ, 'x', implementation='NTL')
sage: f = Rntl([ZZ.random_element(2^64) for _ in [1..32]])
sage: g = Rntl([ZZ.random_element(2^64) for _ in [1..32]])
sage: timeit('f*g') # random output
625 loops, best of 3: 310 microseconds per loop
sage: ff = magma(f); gg = magma(g) #optional - magma
sage: s = 'time v := [%s * %s : i in [1..10^5]];'%(ff.name(), gg.name()) #optional - magma
sage: magma.eval(s) #optional - magma
'Time: ...'
单数：多元多项式算术¶
多变量多项式算术在许多情况下在库模式中使用奇异(由于Martin Albrecht)，这是相当快的。例如，下面我们在32003阶的有限域上进行法特曼基准测试，并将时间与岩浆进行比较。
sage: P.<x,y,z> = GF(32003)[]
sage: p = (x+y+z+1)^10
sage: q = p+1
sage: timeit('p*q') # random output
125 loops, best of 3: 1.53 ms per loop
sage: p = (x+y+z+1)^20
sage: q = p+1
sage: timeit('p*q') # not tested - timeout if SAGE_DEBUG=yes
5 loops, best of 3: 384 ms per loop
sage: pp = magma(p); qq = magma(q) #optional - magma
sage: s = 'time w := %s*%s;'%(pp.name(),qq.name()) #optional - magma
sage: magma.eval(s) #optional - magma
'Time: ...'