Archive

Archive for February, 2010

Blum-Goldwasser probabilistic encryption

24 February 2010 1 comment

Sage 4.3.3 merged an implementation of the Blum-Goldwasser probabilistic public-key encryption scheme described in the following paper:

I wrote that implementation based on a public domain version by Mike Hogan and David Joyner. See ticket #7746 for background information. A big thank you to David Joyner for reviewing that ticket and many suggestions for improvement. The current implementation in Sage 4.3.3 follows the description of the Blum-Goldwasser scheme as described in the following book:

This implementation is documented in the Sage reference manual. In this post, I will provide some usage examples.

The Blum-Goldwasser encryption and decryption algorithms make use of the least significant bit of a binary string. A related concept is the $k$ least significant bits of a binary string. For example, given a positive integer $n$, let $b = b_0 b_1 \cdots b_{m-1}$ be the binary representation of $n$ so that $b$ is a binary string of length $m$. Then the least significant bit of $n$ is $b_{m-1}$. If $0 < k \leq m$, then the $k$ least significant bits of $n$ are $b_{m-1-k} b_{m-k} \cdots b_{m-1}$. The least significant bit of an integer is also referred to as its parity bit, because this bit determines whether the integer is even or odd. In the following example, we obtain the least significant bit of an integer:

sage: from sage.crypto.util import least_significant_bits
sage: least_significant_bits(123, 1)
[1]
sage: least_significant_bits(123, 4)
[1, 0, 1, 1]

The following encryption/decryption example is taken from Example 8.57, pages 309–310 of (Menezes et al. 1996):

sage: from sage.crypto.public_key.blum_goldwasser import BlumGoldwasser
sage: bg = BlumGoldwasser(); bg
The Blum-Goldwasser public-key encryption scheme.
sage: p = 499; q = 547
sage: pubkey = bg.public_key(p, q); pubkey
272953
sage: prikey = bg.private_key(p, q); prikey
(499, 547, -57, 52)
sage: P = "10011100000100001100"
sage: C = bg.encrypt(P, pubkey, seed=159201); C
([[0, 0, 1, 0], [0, 0, 0, 0], [1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0]], 139680)
sage: M = bg.decrypt(C, prikey); M
[[1, 0, 0, 1], [1, 1, 0, 0], [0, 0, 0, 1], [0, 0, 0, 0], [1, 1, 0, 0]]
sage: M = "".join(map(lambda x: str(x), flatten(M))); M
'10011100000100001100'
sage: M == P
True

Now generate a pair of random public/private keys. Use the public key to encrypt a plaintext. Then decrypt the resulting ciphertext using the private key. Finally, compare the decrypted message with the original plaintext.

sage: from sage.crypto.public_key.blum_goldwasser import BlumGoldwasser
sage: from sage.crypto.util import bin_to_ascii
sage: bg = BlumGoldwasser()
sage: pubkey, prikey = bg.random_key(10**4, 10**6)
sage: P = "A fixed plaintext."
sage: C = bg.encrypt(P, pubkey)
sage: M = bg.decrypt(C, prikey)
sage: bin_to_ascii(flatten(M)) == P
True

If $(p, q, a, b)$ is a private key, then $n = pq$ is the corresponding public key. Furthermore, we have $\gcd(p, q) = ap + bq = 1$.

sage: p, q, a, b = prikey
sage: pubkey == p * q
True
sage: gcd(p, q) == a*p + b*q == 1
True

The class BlumGoldwasser makes use of various utility functions from the new module util. Here, we compute the ASCII integers of some binary strings:

sage: from sage.crypto.util import ascii_integer
sage: bin = BinaryStrings()
sage: B = bin.encoding("A"); B
01000001
sage: ascii_integer(B)
65
sage: B = bin.encoding("C"); list(B)
[0, 1, 0, 0, 0, 0, 1, 1]
sage: ascii_integer(list(B))
67
sage: ascii_integer("01000100")
68
sage: ascii_integer([0, 1, 0, 0, 0, 1, 0, 1])
69

Compute the binary representation of some ASCII strings:

sage: from sage.crypto.util import ascii_to_bin
sage: ascii_to_bin("A")
01000001
sage: ascii_to_bin("Abc123")
010000010110001001100011001100010011001000110011

Convert some ASCII strings to their binary representations and recover the ASCII strings from the binary representations:

