初等数论

取模幂

在Sage中如何计算模幂？

计算 \(51^{{2006}} \pmod{{97}}\) 在Sage中，键入

sage: R = Integers(97)
sage: a = R(51)
sage: a^2006
12

而不是 R = Integers(97) 你也可以打字 R = IntegerModRing(97) . 另一个选择是使用与GMP的接口：

sage: 51.powermod(99203843984,97)
96

离散日志

找到一个号码 \(x\) 这样的话 \(b^x\equiv a \pmod m\) 离散对数 \(a \pmod m\) )，你可以打电话给 log 命令：

sage: r = Integers(125)
sage: b = r.multiplicative_generator()^3
sage: a = b^17
sage: a.log(b)
17

这也适用于有限域：

sage: FF = FiniteField(16,"a")
sage: a = FF.gen()
sage: c = a^7
sage: c.log(a)
7

素数

在Sage中如何构造素数？

班级 Primes 允许进行素性测试：

sage: 2^(2^12)+1 in Primes()
False
sage: 11 in Primes()
True

用法 next_prime 不言自明：

sage: next_prime(2005)
      2011

巴黎司令部 primepi 通过命令使用 pari(x).primepi() . 这将返回素数 \(\leq x\) 例如：

sage: pari(10).primepi()
      4

使用 primes_first_n 或 primes 我们可以确认，确实有 \(4\) 启动至 \(10\) ：

sage: primes_first_n(5)
[2, 3, 5, 7, 11]
sage: list(primes(1, 10))
[2, 3, 5, 7]

约数

在Sage中如何计算整数的除数之和？

Sage使用 divisors(n) 的除数列表 n ， number_of_divisors(n) 的除数 n 和 sigma(n,k) 对于 k -除数的次幂 n （所以 number_of_divisors(n) 和 sigma(n,0) 相同）。

例如：

sage: divisors(28); sum(divisors(28)); 2*28
[1, 2, 4, 7, 14, 28]
56
56
sage: sigma(28,0); sigma(28,1); sigma(28,2)
6
56
1050

二次剩余

试试这个：

sage: Q = quadratic_residues(23); Q
[0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18]
sage: N = [x for x in range(22) if kronecker(x,23)==-1]; N
[5, 7, 10, 11, 14, 15, 17, 19, 20, 21]

Q是mod 23的二次剩余集，N是非剩余集。

下面是另一种使用 kronecker 命令（也称为“勒让德符号”）：

sage: [x for x in range(22) if kronecker(x,23)==1]
[1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18]
sage: [x for x in range(22) if kronecker(x,23)==-1]
[5, 7, 10, 11, 14, 15, 17, 19, 20, 21]