Sage for Mathematical and Cryptographic Research

http://www.sagemath.org

William Stein^{1} Martin Albrecht^{2}

1Department of Mathematics University of Washington, Seattle

2Information Security Group Royal Holloway, University of London

Bristol, 10.November 2007

Outline Outline Mission Statement

Provide an open (GPL-compatible), high-quality, and free viable alternative to Magma, Mathematica, Maple and MATLAB (in that order).

To achieve this do not reinvent the wheel but reuse as much existing building blocks as possible and make sure the result is rigorously tested, easy to modify by the end user and very well documented.

Also create a helpful environment for users to get help (mailinglists, irc-channel, meetings).

What is Sage?

Sage is a mathematics software package developed by a worldwide community of developers.

1 a distribution of the best free, open-source mathematics software available (Sage 2.8.9 ships roughly 70 third-party packages) that is easy to compile and/or install on Linux, OS X, Solaris (soon) and Windows (via virtualisation)

2 a unified interface to many free and commercial mathematics software

packages (e.g. Magma, Mathematica) 3 the mathematics package which covers the widest area of functionality

ever (see: 1.) including new implementations not yet found elsewhere.

Welcome to Sage:

−

| SAGE V e r s i o n 2 . 8 . 1 1 , R e l e a s e Date : 2007−11−02  |
| Type notebook ( ) f o r the GUI , and l i c e n s e ( ) f o r i n f o r m a t i o n .  |

−

sage : 1 + 1

Timeline

1997–1999 (Berkeley) HECKE – C++ (modular forms) 1999–2005 (Berkeley, Harvard) I wrote over 25,000 lines of Magma code.

Magma is incredibly powerful! But the languages of Magma, Mathematica, and Maple are old-fashioned and painful compared to Python. I need to be able to see inside and change anything in my software in order to be the best in the world at my research. Magma is frustrating and is a terrible longterm investment.

Feb 2005 I released SAGE-0.1 — a Python math library. Feb 2006 UCSD SAGE Days 1 – SAGE 1.0.

October 2006 U Washington SAGE Days 2 workshop. March 2007 UCLA SAGE Days 3 workshop. June 2007 U Washington SAGE Days 4 workshop.

October 2007 Clay Math Institute SAGE Days 5 workshop. Now Heilbronn Institute SAGE Days 6 (you are here :-)) Now SAGE-2.8.12; over 100 contributors to SAGE.

Outline Overview I

see http://www.sagemath.org:9001/cando

Commutative Algebra commutative algebra over 𝔽_{p^{n}} using Singular, basic arithmetic over arbitrary rings, very fast basic arithmetic over 𝔽_{p^{n}}, boolean polynomial rings (soon via PolyBoRi), quotient rings over multivariate polynomial rings, global & local orderings

Linear Algebra dense linear algebra over 𝔽_{q} using LinBox, M4RI (for 𝔽_{2}), and custom code, and sparse linear algebra over 𝔽_{q} via custom code and LinBox (e.g. sparse solver). Numerical dense linear algebra via Numpy and GSL. Matrix structure visualisation.

Group Theory permutations groups, abelian groups, matrix groups (in

particular, classical groups over finite fields)

Combinatorics many basic functions, many of Sloane’s functions are

implemented.

Graph Theory construction, directed graphs, labeled graphs. 2d and 3d plotting of graphs using an optimized implementation of the spring layout algorithm. constructors for all standard families of graphs, graph isomorphism testing, automorphism group computation

Overview II

see http://www.sagemath.org:9001/cando

Number Theory compute Mordell-Weil groups of (many) elliptic curves using both invariants and algebraic 2-descents, a wide range of number theoretic functions, optimized modern quadratic sieve for factoring integers n = p · q, optimized implementation of the elliptic curve factorization method, modular symbols for general weight, character, Gamma1, and GammaH, modular forms for general weight ≥ 2

Elliptic Curves all standard invariants of elliptic curves over ℚ, division polynomials, etc. , compute the number of points on an elliptic curve modulo p for all primes p less than a million in seconds, optimized implementation of the Schoof-Elkies-Atkin point counting algorithm for counting points modulo p when p is large, complex and p-adic L-functions of elliptic curves. Can compute p-adic heights and regulators for p < 100000 in a reasonable amount of time.

p-adic Numbers extensive support for arithmetic with a range of different

models of p-adic arithmetic. Plotting very complete 2d plotting functionality similar to

Mathematica’s, limited 3d plotting via an included ray tracer.

New Functionality