sage: from sage.crypto.util import ascii_to_bin
sage: from sage.crypto.util import bin_to_ascii
sage: A = "Abc"
sage: B = ascii_to_bin(A); B
010000010110001001100011
sage: bin_to_ascii(B)
'Abc'
sage: bin_to_ascii(B) == A
True
sage: A = "123 \" #"
sage: B = ascii_to_bin(A); B
00110001001100100011001100100000001000100010000000100011
sage: bin_to_ascii(B)
'123 " #'
sage: bin_to_ascii(B) == A
True

Testing for the presence of Blum primes within some closed intervals. The interval $[4, 100]$ has a Blum prime, the smallest such prime being 7. The interval $[24, 28]$ has no primes, hence no Blum primes.

sage: from sage.crypto.util import has_blum_prime
sage: from sage.crypto.util import is_blum_prime
sage: has_blum_prime(4, 100)
True
sage: for n in xrange(4, 100):
...       if is_blum_prime(n):
...           print n
...           break
...
7
sage: has_blum_prime(24, 28)
False

Choose a random prime and check that it is a Blum prime:

sage: from sage.crypto.util import random_blum_prime
sage: p = random_blum_prime(10**4, 10**5)
sage: is_prime(p)
True
sage: mod(p, 4) == 3
True

Automatically generating a release note template

I have pushed further changes to the rnotes repository. Here is a high-level summary of the changes so far:

• The script is now called rnotes.py.
• The script now maintains a list of contributors up to and including Sage 4.3.2. After each release, this list should be updated to reflect new contributors.
• You can generate a template of a release note. You then fill in the details to obtain a complete release note. The generated template includes the standard information and headers, together with various lists of closed tickets in a milestone.
• There is an optional argument -o to output the generated template to a text file.

The usage pattern for the script is

python rnotes.py [-o] sage-x.y.z

To show what the script does, here’s a release note template for Sage 4.3.2:

Hi folks,

Sage 4.3.2 was released on <FIXME>. It is available at

Sage is developed by volunteers and combines over 90 open source packages.
source or binary form. If you have any questions and/or problems,
You can also drop by in #sage-devel on freenode.

The following 44 people contributed to this release. Of those, 3 made
their first contribution to Sage:

* Alex Ghitza
* Alex Leone
* Alexandre Blondin Massé
* Burcin Erocal
* Chris Wuthrich
* Christian Wuthrich [first contribution]
* Craig Citro
* Dan Drake
* David Joyner
* David Kirkby
* David Roe
* Florent Hivert
* Jaap Spies
* Jason Bandlow
* Jason Grout
* John Cremona
* John Palmieri
* Karl-Dieter Crisman
* Maite Aranes
* Marshall Hampton
* Martin Albrecht
* Michael Brickenstein
* Mike Hansen
* Minh Van Nguyen
* Mitesh Patel
* Nathann Cohen
* Nicolas M. Thiéry
* Nils Bruin
* Peter Jeremy
* Rishikesh
* Rob Beezer
* Robert Marik [first contribution]
* Robert Mařík
* Robert Miller
* Ross Kyprianou
* Sebastian Pancratz
* Sébastien Labbé
* Tim Dumol
* Tom Boothby
* Volker Braun
* Willem Jan Palenstijn
* Willem Palenstijn [first contribution]
* William Stein

* Release manager

* <FIXME>

* Major features, new spkg's, and bug fixes

* <FIXME>

* Bug statistics

We closed 126 tickets. For details see

http://trac.sagemath.org/sage_trac/milestone/sage-4.3.2

or check out the closed ticket section at the end of the announcement.

* Upcoming release

<FIXME>

* Doctesting coverage

For Sage <FIXME>, we had an overall weighted doctest coverage score of
<FIXME>, with <FIXME> functions. In Sage 4.3.2, we increased the doctest
coverage by <FIXME> and added <FIXME> new functions. Thus for Sage 4.3.2 we
now have

* Overall weighted coverage score:  <FIXME>
* Total number of functions:  <FIXME>

* Known issues

<FIXME>

Closed tickets:

