SAGE Demo
system:sage

<h2>You can use Sage to teach Calculus</h2>

{{{id=0|
2 + 3
///
5
}}}

{{{id=1|
x = var('x')
show(plot(sin(x^2), 0, pi))
}}}

{{{id=2|
a = integrate(sin(x^2),x); a
///
sqrt(pi)*((sqrt(2)*I + sqrt(2))*erf((sqrt(2)*I + sqrt(2))*x/2) + (sqrt(2)*I - sqrt(2))*erf((sqrt(2)*I - sqrt(2))*x/2))/8
}}}

{{{id=3|
show(a)
///
<html><div class="math">\frac{{\sqrt{ \pi } \cdot \left( {\left( {\sqrt{ 2 } \cdot i} + \sqrt{ 2 } \right) \cdot \left( \text{erf} \left( \frac{{\left( {\sqrt{ 2 } \cdot i} + \sqrt{ 2 } \right) \cdot x}}{2} \right) \right)} + {\left( {\sqrt{ 2 } \cdot i} - \sqrt{ 2 } \right) \cdot \left( \text{erf} \left( \frac{{\left( {\sqrt{ 2 } \cdot i} - \sqrt{ 2 } \right) \cdot x}}{2} \right) \right)} \right)}}{8}</div></html>
}}}

{{{id=10|
search_src("integrate")
///
<html><font color="black"><h2>Search Source Code: integrate</h2></font><font color="darkpurple"><ol><li><a href="/src/calculus/all.py"><tt>calculus/all.py</tt></a>
<li><a href="/src/calculus/calculus.py"><tt>calculus/calculus.py</tt></a>
<li><a href="/src/calculus/functional.py"><tt>calculus/functional.py</tt></a>
<li><a href="/src/calculus/tests.py"><tt>calculus/tests.py</tt></a>
<li><a href="/src/calculus/wester.py"><tt>calculus/wester.py</tt></a>
<li><a href="/src/functions/elementary.py"><tt>functions/elementary.py</tt></a>
<li><a href="/src/functions/functions.py"><tt>functions/functions.py</tt></a>
<li><a href="/src/functions/piecewise.py"><tt>functions/piecewise.py</tt></a>
<li><a href="/src/gsl/gsl_monte.pxi"><tt>gsl/gsl_monte.pxi</tt></a>
<li><a href="/src/gsl/integration.pyx"><tt>gsl/integration.pyx</tt></a>
<li><a href="/src/interfaces/kash.py"><tt>interfaces/kash.py</tt></a>
<li><a href="/src/interfaces/maxima.py"><tt>interfaces/maxima.py</tt></a>
<li><a href="/src/misc/functional.py"><tt>misc/functional.py</tt></a>
<li><a href="/src/misc/latex.py"><tt>misc/latex.py</tt></a>
<li><a href="/src/numerical/test.py"><tt>numerical/test.py</tt></a>
<li><a href="/src/rings/algebraic_real.py"><tt>rings/algebraic_real.py</tt></a>
<li><a href="/src/schemes/elliptic_curves/monsky_washnitzer.py"><tt>schemes/elliptic_curves/monsky_washnitzer.py</tt></a>
<li><a href="/src/schemes/elliptic_curves/padics.py"><tt>schemes/elliptic_curves/padics.py</tt></a>
<li><a href="/src/schemes/hyperelliptic_curves/hyperelliptic_padic_field.py"><tt>schemes/hyperelliptic_curves/hyperelliptic_padic_field.py</tt></a>
<li><a href="/src/server/notebook/tutorial.py"><tt>server/notebook/tutorial.py</tt></a>
</ol></font></html>
}}}

{{{id=68|
var('a,b,c,X')
s = solve(a*X^2 + b*X + c == 0, X)
show(s[0])
///
<html><div class="math">X  =  \frac{-\sqrt{ {b}^{2}  - {{4 \cdot a} \cdot c} } - b}{{2 \cdot a}}</div></html>
}}}

<h2>Finite Field Arithmetic</h2>

{{{id=4|
k.<a> = GF(2^8)
k
///
Finite Field in a of size 2^8
}}}

