Sage Quick Reference: Elementary Number Theory William Stein (modified by nu)

Sage Version 3.4

http://wiki.sagemath.org/quickref

GNU Free Document License, extend for your own use

以下 m, n, a, b, … は ZZ の元とする. ZZ = ℤ = 全ての整数

Everywhere m, n, a, b, etc. are elements of ZZ ZZ = ℤ = all integers

整数 Integers

…, −2, −1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …

n を m で割ると余りは n % m

gcd(n,m), gcd(list)

拡張された公約数 g = sa + tb = gcd(a, b): g,s,t=xgcd(a,b)

lcm(n,m), lcm(list)
二項係数\binom{m}{n} = binomial(m,n)

base 進法による表示: n.digits(base) base 進法による桁数: n.ndigits(base) (base は省略可, デフォルトは 10) 割り切る. n | m: n.divides(m), nk = m を満たす k があるか. 約数 – d | n を満たす d 達 : n.divisors()

階乗 – n! = n.factorial()

n divided by m has remainder n % m

gcd(n,m), gcd(list)

extended gcd g = sa + tb = gcd(a, b): g,s,t=xgcd(a,b)

lcm(n,m), lcm(list)

binomial coefficient \binom{m}{n} = binomial(m,n) digits in a given base: n.digits(base) number of digits: n.ndigits(base) (base is optional and defaults to 10) divides n | m: n.divides(m) if nk = m some k divisors – all d with d | n: n.divisors()

factorial – n! = n.factorial()

素数 Prime Numbers

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, …

素因数分解: factor(n)
素数判定: is prime(n), is pseudoprime(n)
素冪判定: is prime power(n)

π(x) = #{p : p ≤ x is prime} = prime pi(x)

素数の集合: Primes()

{p : m ≤ p < n and p prime} =prime range(m,n)

n 以上 m 以下の素冪の集合: prime powers(m,n)
最初の n 個の素数: primes first n(n)

次の素数, ひとつ前の素数: next prime(n),

previous prime(n), next probable prime(n)
次の素冪, ひとつ前の素冪: next prime power(n),
pevious prime power(n)

2^{p} − 1 の素数性に関する Lucas-Lehmer テスト

def is_prime_lucas_lehmer(p):
s = Mod(4, 2^p - 1)
for i in range(3, p+1): s = s^2 - 2
return s == 0

factorization: factor(n)

primality testing: is prime(n), is pseudoprime(n)

prime power testing: is prime power(n) π(x) = #{p : p ≤ x is prime} = prime pi(x) set of prime numbers: Primes() {p : m ≤ p < n and p prime} =prime range(m,n)

prime powers: prime powers(m,n)
first n primes: primes first n(n)

next and previous primes: next prime(n),

previous prime(n), next probable prime(n)
prime powers: next prime power(n),
pevious prime power(n)

Lucas-Lehmer test for primality of 2^{p} − 1

def is_prime_lucas_lehmer(p):
s = Mod(4, 2^p - 1)
for i in range(3, p+1): s = s^2 - 2
return s == 0

合同式, モジュラ計算 Modular Arithmetic and Congruences

k=12; m = matrix(ZZ, k, [(i*j)%k for i in [0..k-1] for j in [0..k-1]]); m.plot(cmap='gray')

オイラーの ϕ(n) 関数: euler phi(n)

クロネッカーシンボル (\frac{a}{b}) = kronecker symbol(a,b)
平方剰余: quadratic residues(n)
平方非剰余: quadratic residues(n)
環 ℤ/nℤ = Zmod(n) = IntegerModRing(n)

ℤ/nℤ の元としての a (a mod n): Mod(a, n)

ℤ/nℤ での原始根 = primitive root(n)
ℤ/nℤ での逆元: n.inverse mod(m)

ℤ/nℤ での冪 a^{n} (mod m): power mod(a, n, m)

中国の剰余定理: x = crt(a,b,m,n)

x ≡ a (mod m) かつ x ≡ b (mod n) を満たす x を探す

離散対数: log(Mod(6,7), Mod(3,7))
a (mod n) の次数 = Mod(a,n).multiplicative order()

a (mod n) の平方根 = Mod(a,n).sqrt()

