Sage for Mathematics : a Primer.. / JST CREST. s-yokoyama@imi.kyushu-u.ac.jp 2013 1 15 / IIJ
Sage for Mathematics : a Primer 1 Sage Sage Sage Notebook Sage Salvus 2 Sage Sage Cryptosystem Sage
Sage - Sage 3 factor Pari ecm.factor GMP-ECM, Sage qsieve Sage by Bill Hart (ms) factor 1260 ecm.factor 404 qsieve 1121 sage: p,q=next prime(2^72), next prime(2^84) Magma ECM
Magma Magma Version 2.18-7 Integer main factorization (primality of factors will be proved) Effort: 3 Seed: 295384768 59 Number: 91343852333181432388020458408574648339360907309 Pollard Rho Trials: 8191 Number: 91343852333181432388020458408574648339360907309 (47 digits) No factor found Time: 0.015 1 composite number remaining ECM x: 91343852333181432388020458408574648339360907309 (47 digits) Initial B1: 5000, limit: 7177 Initial Pollard p - 1, B1: 45000 Step 1; B1: 5000 [7177], digits: 47, elapsed time: 0.109 Step 10; B1: 5650 [7177], digits: 47, elapsed time: 0.967 Step 20; B1: 6420 [7177], digits: 47, elapsed time: 1.809 Pollard p - 1, B1: 65160, elapsed time: 2.683 Pollard p + 1, B1: 21720, elapsed time: 2.761 Pollard p + 1, B1: 21720, elapsed time: 2.808 Pollard p + 1, B1: 21720, elapsed time: 2.839 No factor found Total ECM time: 2.886 MPQS x: 91343852333181432388020458408574648339360907309 (47 digits) Factor 1: 4722366482869645213711 (22 digits) Factor 2: 19342813113834066795298819 (26 digits) Total MPQS Time: 1.575 [ <4722366482869645213711, 1>, <19342813113834066795298819, 1> ] Time: 4.477 ------------------------------------ Pollard ρ, ECM MPQS. Pollard ρ.
Magma Sage beats Magma List of computations where Sage is noticeably faster than Magma http://wiki.sagemath.org/sagebeatsmagma
Magma Is it worth learning Magma?... is definitely still yes, since there are still many algorithms today in arithmetic geometry that are only implemented in Magma, and available nowhere else (definitely not in Macaulay2, Singular, Mathematica, Sage). It will only take a few days, and you will have a better sense of what is possible. The exact same argument applies to Sage as well. Learn both. For Sage, you basically should: learn Python, and go through the Sage tutorial, which takes 2-3 hours. William Stein, Jan. 17th, 2011
1. 2 Sage Cryptosystem David Kohel s course note Cryptography (2007).
1. 1/9 Q sage: E = EllipticCurve([1,2,3,4,5]); E Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Rational Field sage: E.conductor() 10351
1. 2/9 j-, Weierstrass sage: E = EllipticCurve([0, -1, 1, -10, -20]) sage: E Elliptic Curve defined by y^2 + y = x^3 - x^2-10*x - 20 over Rational Field sage: E.j_invariant() -122023936/161051 sage: E.short_weierstrass_model() Elliptic Curve defined by y^2 = x^3-13392*x - 1080432 over Rational Field sage: E.discriminant() -161051 F p, sage: E = EllipticCurve(GF(5),[0, -1, 1, -10, -20]) sage: E.short_weierstrass_model() Elliptic Curve defined by y^2 = x^3 + 3*x + 3 over Finite Field of size 5 sage: E.j_invariant() 4
1. 3/9 F q sage: E = EllipticCurve(GF(5),[0, -1, 1, -10, -20]) sage: E Elliptic Curve defined by y^2 + y = x^3 + 4*x^2 over Finite Field of size 5 sage: E.points() [(0 : 0 : 1), (0 : 1 : 0), (0 : 4 : 1), (1 : 0 : 1), (1 : 4 : 1)] sage: E.cardinality() 5 sage: G = E.abelian_group() sage: G Additive abelian group isomorphic to Z/5 embedded in Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 + 4*x^2 over Finite Field of size 5 sage: G.permutation_group() Permutation Group with generators [(1,2,3,4,5)]
1. 4/9 sage: E = EllipticCurve([0, -1, 1, -10, -20]) sage: E Elliptic Curve defined by y^2 + y = x^3 - x^2-10*x - 20 over Rational Field sage: E.conductor() 11 sage: E.anlist(20) [0, 1, -2, -1, 2, 1, 2, -2, 0, -2, -2, 1, -2, 4, 4, -1, -4, -2, 4, 0, 2] sage: E.analytic_rank() 0 anlist E eigen cuspform Fourier rank, BSD
1. 5/9 sage: E = EllipticCurve(GF(37), [1,0]) sage: E Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 37 sage: E.plot(pointsize=45)
1. 6/9 counting F p Baby-step Giant-step Schoof-Elkies-Atkin SEA 1. simple enumeration sage: x,y,z = PolynomialRing(GF(5), 3, xyz ).gens() sage: C = Curve(y^2*z^7 - x^9 - x*z^8); C Projective Curve over Finite Field of size 5 defined by -x^9 + y^2*z^7 - x*z^8 sage: C.rational_points() [(0 : 0 : 1), (0 : 1 : 0), (2 : 2 : 1), (2 : 3 : 1), (3 : 1 : 1), (3 : 4 : 1)] sage: C.rational_points(algorithm="bn") [(0 : 0 : 1), (0 : 1 : 0), (2 : 2 : 1), (2 : 3 : 1), (3 : 1 : 1), (3 : 4 : 1)] bn brnoeth Singular 1 C. Doche, S. Duquesne Pari
1. 7/9 Singular Riemann-Roch space sage: x, y, z = PolynomialRing(GF(5), 3, xyz ).gens() sage: f = x^7 + y^7 + z^7 sage: X = Curve(f); pts = X.rational_points() sage: D = X.divisor([ (3, pts[0]), (-1,pts[1]), (10, pts[5]) ]) sage: X.riemann_roch_basis(D) [(-2*x + y)/(x + y), (-x + z)/(x + y)] Singular brnoeth.lib sage: singular.lib( brnoeth.lib ) sage: _ = singular.ring(5, (x,y), lp ) sage: print singular.eval("list X = Adj_div(-x5+y2+x);") Computing affine singular points... Computing all points at infinity... Computing affine singular places... Computing singular places at infinity... Computing non-singular places at infinity... Adjunction divisor computed successfully The genus of the curve is 2 sage: print singular.eval("x = NSplaces(1,X);") Computing non-singular affine places of degree 1...
1. 8/9 GF(8) sage: x, y, z = PolynomialRing(GF(8, a ), 3, xyz ).gens() sage: f = x^3*y+y^3*z+x*z^3 sage: C = Curve(f); C Projective Curve over Finite Field in a of size 2^3 defined by x^3*y + y^3*z + x*z^3 sage: C.rational_points() [(0 : 0 : 1), (0 : 1 : 0), (1 : 0 : 0), (1 : a : 1), (1 : a^2 : 1), (1 : a^2 + a : 1), (a : 1 : 1), (a : a^2 : 1), (a : a^2 + 1 : 1), (a + 1 : a + 1 : 1), (a + 1 : a^2 : 1), (a + 1 : a^2 + a + 1 : 1), (a^2 : 1 : 1), (a^2 : a^2 + a : 1), (a^2 : a^2 + a + 1 : 1), (a^2 + 1 : a + 1 : 1), (a^2 + 1 : a^2 + 1 : 1), (a^2 + 1 : a^2 + a : 1), (a^2 + a : 1 : 1), (a^2 + a : a : 1), (a^2 + a : a + 1 : 1), (a^2 + a + 1 : a : 1), (a^2 + a + 1 : a^2 + 1 : 1), (a^2 + a + 1 : a^2 + a + 1 : 1)]
1. 9/9 / C.points() sage: K.<a> = GF(9, a ) sage: x = polygen(k) sage: C = HyperellipticCurve(x^7 - x^5-2, x^2 + a) sage: C._points_fast_sqrt() [(0 : 1 : 0), (a + 1 : a : 1), (a + 1 : a + 1 : 1), (2 : a + 1 : 1), (2*a : 2*a + 2 : 1), (2*a : 2*a : 1), (1 : a + 1 : 1)] Jac(C) QQ Q sage: from sage.schemes.jacobians.abstract_jacobian import Jacobian_generic sage: P2.<x, y, z> = ProjectiveSpace(QQ, 2) sage: C = Curve(x^3 + y^3 + z^3) sage: J = Jacobian_generic(C); J Jacobian of Projective Curve over Rational Field defined by x^3 + y^3 + z^3 sage: type(j) <class sage.schemes.jacobians.abstract_jacobian.jacobian_generic_with_ category >
2. Sage Cryptosystem 1/15 Cryptosystem + SymmetricKeyCryptosystem + HillCryptosystem + LFSRCryptosystem + ShiftCryptosystem + ShrinkingGeneratorCryptosystem + SubstitutionCryptosystem + TranspositionCryptosystem + VigenereCryptosystem + PublicKeyCryptosystem
2. Sage Cryptosystem 2/15 String sage: S = AlphabeticStrings() sage: S Free alphabetic string monoid on A-Z sage: H = HexadecimalStrings() sage: H Free hexadecimal string monoid sage: B = BinaryStrings() sage: B Free binary string monoid, sage: S.gens() (A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z) sage: H.gens() (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f) sage: B.gens() (0, 1)
2. Sage Cryptosystem 3/15 encoding sage: S.encoding( abc ) ABC sage: H.encoding( abc ) 616263 sage: B.encoding( abc ) 011000010110001001100011 decoding sage: S.encoding( abc ).decoding() ABC sage: H.encoding( abc ).decoding() abc sage: B.encoding( abc ).decoding() abc
2. Sage Cryptosystem 4/15 encryption / decryption * sage.crypto.classical.shiftcryptosystem sage: S = ShiftCryptosystem(AlphabeticStrings()); S Shift cryptosystem on Free alphabetic string monoid on A-Z sage: plaintext = S.encoding("Shift cryptosystem generalizes Caesar cipher.") sage: plaintext SHIFTCRYPTOSYSTEMGENERALIZESCAESARCIPHER sage: key = 7 sage: ciphertext = S.enciphering(key, plaintext); ciphertext ZOPMAJYFWAVZFZALTNLULYHSPGLZJHLZHYJPWOLY sage: S.deciphering(key, ciphertext) SHIFTCRYPTOSYSTEMGENERALIZESCAESARCIPHER sage: S.deciphering(key, ciphertext) == plaintext True
2. Sage Cryptosystem 5/15 ASCII encodings +----------------------------------------------------+ A B C D E F G H I J K L M 65 66 67 68 69 70 71 72 73 74 75 76 77 +----------------------------------------------------+ N O P Q R S T U V W X Y Z 78 79 80 81 82 83 84 85 86 87 88 89 90 +----------------------------------------------------+ HELLOWORLD RSA Cryptosystem,. ASCII m = 72697676798779827668
2. Sage Cryptosystem 6/15 RSA / Algorithm (Rivest-Shamir-Adleman) 1 2 p, q, n = pq. 2 gcd(e, φ(n)) = 1 e Z >0... 3 de 1 (mod φ(n)) d Z. 4 (n, e), (p, q, d). 5 0 m(< n) c m e (mod n). 6 m c d (mod n)....
2. Sage Cryptosystem 7/15 1 sage: p = (2^31) - 1; p 2147483647 sage: is_prime(p) True sage: q = (2^61) - 1; q 2305843009213693951 sage: is_prime(q) True sage: n = p*q ; n 4951760154835678088235319297
2. Sage Cryptosystem 8/15 2 sage: e = ZZ.random_element(euler_phi(n)) sage: while gcd(e, euler_phi(n))!= 1:... e = ZZ.random_element(euler_phi(n))... sage: e # random 1850567623300615966303954877 sage: e < n True *double enter while
2. Sage Cryptosystem 9/15 3 n = 4951760154835678088235319297 e = 1850567623300615966303954877 φ(n) = 4951760152529835076874141700. sage: bezout = xgcd(e, euler_phi(n)); bezout (1, 4460824882019967172592779313, -1667095708515377925087033035) sage: d = Integer(mod(bezout[1], euler_phi(n))) ; d 4460824882019967172592779313 sage: mod(d*e, euler_phi(n)) 1 xgcd(x,y) (g,s,t), Bézout identity g = gcd(x, y) = sx + ty
2. Sage Cryptosystem 10/15 4 (n, e) n = 4951760154835678088235319297 e = 1850567623300615966303954877 (p, q, d) p = 2147483647 q = 2305843009213693951 d = 4460824882019967172592779313
2. Sage Cryptosystem 11/15 5 m = 72697676798779827668 c m e (mod n) sage: mod(m^e, n) ---------------------------------------------------- RuntimeError Traceback (most recent call last) /home/mvngu/<ipython console> in <module>() /home/mvngu/usr/bin/sage-3.1.4/local/lib/python2.5/ site-packages/sage/rings/integer.so in sage.rings.integer.integer. pow (sage/rings/integer.c:9650)() RuntimeError: exponent must be at most 2147483647,
2. Sage Cryptosystem 12/15 5 power mod binary rep. modular exponentiation using repeated squaring sage: c = power_mod(m, e, n); c 630913632577520058415521090 def power_mod(a, b, n): d = 1 for i in list(integer.binary(b)): d = mod(d * d, n) if Integer(i) == 1: d = mod(d * a, n) return Integer(d)
2. Sage Cryptosystem 13/15 5 Pythonic Python def power_mod(a, b, n): d = 1 for i in reversed(b.digits(base=2)): d = mod(d * d, n) if i == 1: d = mod(d * a, n) return Integer(d) Sage def power_mod(a, b, n): d = 1 for i in list(integer.binary(b)): d = mod(d * d, n) if Integer(i) == 1: d = mod(d * a, n) return Integer(d)
2. Sage Cryptosystem 14/15 6 c = 630913632577520058415521090 m c d (mod n) sage: power_mod(c, d, n) 72697676798779827668 sage: m 72697676798779827668 HELLOWORLD +----------------------------------------+ H E L L O W O R L D 72 69 76 76 79 87 79 82 76 68 +----------------------------------------+
2. Sage Cryptosystem 15/15 sage: def rsa(bits):... # only prove correctness up to 1024 bits... proof = (bits <= 1024)... p = next_prime(zz.random_element(2**(bits//2 +1)),... proof=proof)... q = next_prime(zz.random_element(2**(bits//2 +1)),... proof=proof)... n = p * q... phi_n = (p-1) * (q-1)... while True:... e = ZZ.random_element(1,phi_n)... if gcd(e,phi_n) == 1: break... d = lift(mod(e,phi_n)^(-1))... return e, d, n... sage: def encrypt(m,e,n):... return lift(mod(m,n)^e)... sage: def decrypt(c,d,n):... return lift(mod(c,n)^d)...
Sage Quick Reference Cards http://wiki.sagemath.org/quickref Sage Reference Manual http://www.sagemath.org/doc/reference/ HTML
2013 Python Year!!