SAGE number theory demo for AMS

862 days ago by wstein

Integer Factorization

  • PARI's factoring (and primality testing) suite
  • Paul Zimmerman's GMP-ECM factorization library
  • Bill Hart's quadratic sieve
factor(2010) 
        
2 * 3 * 5 * 67
2 * 3 * 5 * 67
# GMP-ECM time ecm.factor((2^197 + 1)/3) 
        
[197002597249, 1348959352853811313, 251951573867253012259144010843]
Time: CPU 0.23 s, Wall: 3.32 s
[197002597249, 1348959352853811313, 251951573867253012259144010843]
Time: CPU 0.23 s, Wall: 3.32 s
# PARI time factor((2^197 + 1)/3) 
        
197002597249 * 1348959352853811313 * 251951573867253012259144010843
Time: CPU 2.24 s, Wall: 2.41 s
197002597249 * 1348959352853811313 * 251951573867253012259144010843
Time: CPU 2.24 s, Wall: 2.41 s
# Hart's Sieve time qsieve(1348959352853811313 * 251951573867253012259144010843) 
        
([1348959352853811313, 251951573867253012259144010843], '')
Time: CPU 0.03 s, Wall: 1.71 s
([1348959352853811313, 251951573867253012259144010843], '')
Time: CPU 0.03 s, Wall: 1.71 s
 
       

Number Fields

  • All capabilities of NTL and PARI (which are included)
  • But with a more structural Magma-like interface
  • Class groups, Galois groups, arithmetic, relative extensions, orders, ideals, residue class fields
var('x') K.<a> = NumberField(x^3 + 3*x + 2) K 
        
Number Field in a with defining polynomial x^3 + 3*x + 2
Number Field in a with defining polynomial x^3 + 3*x + 2
K.maximal_order() 
        
Maximal Order in Number Field in a with defining polynomial x^3 + 3*x +
2
Maximal Order in Number Field in a with defining polynomial x^3 + 3*x + 2
F = K.factor(13); F 
        
(Fractional ideal (-3*a^2 + a - 5)) * (Fractional ideal (-a^2 + a - 1))
(Fractional ideal (-3*a^2 + a - 5)) * (Fractional ideal (-a^2 + a - 1))
I = F[0][0]; I 
        
Fractional ideal (-3*a^2 + a - 5)
Fractional ideal (-3*a^2 + a - 5)
k = I.residue_field(); k 
        
Residue field in abar of Fractional ideal (-3*a^2 + a - 5)
Residue field in abar of Fractional ideal (-3*a^2 + a - 5)
k(a^2/3) 
        
3*abar + 11
3*abar + 11
K.class_number() 
        
1
1
K.galois_group(type='pari') 
        
Galois group PARI group [6, -1, 2, "S3"] of degree 3 of the Number Field
in a with defining polynomial x^3 + 3*x + 2
Galois group PARI group [6, -1, 2, "S3"] of degree 3 of the Number Field in a with defining polynomial x^3 + 3*x + 2
 
       