{{{id=64|
latex(k)
///
\mathbf{F}_{2^{8}}
}}}

{{{id=65|
show(k)
///
<html><div class="math">\mathbf{F}_{2^{8}}</div></html>
}}}

{{{id=62|
P.<x> = GF(3)['x']
while True:
  p = P.random_element(degree=5)
  if p.is_irreducible() and p.degree() == 5:
    break
p
///
x^5 + 2*x^4 + x + 1
}}}

{{{id=66|
p = p/p.leading_coefficient()
p
///
x^5 + 2*x^4 + x + 1
}}}

{{{id=63|
k.<a> = GF(3^5, modulus=p)
k.modulus()
///
x^5 + 2*x^4 + x + 1
}}}

<h2>Dense Linear Algebra over the Rationals and Integers</h2>

The NTRUEncrypt Public Key Cryptosystem is based on the hard mathematical problem of finding very short vectors in
lattices of very high dimension.

Generate a ntru-like lattice of dimension ($400 \times 400$), with the
coefficients $h_i$ chosen as random $130$ bits integers and parameter $q=35$:

$$
\left( \begin{array}{cccccccc}
 1 & 0 & \dots & 0 & h_0  &     h_1 & \dots & h_{d-1}\\
 0 & 1 & \dots & 0 & h_1  &     h_2 & \dots & h_0     \\
 \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots \\
 0 & 0 & \dots & 1 & h_{d-1} & h_0 & \dots & h_{d-1}\\
 0 & 0 & \dots & 0 & q   &      0  & \dots & 0     \\
 0 & 0 & \dots & 0 & 0   &      q  & \dots & 0     \\
 \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots \\
 0 & 0 & \dots & 0 & 0 &       0  & \dots & q     \\
\end{array} \right)
$$

{{{id=74|
from sage.libs.fplll.fplll import gen_ntrulike
A = gen_ntrulike(200,130,35)
time B = A.LLL()   # uses fpLLL by Damien Stehle
}}}

{{{id=15|
n = 100
a = random_matrix(QQ,n, n+1, num_bound=2^64, den_bound=1)
time a.echelonize()
///
Time: CPU 0.40 s, Wall: 0.41 s
}}}

{{{id=26|
%magma
n := 100;
a := RMatrixSpace(RationalField(), n,n+1)![Random(1,2^64): i in [1..n*(n+1)]];
time e := EchelonForm(a);
///
Time: 6.690
}}}

<h2>Dense Linear Algebra over Finite Fields</h2>

{{{id=69|
A = random_matrix(GF(127),2000,2000)
B = random_matrix(GF(127),2000,2000)
time C = A._multiply_linbox(B)
///
Time: CPU 4.19 s, Wall: 4.24 s
}}}

{{{id=70|
time A.echelonize()
///
CPU time: 4.35 s,  Wall time: 4.39 s
}}}

{{{id=35|
n = 5000
A = random_matrix(GF(2),n,n)
time E = A.echelon_form()
///
Time: CPU 0.29 s, Wall: 0.29 s
}}}

{{{id=36|
%magma
n := 5000;
k := GF(2);
A := Random(RMatrixSpace(k, n,n));
time E := EchelonForm(A);
///
Time: 1.080
}}}

{{{id=37|
n = 10000
A = random_matrix(GF(2),n,n)
time E = A.echelon_form()
///
Time: CPU 6.29 s, Wall: 6.38 s
}}}

{{{id=38|
%magma
n := 10000;
k := GF(2);
A := Random(RMatrixSpace(k, n,n));
time E := EchelonForm(A);
///
Time: 6.350
}}}

<h2>Sparse Linear Algebra over Finite Fields</h2>

{{{id=12|
A = random_matrix(GF(127),3000,3000,density=1.0/3000)
time A.echelonize()
A.rank()
///
Time: CPU 7.19 s, Wall: 7.46 s
1886
}}}

{{{id=91|
A = random_matrix(GF(127),3000,3000,density=10/3000)
b = random_matrix(GF(127),3000,1)
time c = A\b
(A*c) == b
///
Time: CPU 27.84 s, Wall: 28.31 s
True
}}}