free re-implementation of Nauty’s graph isomorphism algorithm certain models of arithmetic with p-adic numbers & polynomial rings over them task farming distributed computing (DSage) modular symbols, modular forms, modular abelian varieties computing with Dirichlet characters Eisenstein series enumeration arithmetic on jacobians of curves quaternion algebras p-adic L-functions of elliptic curves in a lot of generality, with proven precision fast computation of p-adic heights on elliptic curves Coleman integration Duursma zeta functions of linear codes permanents of rectangular matrices over general rings

Web-based Notebook Interface

public notebooks available at http://www.sagenb.org

graphical user interface 2d plotting LaTeX typesetting remote access worksheet sharing interface to 3rd party systems like e.g. Magma

Basic Finite Field Arithmetic

finite fields 𝔽_{p^{n}} for arbitrary sizes of p and n < 2^{32}. finite extension fields of order < 2^{16} implemented using Zech logs (fast!) larger 𝔽_{q} implemented using Pari’s (slow) or NTL’s (reasonable) polynomial representation mp𝔽_{q} ?

http://hyperelliptic.org/SPEED/slides/Gaudry Thome mpFq.pdf

sage : k.<a> = GF ( 2 ˆ 8 ) ; k
F i n i t e F i e l d i n a o f s i z e 2ˆ 8
sage : P.<x> = GF ( 3 ) [ ’ x ’ ]
sage : p = P . random element ( d e g r e e =5); p
2∗ x ˆ 5 + 2∗ x ˆ 2 + 2∗ x + 1
sage : p/2 # monic
x ˆ 5 + x ˆ 2 + x + 2
sage : k.<a> = GF(3ˆ 5 , modulus=p )
sage : k . modulus ( )
x ˆ 5 + x ˆ 2 + x + 2

Dense Linear Algebra over Finite Fields

specialised implementation for prime fields

uses LinBox’s BLAS arithmetic (see Clement Pernet’s talk) for some operations Todo: extension fields (LinBox supports them!)

sage : A = random matrix (GF( 1 2 7 ) , 2 0 0 0 , 2 0 0 0 )
sage : B = random matrix (GF( 1 2 7 ) , 2 0 0 0 , 2 0 0 0 )
sage : %time C = A . m u l t i p l y l i n b o x (B)
CPU t i m e s : u s e r 4 . 1 5 s , s y s : 0 . 0 0 s , t o t a l : 4 . 1 5 s
Wall time : 4 . 1 9 # time depends on i n s t a l l e d BLAS
sage : time A . e c h e l o n i z e ( )
CPU t i m e s : u s e r 4 . 3 0 s , s y s : 0 . 0 3 s , t o t a l : 4 . 3 4 s
Wall time : 4 . 5 1

Dense Linear Algebra over GF(2)

M4RI package by Gregory Bard uses packed representation and Gray-Codes multiplication & echolonisation O(n^{3}/log(n)) fastest implementation up to 5.000 × 5.000 – 10.000 × 10.000 matrices

sage : A = random matrix (GF( 2 ) , 2 0 0 0 0 , 2 0 0 0 0 )
sage : time A . e c h e l o n i z e ( )
CPU t i m e s : u s e r 48.06 s , s y s : 0 . 0 4 s , t o t a l : 48.10 s
Wall time : 48.46

Strassen (O(n^{2.7})) support in the works

Sparse Linear Algebra over Finite Fields

generic sparse matrix classes and a special 𝔽_{p} class custom code for computing the reduced row echelon form

sage : A = random matrix (GF(127) ,10000 ,10000 , d e n s i t y =3/10000)
sage : time A . e c h e l o n i z e ( )
CPU t i m e s : u s e r 53.13 s , s y s : 0 . 1 5 s , t o t a l : 53.28 s
Wall time : 59.18
sage : A . rank ( )

9307

sparse matrix solver via LinBox(see Clement Pernet’s talk):

sage : A = random matrix (GF( 1 2 7 ) , 3 0 0 0 , 3 0 0 0 , d e n s i t y =10/3000)
sage : time c = A\b
CPU t i m e s : u s e r 35.12 s , s y s : 0 . 5 9 s , t o t a l : 35.71 s
Wall time : 38.75
sage : (A∗ c ) = b

True

Ralf Weinmann working on integrating John Cremonas fast g0n sparse matrix code

Matrix Visualisation

A.visualize structure()

Factoring

factor uses PARI

sage : time f a c t o r (2ˆ 197 + 1)
CPU t i m e s : u s e r 2 . 0 8 s , s y s : 0 . 0 4 s , t o t a l : 2 . 1 2 s
Wall time : 2 . 1 7
3 ∗ 197002597249 ∗ 1348959352853811313 ∗ 251951573867253012259144010843

