初等数论¶
利用模数权力¶
如何在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\) ),你可以叫‘S’ 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
Pari命令 primepi
通过以下命令使用 pari(x).primepi()
。它返回素数的个数 \(\leq x\) ,例如:
sage: pari(10).primepi()
4
vbl.使用 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
命令(也称为“Legendre符号”):
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]