{{{id=89|
n = 300
A = random_matrix(GF(127),n,n+100,sparse=True,density=2/n)
A.echelonize()
A.visualize_structure()
}}}

{{{id=90|
sr = mq.SR(4,2,2,4,gf2=True, allow_zero_inversions=True)
F,s = sr.polynomial_system() 
A,v = F.coefficient_matrix()
A.visualize_structure(maxsize=600)
}}}

<h2>Factoring</h2>

{{{id=71|
time factor(next_prime(2^40) * next_prime(2^300),verbose=0)
///
1099511627791 * 2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397533
CPU time: 3.77 s,  Wall time: 3.82 s
}}}

{{{id=73|
time ecm.factor(next_prime(2^40) * next_prime(2^300))
///
[1099511627791, 2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397533]
CPU time: 0.18 s,  Wall time: 0.60 s
}}}

{{{id=16|
v,t = qsieve(next_prime(2^90)*next_prime(2^91),time=True)
print v, t[:4]
///
[1237940039285380274899124357, 2475880078570760549798248507] 3.51
}}}

<h2>Elliptic Curves</h2>

{{{id=13|
e = EllipticCurve("37a") # Cremona Label
show(e)
///
<html><div class="math">y^2 + y = x^3 - x </div></html>
}}}

{{{id=75|
show(plot(e))
}}}

{{{id=58|
#e.aplist
e.a_invariants()
///
[0, 0, 1, -1, 0]
}}}

{{{id=67|
print e.aplist(20)
time n = e.aplist(10^6)
///
[-2, -3, -2, -1, -5, -2, 0, 0]
Time: CPU 4.70 s, Wall: 4.82 s
}}}

{{{id=77|
%magma
print GetVersion();
E := EllipticCurve([0,0,1,-1,0]);
print TracesOfFrobenius(E, 20);
time n := TracesOfFrobenius(E,10^6);
///
2 13 5

[ -2, -3, -2, -1, -5, -2, 0, 0 ]
Time: 8.360
}}}

{{{id=79|
E = e.change_ring(GF(997))
show(E.plot())
}}}

{{{id=78|
k = GF(next_prime(10^7))
E = EllipticCurve(k, [k.random_element(),k.random_element()])
E
///
Elliptic Curve defined by y^2  = x^3 + 897076*x + 4879343 over Finite Field of size 10000019
}}}

{{{id=82|
P = E.random_element()
P.order()
///
4998060
}}}

{{{id=81|
E.cardinality()
///
9996120
}}}

{{{id=86|
2*P + P
///
(4776249 : 6633546 : 1)
}}}

<h2>p-Adic Numbers</h2>

{{{id=102|
R = Zp(5)
e = R(3125346)
f = R(5*34234234)
t = cputime()
for i in xrange(10^6):
  z = e*f
cputime(t)
///
0.5019240000000309
}}}

{{{id=101|
%magma
R := pAdicRing(5);
e := R!3125346;
f := R!5*34234234;
time for i in [1..10^6] do
  z := e*f;
end for
///
Time: 0.990
}}}

{{{id=100|
gp.eval("e = %s"%(e._gp_().name()))
gp.eval("f = %s"%(f._gp_().name()))
///
'4*5 + 5^2 + 4*5^3 + 3*5^4 + 4*5^5 + 4*5^6 + 3*5^8 + 2*5^9 + 2*5^10 + 3*5^11 + O(5^21)'
}}}

{{{id=103|
%gp
gettime;
for(i=1,10^6,z=e*f);
gettime/1000.0
///
0.78300000000000000000000000000000000000
}}}

<h2>Graph Theory</h2>

{{{id=17|
D = graphs.DodecahedralGraph()
D.show()
}}}

{{{id=18|
D.show3d()
}}}

{{{id=19|
gamma = SymmetricGroup(20).random_element()
E = D.copy()
E.relabel(gamma)
D.is_isomorphic(E)
///
True
}}}

{{{id=20|
D.radius()
///
5
}}}

<h2>Univariate Polynomials over $\mathbf{Z}$</h2>

{{{id=22|
from sage.libs.flint.fmpz_poly import Fmpz_poly
}}}

