PolyBoRi is dead, it needs your help

On the Sage development list a discussion is going on what to do about PolyBoRi. For those who do not know PolyBoRi, for computing Gröbner bases for Boolean polynomials it is pretty much the only (open-source) game in town (as far as I know):

The core of PolyBoRi is a C++ library, which provides high-level data types for Boolean polynomials and monomials, exponent vectors, as well as for the underlying polynomial rings and subsets of the powerset of the Boolean variables. As a unique approach, binary decision diagrams are used as internal storage type for polynomial structures.

On top of this C++-library we provide a Python interface. This allows parsing of complex polynomial systems, as well as sophisticated and extendable strategies for Gröbner base computation. PolyBoRi features a powerful reference implementation for Gröbner basis computation.

Boolean polynomials show up a lot in cryptography and other areas of computer science.

The trouble with PolyBoRi is that both authors of PolyBoRi – Alexander Dreyer and Michael Brickenstein – left academia and have jobs now which have nothing to do with PolyBoRi. Hence, PolyBoRi is currently not maintained. This is a big problem. In particular, there are some issues with PolyBoRi which cannot be ignored forever:

  • PolyBoRi uses Python (yay) but only Python 2. At some point the world – i.e. Sage – will switch to Python 3 and PolyBoRi is the only obstacle to that switch except for the Sage Python library itself.
  • PolyBoRi uses Scons as a build system. Everybody would be a lot happier if it was switched to using autotools (which are a lot more awesome than many people realise).

In the long-term the Singular team might get involved and keep PolyBoRi alive, but this is not certain. Also, there is a push for a decision about what to do with PolyBoRi in Sage now.

The current proposal on the table is to drop PolyBoRi from the default Sage installation, i.e. to demote it to an optional package. In my mind, this would be very bad as Sage and PolyBoRi benefit from the tight integration that currently exists. Also, in my experience, optional packages tend to simply not work that well as they are not tested in each release.

Hence, if you care about PolyBoRi you should consider to

  1. let us know in the relevant thread on the mailing list if you use PolyBoRi in Sage.
  2. volunteer to help to autotool-ify PolyBoRi if you speak autotools. (If you don’t speak autotools, you should learn, they are awesome.)
  3. volunteer to help to port PolyBoRi from Python 2 to Python 3.

I’m up for getting involved, but I don’t want to take on the responsibility alone.

Update (2015-06-13): A fair share of work has already been done by Andrew. Still, anyone up for helping out?

Sage Code for GGH Cryptanalysis by Hu and Jia

Recently, Yupu Hu and Huiwen Jia put a paper on the Cryptology ePrint Archive which describes a successful attack of the GGH (and GGHLite) candidate multilinear map. The attack does not try to recover the secret g or any other secret parameter of the map. Instead, it solves the Extraction \kappa-graded CDH (Ext-GCDH) problem directly.

Continue reading “Sage Code for GGH Cryptanalysis by Hu and Jia”

Google Summer of Code 2015

Both Sage and the Lmonade project were selected for Google’s Summer of Code 2015. If you are an eligible student, you should consider applying. If you need ideas what to work on, there are many fine projects/project ideas on either the Lmonade or the Sage GSoC pages. In particular, here are the fplll project ideas, for which I could be one of the two mentors.

Continue reading “Google Summer of Code 2015”

Sage Development with Emacs

A while back I described my (then current) setup to develop C code with Emacs. The other programming language I tend to spend a lot of time with is Python, specifically Sage’s Python. Here’s my Emacs setup for writing Sage code. For starters, it makes sense to highlight indentation in Python.

(use-package highlight-indentation
   :ensure t)

I use anaconda-mode for auto-completion and stuff, it runs jedi for me. In particular it offers:

  • M-. Goto definition for thing at point.
  • M-, Switch to buffer of most recent marker.
  • M-? Show documentation for context at point.
  • M-r Show usage for thing at point.
(use-package anaconda-mode
  :ensure t
  :diminish anaconda-mode
  :config (bind-key "M-," #'anaconda-nav-pop-marker anaconda-mode-map))

Continue reading “Sage Development with Emacs”

Looking Back and Forward for Open-Source Mathematics Software (2014)

When a year ends people make lists. I can only guess that several people are currently busy with writing “The 5 most revised papers on eprint ” and “The 8 best IACR flagship conference rump session presentations of 2014”. Since all the good lists are taken, my list has to be a little bit more personal. Alas, here is my list of stuff that happened in open-source computational mathematics in 2014 around me. That is, below I list what developments happened in 2014 and try to provide an outlook for 2015 (so that I can come back in a year to notice that nothing played out as planned).

If you are interested in any of the projects below feel invited to get involved. Also, if you are student and you are interested in working on one of the (bigger) projects listed below over the summer, get in touch: we could try to turn it into a Google Summer of Code 2015 project.

Continue reading “Looking Back and Forward for Open-Source Mathematics Software (2014)”