Sage 2.11 Release Tour

Sage 2.11 was released on March 30, 2008. For the official, comprehensive release notes, see the HISTORY.txt file that comes with the release. For the latest changes see [http://sagemath.org/announce/sage-2.11.txt sage-2.11.txt].

ATLAS

Michael Abshoff and Burcin Erocal upgraded ATLAS to the 3.8.1 release. In addition tuning info for 32 bit Prescott CPUs as well as Powerbook G4s under Linux was added.

zn_poly

David Harvey's zn_poly library is now a standard package for Sage. zn_poly is a new C library for polynomial arithmetic in (Z/nZ)[x] where 3 \le n \le ULONG\_MAX (i.e. any machine-word-sized modulus). The main benefit is speed. Three examples on sage.math, from my current development code (this code is not yet in the spkg):

The library is used so far only to compute the zeta function for hyperelliptic curves.

small roots method for polynomials mod N (N composite)

Coppersmith's method for finding small roots of univariate polynomials modulo N where N is composite was implemented. An application of this method is to consider RSA. We are using 512-bit RSA with public exponent e=3 to encrypt a 56-bit DES key. Because it would be easy to attack this setting if no padding was used we pad the key K with 1s to get a large number.

   1 sage: Nbits, Kbits = 512, 56
   2 sage: e = 3

We choose two primes of size 256-bit each.

   1 sage: p = 2^256 + 2^8 + 2^5 + 2^3 + 1
   2 sage: q = 2^256 + 2^8 + 2^5 + 2^3 + 2^2 + 1
   3 sage: N = p*q
   4 sage: ZmodN = Zmod( N )

We choose a random key

   1 sage: K = ZZ.random_element(0, 2^Kbits)

and pad it with 512-56=456 1s

   1 sage: Kdigits = K.digits()
   2 sage: M = [0]*Kbits + [1]*(Nbits-Kbits)
   3 sage: for i in range(len(Kdigits)): M[i] = Kdigits[i]
   4 sage: M = ZZ(M, 2)

Now we encrypt the resulting message:

   1 sage: C = ZmodN(M)^e

To recover K we consider the following polynomial modulo N:

   1 sage: P.<x> = PolynomialRing(ZmodN)
   2 sage: f = (2^Nbits - 2^Kbits + x)^e - C

and recover its small roots:

   1 sage: Kbar = f.small_roots()[0]
   2 sage: K == Kbar
   3 True

Generic Multivariate Polynomial Arithmetic

Joel Mohler improved the efficiency of the generic multivariate polynomial arithmetic in Sage. Before his patch was applied:

   1 sage: R.<x,y,z,a,b>=ZZ[]
   2 sage: f=prod([2*g^2-4*g+8 for g in R.gens()])
   3 sage: %time _=f*f
   4 CPU times: user 2.23 s, sys: 0.00 s, total: 2.23 s
   5 Wall time: 2.24

and after:

   1 sage: R.<x,y,z,a,b>=ZZ[]
   2 sage: f=prod([2*g^2-4*g+8 for g in R.gens()])
   3 sage: %time _=f*f
   4 CPU times: user 0.22 s, sys: 0.00 s, total: 0.22 s
   5 Wall time: 0.22

k-Schur Functions and Non-symmetric Macdonald Polynomials

k-Schur functions s_\lambda^{(k)} are a relatively new family of symmetric functions which play a role in \mathbb{Z}[h_1, \ldots, h_k] as the Schur functions s_\lambda do in \Lambda. The k-Schur functions, amongst other things, provide a natural basis for the quantum cohomology of the Grassmannian. The k-Schur functions can be used like any other symmetric functions and are created with kSchurFunctions.

   1 sage: ks3 = kSchurFunctions(QQ,3); ks3
   2 k-Schur Functions at level 3 over Univariate Polynomial Ring in t over Rational Field
   3 sage: s(ks3([3,2,1]))
   4 s[3, 2, 1] + t*s[4, 1, 1] + t*s[4, 2] + t^2*s[5, 1]

Non-symmetric Macdonald polynomials in type A can now be accessed in Sage. The polynomials are computed from the main theorem in "A Combinatorial Formula for the Non-symmetric Macdonald Polynomials" by Haglun, Haiman, and Loehr. ( http://arxiv.org/abs/math.CO/0601693 )

   1 sage: from sage.combinat.sf.ns_macdonald import E
   2 sage: E([0,1,0])
   3 ((-t + 1)/(-q*t^2 + 1))*x0 + x1
   4 sage: E([1,1,0])
   5 x0*x1

Bugfixes/Upgrades (incomplete)