{{{id=23|
deg = 32; coeff=64
f = Fmpz_poly([ZZ.random_element(2^coeff) for _ in range(deg)])
g = Fmpz_poly([ZZ.random_element(2^coeff) for _ in range(deg)])
}}}

{{{id=24|
%time
for _ in xrange(10^5):
   w = f*g
///
CPU time: 1.28 s,  Wall time: 1.29 s
}}}

{{{id=25|
gp.eval('f = Pol(%s)'%f.list())
_ = gp.eval('g = Pol(%s)'%g.list())
}}}

{{{id=27|
%gp
gettime; for(i=1,10^5,w=f*g); gettime/1000.0
///
8.4720000000000000000000000000000000000
}}}

{{{id=28|
%magma
R<x> := PolynomialRing(IntegerRing());
}}}

{{{id=29|
magma.eval('f := R!%s'%f.list())
_ = magma.eval('g := R!%s'%g.list())
}}}

{{{id=30|
%magma
time for i in [1..10^5] do w := f*g; end for;
///
Time: 3.870
}}}

{{{id=31|
# Uses NTL
R.<x> = ZZ[]
ff = R(f.list())
gg = R(g.list())
}}}

{{{id=39|
time for i in xrange(10^5): w = ff*gg
///
CPU time: 7.58 s,  Wall time: 7.68 s
}}}

<h2>Multivariate Polynomial Rings over Finite Fields</h2>

{{{id=92|
#In SAGE
P.<x,y,z> = PolynomialRing(QQ,3)
p = (x + y + z + 1)^20 # the Fateman fastmult benchmark
q = p + 1
time r = p*q
///
Time: CPU 1.06 s, Wall: 1.08 s
}}}

{{{id=32|
%magma
P<x,y,z> := PolynomialRing(RationalField(),3);
p:= (x + y + z + 1)^20;
q:= p + 1;
time r:= p*q;
///
Time: 0.530
}}}

{{{id=33|
#In SAGE
P.<x,y,z> = PolynomialRing(GF(32003),3)
p = (x + y + z + 1)^20 # the Fateman fastmult benchmark
q = p + 1
time r = p*q
///
Time: CPU 0.12 s, Wall: 0.12 s
}}}

{{{id=34|
%magma
P<x,y,z> := PolynomialRing(GF(32003),3);
p := (x + y + z + 1)^20;
q := p + 1;
time r := p*q;
///
Time: 0.310
}}}

{{{id=61|
P = PolynomialRing(GF(32003),10,'x')
I = sage.rings.ideal.Cyclic(P,7)
t = cputime()
gb = I.groebner_basis('libsingular:std')
print 'Sage/Singular', cputime(t)

I = sage.rings.ideal.Cyclic(P,7)
t = magma.cputime()
gb = I.groebner_basis('magma:GroebnerBasis')
print 'MAGMA', magma.cputime(t)
///
Sage/Singular 2.30265
MAGMA 0.48
}}}

<h2>Algebraic Cryptanalysis</h2>

{{{id=93|
sr = mq.SR(2,1,1,4,gf2=True)
sr
///
SR(2,1,1,4)
}}}

{{{id=95|
F,s = sr.polynomial_system()
F
///
Polynomial System with 104 Polynomials in 36 Variables
}}}

{{{id=94|
gb = F.groebner_basis()
Ideal(gb).variety()
///
[{x101: 0, x100: 0, x103: 1, x102: 1, k103: 1, x202: 1, x203: 0, x200: 1, x201: 1, w100: 1, w101: 1, w102: 1, w103: 0, k102: 1, k203: 0, k202: 1, k201: 1, k200: 0, s001: 1, s000: 1, s003: 1, s002: 0, k001: 1, k000: 0, k003: 0, k002: 0, w203: 1, w202: 1, w201: 0, w200: 0, s100: 1, s101: 1, s102: 1, s103: 0, k100: 0, k101: 0}]
}}}

{{{id=96|
s
///
{k001: 1, k000: 0, k003: 0, k002: 0}
}}}

{{{id=97|
A,v = F.coefficient_matrix()
}}}

{{{id=99|
A.visualize_structure()
}}}

{{{id=104|

}}}