#3043: The SPKG.txt  of the gfan spkg does not specify license exactly
#3338: gfan tarball is not clean upstream
#4339: modular forms -- incorporate Nils Skoruppa's code for computing generators for the ring of modular forms of given level
#4766: parallel? is lame and incomplete
#4959: r's install_packages is broken in many variants of sage
#5468: matrix creation over laurent polynomial rings
#5580: preparsing error in recursive load of .sage files
#5775: Building the documentation after -bdisting is broken
#5885: #5567 should throw a deprecation warning
#6279: spkg-check fails for the R spkg
#6427: Fix doctest failures in sage-4.1.alpha1
#6943: Make @parallel more robust [Reviewed by Tim Dumol]
#6987: reorganize section on producing patches with Mercurial
#7090: R test suite fails when building with SAGE_CHECK
#7833: Peter Jeremy: r-2.9.2 - fix compilation on FreeBSD [Reviewed by David Kirkby]
#7903: mixing a non-GNU Fortran compiler with GCC is not detected very early
#8024: Update prereq to check for Fortran compiler
#8047: Sage 4.3.1 has both lapack-20071123.p0.spkg and lapack-20071123.p1.spkg

Merged in sagenb:

#3083: Tim Dumol: Make shift-enter docstrings appear in printed / published worksheets [Reviewed by Mitesh Patel; merged in sagenb-0.7]
#3844: William Stein: notebook -- worksheet should call sys.path.append(DATA) when being initalized [Reviewed by Mitesh Patel; merged in sagenb-0.7]
#4217: Tim Dumol: notebook -- formatting of cells  beginning with "%hide %html" is not saved [Reviewed by Mitesh Patel; merged in sagenb-0.7]
#4450: Tim Dumol: notebook -- cursor down in last cell wraps around cell, instead of just staying at bottom [Reviewed by Alex Leone; merged in sagenb-0.7]
#5263: Tim Dumol: publishing a worksheet displays the URL without the hostname [Reviewed by Mitesh Patel; merged in sagenb-0.7]
#5675: Tim Dumol: Auto browser open of notebook does not open to a valid url when interface="" [Reviewed by Alex Leone; merged in sagenb-0.7]
#6182: Tim Dumol: Notebook -- Saving a worksheet with double quotes in the worksheet name fails with a weird error [Reviewed by Mitesh Patel; merged in sagenb-0.7]
#6353: Tim Dumol: change cookies structure to support multiple notebook logins at different ports [Reviewed by Mitesh Patel; merged in sagenb-0.7]
#6368: Alex Leone: shift-tab in the notebook should go back 4 spaces instead of going to the previous input cell [Reviewed by Mitesh Patel; merged in sagenb-0.7]
#6475: Tim Dumol: Notebook error page after deleting data file [Reviewed by Alex Leone; merged in sagenb-0.7]
#7207: Tim Dumol: from __future__ import <anything> results in a Syntax Error [Reviewed by Alex Leone; merged in sagenb-0.7]
#7249: Tim Dumol, Dan Drake: switch the notebook's templating system to Jinja2 [Reviewed by Mitesh Patel; merged in sagenb-0.7]
#7434: Alex Leone: notebook: new modal jquery dialog boxes are covered by jmol 3d graphics [Reviewed by Tim Dumol, Mitesh Patel; merged in sagenb-0.7]
#7435: Tim Dumol: notebook: help screen talks about DIR variable, which was removed from the notebook a while ago [Reviewed by Alex Leone; merged in sagenb-0.7]
#7631: Tim Dumol: notebook -- republishing a worksheet doesn't update the displayed title [Reviewed by Mitesh Patel; merged in sagenb-0.7]
#7752: Tim Dumol: RAM is not free after deleting a worksheet [Reviewed by Alex Leone; merged in sagenb-0.7]
#7784: Mitesh Patel: Add Makefile, update MANIFEST.in, .hgignore, and spkg-related files [Reviewed by Minh Van Nguyen; merged in sagenb-0.7.3]
#7848: Alex Leone: Fix misleading stuff about HTML cells on sagenb [Reviewed by Tim Dumol; merged in sagenb-0.7]
#7969: Tim Dumol, Willem Palenstijn: escaped backslash at end of line in notebook [Reviewed by Mitesh Patel; merged in sagenb-0.7]
#7996: Alex Leone: Invisible Text With Dark Theme (White on White Text) [Reviewed by Tim Dumol, Mitesh Patel; merged in sagenb-0.7]
#8000: Tim Dumol: Add # -*- coding: utf-8 -*- to the top of all SageNB .py files [Reviewed by Mitesh Patel; merged in sagenb-0.7]
#8102: Mitesh Patel: Simplify Sphinxify [Reviewed by John Palmieri; merged in sagenb-0.7.4]
#8103: Mitesh Patel: Published worksheets aren't inert [Reviewed by William Stein; merged in sagenb-0.7.1]
#8160: John Palmieri: add 'text' option to sphinxify [Reviewed by Mitesh Patel; merged in sagenb-0.7.4]
#8167: Mitesh Patel: Use LaTeX-friendly Unicode characters in SageNB docstrings [Reviewed by John Palmieri; merged in sagenb-0.7.4]