Elliptic Curves

  • Sage includes John Cremona's mwrank program, his g0n library (that he used to make his big tables).
  • Group structures over non-prime finite fields
  • Tate's algorithm over arbitrary number fields (plus PARI's fast Tate's algorithm over \mathbf{Q}.
  • L-series evaluation code (New code, Dokchitser's code)
  • Best existing package for p-adic L-series  (Stein and Wuthrich)
  • Fast computation of p-adic heights and regulators
  • Heegner points / Gross-Zagier 
  • Zeros of L-series (Rubinstein)
  • Code for checking BSD
  • Images of Galois representations
  • Isogeny class enumeration
  • Fast SEA point counting (for crypto)
E = EllipticCurve('389a'); E 
        
Elliptic Curve defined by y^2 + y = x^3 + x^2 - 2*x over Rational Field
Elliptic Curve defined by y^2 + y = x^3 + x^2 - 2*x over Rational Field
plot(E,thickness=5) 
       
E.gens() 
        
[(-1 : 1 : 1), (0 : -1 : 1)]
[(-1 : 1 : 1), (0 : -1 : 1)]
E.non_surjective() 
        
[]
[]
L = E.lseries() 
       
L.zeros(10) 
        
[0.000000000, 0.000000000, 2.87609907, 4.41689608, 5.79340263,
6.98596665, 7.47490750, 8.63320525, 9.63307880, 10.3514333]
[0.000000000, 0.000000000, 2.87609907, 4.41689608, 5.79340263, 6.98596665, 7.47490750, 8.63320525, 9.63307880, 10.3514333]
F = E.change_ring(GF(next_prime(10^30))); F 
        
Elliptic Curve defined by y^2 + y = x^3 + x^2 +
1000000000000000000000000000055*x over Finite Field of size
1000000000000000000000000000057
Elliptic Curve defined by y^2 + y = x^3 + x^2 + 1000000000000000000000000000055*x over Finite Field of size 1000000000000000000000000000057
time F.cardinality() 
        
1000000000000001008463730459999
Time: CPU 0.09 s, Wall: 1.12 s
1000000000000001008463730459999
Time: CPU 0.09 s, Wall: 1.12 s
 
       

 
       

Modular Forms and Congruence Subgroups

  • Classical modular forms via modular symbols
  • Overconvergent modular forms
  • Explicit power series generators (very efficient in some cases)
  • Formulas for Eisenstein series
  • Bernoulli numbers (world's fastest code for computing them, by David Harvey)
  • Congruences subgroups including \Gamma_H(N).
  • Extensived dimension formulas
  • Mestre module on supersingular j-invariants
ModularForms(Gamma1(3),8).basis() 
        
[
q + 6*q^2 - 27*q^3 - 92*q^4 + 390*q^5 + O(q^6),
1 + 480*q^3 + O(q^6),
q + 129*q^2 + 2187*q^3 + 16513*q^4 + 78126*q^5 + O(q^6)
]
[
q + 6*q^2 - 27*q^3 - 92*q^4 + 390*q^5 + O(q^6),
1 + 480*q^3 + O(q^6),
q + 129*q^2 + 2187*q^3 + 16513*q^4 + 78126*q^5 + O(q^6)
]
time f = delta_qexp(10^5) 
        
Time: CPU 1.29 s, Wall: 1.34 s
Time: CPU 1.29 s, Wall: 1.34 s
b = bernoulli(10^5, algorithm='bernmm', num_threads=2) 
       
len(str(b)) 
        
376790
376790
G.<a,b> = DirichletGroup(20); G 
        
Group of Dirichlet characters of modulus 20 over Cyclotomic Field of
order 4 and degree 2
Group of Dirichlet characters of modulus 20 over Cyclotomic Field of order 4 and degree 2
(a*b).bernoulli(8) 
        
-99883376*zeta4 - 161669728
-99883376*zeta4 - 161669728
 
       

Fast Hermite Normal Form and Determinants

  • Very fast (fastest?) asymptotic code for computing determinants and Hermite forms of certain integer matrices...
a = random_matrix(ZZ,150,x=0,y=2^32) time d = a.det() 
        
Time: CPU 0.31 s, Wall: 0.31 s
Time: CPU 0.31 s, Wall: 0.31 s
time b = a.hermite_form() 
        
Time: CPU 1.26 s, Wall: 1.28 s
Time: CPU 1.26 s, Wall: 1.28 s

 
       

Rational Quaternion Algebras and Brandt Modules
B = BrandtModule(7,10); B 
        
Brandt module of dimension 10 of level 7*10 of weight 2 over Rational
Field
Brandt module of dimension 10 of level 7*10 of weight 2 over Rational Field
B.right_ideals() 
        
(Fractional ideal (2 + 2*j + 32*k, 2*i + 14*k, 4*j + 24*k, 40*k),
Fractional ideal (2 + 2*j + 32*k, 2*i + 8*j + 22*k, 12*j + 72*k, 120*k),
Fractional ideal (2 + 2*j + 32*k, 2*i + 32*j + 286*k, 36*j + 216*k,
360*k), Fractional ideal (2 + 2*j + 112*k, 2*i + 4*j + 118*k, 12*j +
72*k, 120*k), Fractional ideal (2 + 10*j + 40*k, 2*i + 4*j + 38*k, 12*j
+ 72*k, 120*k), Fractional ideal (2 + 10*j + 80*k, 2*i + 8*j + 62*k,
12*j + 72*k, 120*k), Fractional ideal (2 + 22*j + 232*k, 2*i + 16*j +
230*k, 36*j + 216*k, 360*k), Fractional ideal (2 + 26*j + 136*k, 2*i +
28*j + 262*k, 36*j + 216*k, 360*k), Fractional ideal (2 + 26*j + 296*k,
2*i + 8*j + 262*k, 36*j + 216*k, 360*k), Fractional ideal (2 + 34*j +
184*k, 2*i + 4*j + 38*k, 36*j + 216*k, 360*k))
(Fractional ideal (2 + 2*j + 32*k, 2*i + 14*k, 4*j + 24*k, 40*k), Fractional ideal (2 + 2*j + 32*k, 2*i + 8*j + 22*k, 12*j + 72*k, 120*k), Fractional ideal (2 + 2*j + 32*k, 2*i + 32*j + 286*k, 36*j + 216*k, 360*k), Fractional ideal (2 + 2*j + 112*k, 2*i + 4*j + 118*k, 12*j + 72*k, 120*k), Fractional ideal (2 + 10*j + 40*k, 2*i + 4*j + 38*k, 12*j + 72*k, 120*k), Fractional ideal (2 + 10*j + 80*k, 2*i + 8*j + 62*k, 12*j + 72*k, 120*k), Fractional ideal (2 + 22*j + 232*k, 2*i + 16*j + 230*k, 36*j + 216*k, 360*k), Fractional ideal (2 + 26*j + 136*k, 2*i + 28*j + 262*k, 36*j + 216*k, 360*k), Fractional ideal (2 + 26*j + 296*k, 2*i + 8*j + 262*k, 36*j + 216*k, 360*k), Fractional ideal (2 + 34*j + 184*k, 2*i + 4*j + 38*k, 36*j + 216*k, 360*k))
show(B.hecke_matrix(2)) 
        
\left(\begin{array}{rrrrrrrrrr}
0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 1 & 1 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 2 & 1 \\
0 & 0 & 0 & 1 & 2 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 2 & 1 & 2 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 2 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 2 \\
2 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 0 & 0 \\
2 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\
1 & 2 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 2 & 0 & 0 & 0 & 0
\end{array}\right)
\left(\begin{array}{rrrrrrrrrr}
0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 1 & 1 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 2 & 1 \\
0 & 0 & 0 & 1 & 2 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 2 & 1 & 2 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 2 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 2 \\
2 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 0 & 0 \\
2 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\
1 & 2 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 2 & 0 & 0 & 0 & 0
\end{array}\right)

Quadratic Forms

  • Jon Hanke's long-developed code...
f = QuadraticForm(ZZ,4,[1..10]); f 
        
Quadratic form in 4 variables over Integer Ring with coefficients: 
[ 1 2 3 4 ]
[ * 5 6 7 ]
[ * * 8 9 ]
[ * * * 10 ]
Quadratic form in 4 variables over Integer Ring with coefficients: 
[ 1 2 3 4 ]
[ * 5 6 7 ]
[ * * 8 9 ]
[ * * * 10 ]
f.theta_series(10) 
        
1 + 2*q + 4*q^4 + 4*q^5 + 6*q^6 + 10*q^7 + 12*q^8 + 10*q^9 + O(q^10)
1 + 2*q + 4*q^4 + 4*q^5 + 6*q^6 + 10*q^7 + 12*q^8 + 10*q^9 + O(q^10)