ecm uses GMP-ECM by Paul Zimmermann et al.

sage : time ecm . f a c t o r ((2ˆ 197 + 1)/3)
[197002597249 , 1348959352853811313 , 251951573867253012259144010843]
CPU t i m e s : u s e r 0 . 0 1 s , s y s : 0 . 1 0 s , t o t a l : 0 . 1 0 s
Wall time : 4 . 4 1

qsieve uses Bill Hart’s quadratic sieve implementation

sage : v , t = q s i e v e ( n e x t p r i m e (10ˆ 31)∗ n e x t p r i m e ( 1 0 ˆ 3 0 ) , time=True )
sage : t
’ 10.60 u s e r 0.37 system 0 : 1 1 . 1 3 e l a p s e d 98%CPU (0 a v g t e x t +0avgdata 0 maxresident )k ’
sage : v
[1000000000000000000000000000057 , 10000000000000000000000000000033]

DistributedFactor combines ECM, qsieve and trial division; written by Yi Qiang and Robert Bradshaw.

Lattice Reduction

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 × 400), with the coefficients h_{i} chosen as random 130 bits integers and parameter q = 35:

1 0 … 0  h_{0} h_{1} … h_{d−1}
0 1 … 0  h_{1} h_{2} … h_{0}
. . . . . . . . . . . . . . . . . . . . . . . .
0 0 … 1 h_{d−1} h_{0} … h_{d−1}
0 0 … 0  q  0 …  0
0 0 … 0  0  q …  0
. . . . . . . . . . . . . . . . . . . . . . . .
0 0 … 0  0  0 …  q
sage : A = g e n n t r u l i k e ( 2 0 0 , 1 3 0 , 3 5 )
sage : time B = A . LLL ( ) #fpLLL by Damien S t e h l e
CPU time : 14.91 s , Wall time : 15.06

Elliptic Curves over 𝔽_{q}

sage : k = GF( n e x t p r i m e ( 1 0 ˆ 7 ) )
sage : E = E l l i p t i c C u r v e ( k , \
…  [ k . random element ( ) , k . random element ( ) ] )
sage : E
E l l i p t i c Curve d e f i n e d by y ˆ 2 = x ˆ 3 + 8412640∗ x + 9921951 \
o v e r F i n i t e F i e l d o f s i z e 10000019
sage : P = E . random element ( )
sage : time P . o r d e r ( )

5002257

sage : E . c a r d i n a l i t y ( )

10004514

sage : 2∗P + P
(251564 : 3681217 : 1)

Graphs – very nice.

Commutative Algebra

very fast basic arithmetic for multivariate polynomials over 𝔽_{q}. fast Gröbner basis computation and highlevel ideal operations specialized very fast Gröbner basis computation in

𝔽_{2}[x_{1}, …, x_{n}]/⟨x_{1}^{2} + x_{1}, …, x_{n}^{2} + x_{n}⟩

very soon (see Michael Brickenstein’s talk)

sage : P.<x , y , z> = P o l y n o m i a l R i n g (GF( 3 2 0 0 3 ) , 3 )
sage : p = ( x + y + z + 1)ˆ 20 # the Fateman f a s t m u l t benchmark
sage : q = p + 1
sage : t = cputime ( )
sage : r = p∗q
sage : cputime ( t )

0 . 2 8

Algebraic Attacks

Sage provides equation systems for algebraic cryptanalysis:

sage : s r = mq . SR ( 2 , 1 , 1 , 4 , g f 2=True )
sage : F , s = s r . p o l y n o m i a l s y s t e m ( )
sage : s
{ k003 : 1 , k002 : 1 , k001 : 1 , k000 : 1}
sage : gb = F . g r o e b n e r b a s i s ( )
sage : V = I d e a l ( gb ) . v a r i e t y ( ) ; V [ 0 ]

…

k001 : 1 , k000 : 1 , k003 : 1 , k002 : 1 ,

…

sage : s r = mq . SR ( 1 0 , 4 , 4 , 8 , s t a r=True , aes mode=True )
sage : F , s = s r . p o l y n o m i a l s y s t e m ( ) ; F
P o l y n o m i a l System with 8576 P o l y n o m i a l s i n 4288 V a r i a b l e s
sage : F . g r o e b n e r b a s i s ( ) # i f t h i s t e r m i n a t e s => AES broken : −)

We need a slide about dsage that mentions John Voights recent big computations involving number field enumeration.

Live Demo

Outline