Merged in sage-4.3.2.alpha0:

#2084: Mike Hansen: default 20/40 in padics factory hard coded everywhere [Reviewed by David Roe]
#2480: Craig Citro: problem parsing arguments to NumberField.order() [Reviewed by Mike Hansen]
#2494: Mike Hansen: bugs in evaluation of spherical bessel function [Reviewed by Alex Ghitza]
#3436: Sebastian Pancratz: random_matrix() with prescribed density buggy [Reviewed by Tom Boothby, Craig Citro]
#3617: Mike Hansen: LarentPolynomial.__call__ is broken for Laurent polynomial's that have negative exponents [Reviewed by Sebastian Pancratz]
#4689: Jason Grout: save method for graphics objects does not have an example explicitly using "save" [Reviewed by Mike Hansen]
#5107: William Stein: incorrect trailing digits for continued fraction [Reviewed by Willem Jan Palenstijn]
#5295: Nils Bruin: Make Maxima not read global config files [Reviewed by Minh Van Nguyen]
#5477: Alex Ghitza: Make R.quotient_ring(I) normalize generator in the univariate case (easy to fix!) [Reviewed by Rishikesh]
#5501: Robert Bradshaw: pickling high-precision intervals is broken [Reviewed by Tim Dumol]
#5843: Willem Jan Palenstijn: race condition in cached_method (should not be shared between instances) [Reviewed by Tim Dumol]
#6207: William Stein: roots of polynomial have incorrect parent when ring=R is specified [Reviewed by Alex Ghitza]
#6428: Willem Jan Palenstijn: Large exponents overflow to negative in polydict ring [Reviewed by Sebastian Pancratz]
#6486: Sebastian Pancratz: minimum distance of all 0 code raised mysterious error message [Reviewed by Craig Citro]
#6532: Karl-Dieter Crisman, Jason Grout, Willem Jan Palenstijn: Make R build with recommended packages [Reviewed by Peter Jeremy, Minh Van Nguyen]
#6625: Willem Jan Palenstijn: manually removing executable bits doesn't work [Reviewed by Minh Van Nguyen]
#6863: Maite Aranes, John Cremona: Implement cusps over number fields [Reviewed by Craig Citro, John Cremona]
#6920: William Stein: irreducible components function is stupid in case of projective space [Reviewed by Alex Ghitza]
#7018: John Palmieri: Looking for trees with search_doc("tree") is a bad idea [Reviewed by Dan Drake]
#7109: Volker Braun, Marshall Hampton, Alex Ghitza: polyhedra bugs with linearities, rewrite proposal [Reviewed by Volker Braun, Marshall Hampton, Alex Ghitza]
#7262: Craig Citro: Have multiplication_by_m() return an EllipticCurveIsogeny object [Reviewed by John Cremona, Chris Wuthrich]
#7299: Jason Grout: show() regression: Picture cropped too much [Reviewed by Robert Bradshaw]
#7389: Willem Jan Palenstijn: Fallback _point_morphism_class() has wrong signature [Reviewed by Alex Ghitza]
#7521: Karl-Dieter Crisman: typo in optional doctest for R interface [Reviewed by Minh Van Nguyen]
#7532: John Cremona: "return NotImplementedError" in ring.pyx [Reviewed by Tim Dumol, John Palmieri]
#7535: Tim Dumol: Errors should be raised, not returned. [Reviewed by John Palmieri]
#7719: John Cremona, Robert Bradshaw: Improvements to complex AGM [Reviewed by Robert Bradshaw, John Cremona]
#7802: Jason Grout: Mention that RNDN is the "ties toward even" version in RealField [Reviewed by Minh Van Nguyen]
#7820: Alex Ghitza, David Kirkby: upgrade gfan to latest release (0.4plus) [Reviewed by Marshall Hampton]
#7823: Peter Jeremy: libgcrypt-1.4.4.p1 references incorrect shared library on FreeBSD [Reviewed by David Kirkby]
#7824: Peter Jeremy: cliquer-1.2.p2 - add FreeBSD support [Reviewed by David Kirkby]
#7830: Jason Grout: function for floating point representation of a number [Reviewed by Robert Bradshaw, John Cremona]
#7921: Nicolas M. Thiéry: Categories for extension types via __getattr___ [Reviewed by Robert Bradshaw]
#7938: Jason Bandlow: 'term' and 'monomial' are inconsistently used in some Category and combinat code [Reviewed by Nicolas M. Thiéry]
#7939: Martin Albrecht: shorten doctests in sage/rings/polynomial/multi_polynomial_ideal.py [Reviewed by Michael Brickenstein, Alex Ghitza]
#7949: Sebastian Pancratz: Bit-shifts in Z/(n) [Reviewed by Tom Boothby]
#7950: Burcin Erocal: factoring broken in 0 variable polynomial ring [Reviewed by William Stein, Alex Ghitza]
#7951: Burcin Erocal: coercion problem with 0 variable polynomials [Reviewed by Robert Bradshaw, Alex Ghitza]
#7958: Sebastian Pancratz, Mike Hansen: Conversion of rationals into the fraction field of integer polynomials [Reviewed by Mike Hansen, Sebastian Pancratz]
#7976: Florent Hivert: Extends __classcall__ to control inheritance [Reviewed by Nicolas M. Thiéry]
#7995: Willem Jan Palenstijn: sage-test doesn't handle all of sage-doctest's return values [Reviewed by Alex Ghitza]
#8001: Nicolas M. Thiéry: Stronger category tests [Reviewed by Florent Hivert]
#8002: Willem Jan Palenstijn: remove dead code from sage-ptest [Reviewed by Rob Beezer]
#8003: Christian Wuthrich: EllipticCurve('522j1').sha().an_padic(13) fails [Reviewed by Robert Miller]
#8009: Jason Grout: plot_vector_field does not take a color option [Reviewed by Robert Bradshaw]
#8012: Robert Bradshaw: spurious argument in RIF documentation [Reviewed by Tim Dumol]
#8020: William Stein: python-2.6.4.p4 spkg *totally breaks* itanium support [Reviewed by Craig Citro]
#8021: John Palmieri: ref manual for 4.3.1: error when building (Undefined control sequence \cross) [Reviewed by Minh Van Nguyen]
#8028: Nicolas M. Thiéry: Improvements to element_wrapper [Reviewed by Florent Hivert]
#8032: Willem Jan Palenstijn: block matrix doctest [Reviewed by Robert Bradshaw]
#8041: William Stein, John Palmieri: docstring for XGCD has Sphinx errors "Unknown control sequence '\*'" in sage-4.3.1 [Reviewed by John Palmieri, Alex Ghitza]
#8042: Craig Citro: problem with modular symbols in eclib [Reviewed by Chris Wuthrich]