Euler’s ϕ(n) function: euler phi(n)

Kronecker symbol ( \frac{a}{b} ) = kronecker symbol(a,b)
Quadratic residues: quadratic residues(n)

Quadratic non-residues: quadratic residues(n)

ring ℤ/nℤ = Zmod(n) = IntegerModRing(n)

a modulo n as element of ℤ/nℤ: Mod(a, n) primitive root modulo n = primitive root(n) inverse of n (mod m): n.inverse mod(m)

power a^{n} (mod m): power mod(a, n, m)

Chinese remainder theorem: x = crt(a,b,m,n)

finds x with x ≡ a (mod m) and x ≡ b (mod n)

discrete log: log(Mod(6,7), Mod(3,7))
order of a (mod n) = Mod(a,n).multiplicative order()

square root of a (mod n) = Mod(a,n).sqrt()

特殊函数 Special Functions

complex plot(zeta, (-30,5), (-8,8))

ζ(s) = ∏_{p} \frac{1}{1 − p^{−s}} = ∑ \frac{1}{n^{s}} = zeta(s)

Li(x) = ∫_{2}^{x} \frac{1}{log(t)}dt = Li(x)

Γ(s) = ∫_{0}^{∞} t^{s−1}e^{−t}dt = gamma(s)

ζ(s) = ∏_{p} \frac{1}{1 − p^{−s}} = ∑ \frac{1}{n^{s}} = zeta(s)

Li(x) = ∫_{2}^{x} \frac{1}{log(t)} dt = Li(x)

Γ(s) = ∫_{0}^{∞} t^{s−1}e^{−t}dt = gamma(s)

連分数 Continued Fractions

continued fraction(pi)

π = 3 + \frac{1}{7 + \frac{1}{15 + \frac{1}{1 + \frac{1}{292 + ⋯}}}}

連分数: c=continued fraction(x,bits)
近似分数 (達): c.convergents()
部分分子 p_{n} = c.pn(n)
部分分母 q_{n} = c.qn(n)

値: c.value()
continued fraction: c=continued fraction(x,bits)
convergents: c.convergents()

convergent numerator p_{n} = c.pn(n) convergent denominator q_{n} = c.qn(n)

value: c.value()

楕円曲線 Elliptic Curves

EllipticCurve([0,0,1,-1,0]).plot(plot points=300,thickness=3)

E = EllipticCurve([a_{1}, a_{2}, a_{3}, a_{4}, a_{6}])

y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}

E の導手 (conductor) N = E.conductor()

E の判別式 Δ =E.discriminant()
E の階数 = E.rank()

E(ℚ) の自由生成系 = E.gens()

j-invariant = E.j invariant()

N_{p} = #{modulo p での E の解} = E.Np(prime) a_{p} = p + 1 − N_{p} =E.ap(prime) L(E, s) = ∑ \frac{a_{n}}{n^{s}} = E.lseries()

ord_{s=1} L(E, s) = E.analytic rank()
  E = EllipticCurve([a_{1}, a_{2}, a_{3}, a_{4}, a_{6}])

y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}

conductor N of E =E.conductor() discriminant Δ of E =E.discriminant()

rank of E = E.rank()

free generators for E(ℚ) = E.gens()

j-invariant = E.j invariant()

N_{p} = #{solutions to E modulo p} = E.Np(prime) a_{p} = p + 1 − N_{p} =E.ap(prime) L(E, s) = ∑ \frac{a_{n}}{n^{s}} = E.lseries()

ord_{s=1} L(E, s) = E.analytic rank()

p で合同な楕円曲線 Elliptic Curves Modulo p

EllipticCurve(GF(997), [0,0,1,-1,0]).plot()

E = EllipticCurve(GF(p), [a_{1}, a_{2}, a_{3}, a_{4}, a_{6}])
#E(𝔽_{p}) = E.cardinality()

E(𝔽_{p}) の生成系 = E.gens()

E(𝔽_{p}) =E.points()
  E = EllipticCurve(GF(p), [a_{1}, a_{2}, a_{3}, a_{4}, a_{6}])
#E(𝔽_{p}) = E.cardinality()

generators for E(𝔽_{p}) = E.gens()

                                                                  E(𝔽_{p}) =E.points()