Merged in sage-4.3.2.alpha1:

#5524: Nicolas M. Thiéry: Fix missing equality test in attrcall [Reviewed by Jason Bandlow]
#6989: Jason Grout: line3d can modify its argument type [Reviewed by Karl-Dieter Crisman]
#7325: Robert Marik: Sage cannot solve inequalities [Reviewed by Karl-Dieter Crisman]
#7502: Robert Bradshaw: lazy import module [Reviewed by Mitesh Patel]
#7617: Dan Drake: include sagetex as a standard spkg [Reviewed by William Stein, Mike Hansen, John Palmieri]
#7827: Peter Jeremy: Fix atlas-3.8.3.p9 compilation on FreeBSD [Reviewed by David Kirkby, Minh Van Nguyen]
#7878: David Kirkby: remove any spaces in output of testcc.sh and testcxx.sh [Reviewed by Jaap Spies]
#8052: David Kirkby: Update prereq to version 0.7 (mostly Fortran issues fixed) [Reviewed by Minh Van Nguyen]
#8057: Jaap Spies: New boehm-gc-7.1.p3.spkg works with Open Solaris x64 as 64-bit [Reviewed by David Kirkby]
#8081: Nathann Cohen: documentation bug on new gale_ryser_theorem() [Reviewed by David Joyner]
#8083: Robert Mařík: fix accents in LaTeX output [Reviewed by John Palmieri]
#8084: John Palmieri: fix "show" in the notebook for strings [Reviewed by Robert Mařík]
#8095: Sébastien Labbé: is_primitive of WordMorphism is broken [Reviewed by Alexandre Blondin Massé]
#8107: Mitesh Patel: Fewer unnecessary imports from sage.server.* [Reviewed by Robert Bradshaw]
#8110: Alex Ghitza: fix issue with multi_polynomial.pyx in sage-4.3.2.alpha0 [Reviewed by Martin Albrecht]
#8114: Craig Citro, William Stein: doctest failure in sage/libs/cremona/newforms.pyx on 32-bit machines from #8042 [Reviewed by William Stein, Craig Citro]
#8126: Robert Mařík: fix typo in doc of circle [Reviewed by John Palmieri]

Merged in sage-4.3.2.final:

#8200: Florent Hivert, Nicolas M. Thiéry: ElementWrapper: doctests improvements to not abuse ZZ invariants [Reviewed by William Stein]

Merged in sage-4.3.2.rc0:

#7933: Minh Van Nguyen: update copyright years to span 2005--2010 [Reviewed by Mitesh Patel]
#8022: John Palmieri: ref manual for 4.3.1: fix warning about misc/attach.rst [Reviewed by Mitesh Patel]
#8036: Mitesh Patel: Sage 4.3.1 reference manual: PDF version failed to build due to non-ASCII characters in docstring [Reviewed by John Palmieri]
#8045: John Palmieri: add elliptic integrals to the reference manual [Reviewed by Mitesh Patel]
#8108: Rob Beezer, Minh Van Nguyen: Expand the Sage Developer Guide for newcomers [Reviewed by Ross Kyprianou, John Palmieri]
#8132: Robert Mařík: fix documentation related to ODE solvers [Reviewed by David Joyner]
#8136: John Palmieri: fix ref manual issues in linear_code.py [Reviewed by David Joyner]
#8144: John Palmieri: SageTeX is not actually installed under SAGE_LOCAL [Reviewed by Dan Drake]
#8146: John Palmieri: building HTML version of French tutorial is broken [Reviewed by Mitesh Patel]
#8147: Rob Beezer: Add mercurial queues information to Developer Walkthrough [Reviewed by Minh Van Nguyen, Rob Beezer]
#8179: Volker Braun: configure Mercurial to ignore two binaries by cddlib [Reviewed by Minh Van Nguyen]

With this template, you then double check the list of contributors and fill in other relevant details. You can pass the optional argument -o so the script would output the resulting template to a text file. For instance, the command

python rnotes.py -o sage-4.3.2

would write the generated template to a text file named sage-4.3.2.txt.

Release management: Merging patches

This is a revision of my post to the sage-release mailing list, outlining some guidelines for merging positively reviewed tickets. I want to post it here so that it won’t be lost in the archive of the sage-release mailing list.

There is as yet little to no guidelines for Sage release management. The release management wiki page has been around for months, but it’s not especially helpful for anyone who wants hands-on experience. Here, I’ll try to list some guidelines for merging tickets/spkg’s and managing positively reviewed tickets. The primary focus is on merging tickets with patches.

Before starting on merging tickets for a new milestone, I would compile the source tarball of the current stable release of Sage under a fast-ish directory such as /scratch/. In my case, it’s under my /scratch/ home directory /scratch/mvngu/release/ on the machine sage.math. The idea is to avoid working under a directory that resides on an NFS mounted disk. Towards that end, I also set my default DOT_SAGE directory to a fast-ish directory, as implemented via the following export line in my .bashrc:

# The Sage working directory .sage/
export DOT_SAGE=/dev/shm/mvngu/dot_sage

It also helps to know whether or not there’s any doctest failure on sage.math with the newly compiled source tarball.

After compiling and (parallel) doctesting the latest version of Sage, it’s time to merge tickets that have received positive review. I often use trac report 11 to find out which tickets have been positively reviewed. Using report 11, I would then pick a ticket, read through it for any special instructions. In many cases, the ticket has instructions for which patch to merge and, for more than one patch on the ticket, in which order. In some cases, it can be difficult to work out the order in which to merge patches on a ticket. With a situation like this, I would request the patch author(s) to explain how to merge patches on the ticket and in which order.

Sage has a merge script in the scripts repository. This script is designed for merging tickets. The merge script is SAGE_LOCAL/bin/sage-apply-ticket, which can be used from the command line interface via

./sage -merge <ticket-number>

However, to effectively use that script, one first needs a working knowledge of Mercurial and its queues extension. This is especially important because the merge script uses Mercurial queues (mq). There would be times when the merge script cannot help me with debugging ticket conflicts, so I would need to use mq together with the bisect command to search through the commit history. I don’t often use the merge script, so there is little for me to say about how to effectively use it.

Here, I’ll explain one way to merge a positively reviewed ticket using mq. Ensure that any patches to be merged must have the full name and email address of the patch author. The commit message must contain the ticket number. Use mq to qimport and qpush any relevant patches to be merged. Sometimes a patch author would forget to put in their full name and email address on the patch, so I need to manually download the patch and fill in those details. Another way is to set the username field in my .hgrc to the patch author’s full name and email address; then qimport and qpush. After that, I would restore my full name and email address in my .hgrc. If a commit message doesn’t contain the ticket number, or the message is something non-sensical like

[mq]: real-numbers-work.patch

I would use qrefresh -e to replace that with a sensible commit message that also has the ticket number. Now the patches must pass the following criteria:

1. No hunk failures resulting from qpush.
2. The Sage library must rebuild without errors.
3. The HTML and PDF versions of the reference manual must build successfully.
4. No doctest failures when (parallel) doctesting everything under
SAGE_ROOT/devel/sage-main/.

If any of the above steps results in an error, then it’s very likely that the ticket would receive an automatic “needs work” status. Be sure to explain on the ticket why the patch(es) need work. Is it a rebase? If so, which version of Sage to perform the rebase on. Does the ticket conflict with another ticket? And so on.

If all of the above steps pass for the ticket, then move on to another ticket for merging. Be careful not to close the ticket even though the above criteria are met. What I would do is, merge a dozen or so tickets as per the above instructions, but not closing the corresponding tickets after qimport and qpush their patches. Once I have a qseries with patches from a dozen tickets, which should still be open by now, I would copy everything under SAGE_ROOT to another directory, say, under /dev/shm/. (I would also note down the order in which those dozen tickets have been merged.) From that newly copied SAGE_ROOT, I would create a source tarball to test that everything still builds after merging the dozen tickets. To do so, I would do:

1. cd to the SAGE_ROOT under /dev/shm/.
2. Run ./sage.
3. Run ./sage -b main. This step would take a while, so I would do something during the rebuild process that would occupy me for at least 15 minutes.
4. Create a tentative source tarball with
./sage -sdist x.y.z-<descriptive-name>

The name <descriptive-name> is something to remind myself that this source tarball is only to test that the resulting tarball still builds and all doctests still pass.

5. The result is a source tarball under dist/.
6. Untar that source tarball, compile Sage, and parallel doctest. This step usually takes more than 1 hour, so I would make sure to have something to occupy me for at least an hour.

To be safe, I often copy the whole SAGE_ROOT of my merge tree to another directory and run through the above steps. This is because a ticket can have an spkg for merging into the standard spkg repository. You could push a sage-main repository to another copy of Sage somewhere, but presently you can’t do the same thing for the standard spkg repository.

Once the tentative source tarball successfully compiles and all doctests under SAGE_ROOT/devel/sage-main/ pass, then I would close the relevant dozen or so tickets.

The above is a general overview of the process I follow for merging/closing tickets. It’s a slow process, I admit. But I would rather try to catch build and doctest problems early, than have them bit me later on down the track. As noted at the beginning of this post, I didn’t cover anything about merging updated spkg’s in the standard packages repository. That could be a topic for another post.

Sage humour: Patch management

An email on sage-devel asks about how to use Mercurial for managing patches. I replied that tickets #8108 and #8147 have some introductory materials on that topic. However, I didn’t pick up the irony in my reply, hence the following insightful remark:

> See tickets #8108 and #8147 for introductory materials on patch
> management with Mercurial:
> http://trac.sagemath.org/sage_trac/ticket/8108
> http://trac.sagemath.org/sage_trac/ticket/8147