A Python wrapper for fplll.
>>> from fpylll import *
>>> A = IntegerMatrix(50, 50)
>>> A.randomize("ntrulike", bits=50, q=127)
>>> A[0].norm()
3564748886669202.5
>>> M = GSO.Mat(A)
>>> M.update_gso()
>>> M.get_mu(1,0)
0.815748944429783
>>> L = LLL.Reduction(M)
>>> L()
>>> M.get_mu(1,0)
0.41812865497076024
>>> A[0].norm()
24.06241883103193
The basic BKZ algorithm can be implemented in about 60 pretty readable lines of Python code (cf. simple_bkz.py). For a quick tour of the library, you can check out the tutorial.
fpylll relies on the following C/C++ libraries:
- GMP or MPIR for arbitrary precision integer arithmetic.
- MPFR for arbitrary precision floating point arithmetic.
- QD for double double and quad double arithmetic (optional).
- fplll for pretty much everything.
fpylll also relies on
- Cython for linking Python and C/C++.
- cysignals for signal handling such as interrupting C++ code.
- py.test for testing Python.
- flake8 for linting.
We also suggest
- virtualenv to build and install fpylll in
- IPython for interacting with Python
- Numpy for numerical computations (e.g. with Gram-Schmidt values)
fpylll ships with Sage. Thus, it is available via SageMathCell and CoCalc (select a Jupyter notebook with a Sage kernel). You can also fire up a dply.co virtual server with the latest fpylll/fplll preinstalled (it takes perhaps 15 minutes until everything is compiled).
Note: fpylll is also available via PyPI and Conda-Forge for Conda. In what follows, we explain manual installation.
We recommend virtualenv for isolating Python build environments and virtualenvwrapper to manage virtual environments.
We indicate active virtualenvs by the prefix (fpylll)
.
Automatic install
Run bootstrap.sh
$ ./bootstrap.sh $ source ./activate
Manual install
Create a new virtualenv and activate it:
$ virtualenv env $ ln -s ./env/bin/activate ./ $ source ./activate
Install the required libraries - GMP or MPIR and MPFR - if not available already. You may also want to install QD.
Install fplll:
$ (fpylll) ./install-dependencies.sh $VIRTUAL_ENV
Some OSX users report that they required
export CXXFLAGS="-stdlib=libc++ -mmacosx-version-min=10.7"
andexport CXX=clang++
(after installing a recent clang with brew) since the default GCC installed by Apple does not have full C++11 support.Then, execute:
$ (fpylll) pip install Cython $ (fpylll) pip install -r requirements.txt
to install the required Python packages (see above).
If you are so inclined, run:
$ (fpylll) pip install -r suggestions.txt
to install suggested Python packages as well (optional).
Build the Python extension:
$ (fpylll) export PKG_CONFIG_PATH="$VIRTUAL_ENV/lib/pkgconfig:$PKG_CONFIG_PATH" $ (fpylll) python setup.py build_ext $ (fpylll) python setup.py install
To run fpylll, you will need to:
$ (fpylll) export LD_LIBRARY_PATH="$VIRTUAL_ENV/lib"
so that Python can find fplll and friends.
Note that you can also patch
activate
to setLD_LIBRRY_PATH
. For this, add:### LD_LIBRARY_HACK _OLD_LD_LIBRARY_PATH="$LD_LIBRARY_PATH" LD_LIBRARY_PATH="$VIRTUAL_ENV/lib:$LD_LIBRARY_PATH" export LD_LIBRARY_PATH ### END_LD_LIBRARY_HACK ### PKG_CONFIG_HACK _OLD_PKG_CONFIG_PATH="$PKG_CONFIG_PATH" PKG_CONFIG_PATH="$VIRTUAL_ENV/lib/pkgconfig:$PKG_CONFIG_PATH" export PKG_CONFIG_PATH ### END_PKG_CONFIG_HACK
towards the end and:
### LD_LIBRARY_HACK if ! [ -z ${_OLD_LD_LIBRARY_PATH+x} ] ; then LD_LIBRARY_PATH="$_OLD_LD_LIBRARY_PATH" export LD_LIBRARY_PATH unset _OLD_LD_LIBRARY_PATH fi ### END_LD_LIBRARY_HACK ### PKG_CONFIG_HACK if ! [ -z ${_OLD_PKG_CONFIG_PATH+x} ] ; then PKG_CONFIG_PATH="$_OLD_PKG_CONFIG_PATH" export PKG_CONFIG_PATH unset _OLD_PKG_CONFIG_PATH fi ### END_PKG_CONFIG_HACK
in the
deactivate
function in theactivate
script.
Running fpylll
To (re)activate the virtual environment, simply run:
$ source ./activate
Start Python:
$ (fpylll) ipython
Manual update of fpylll and fplll inside Sagemath 9.0+
The instructions are very similar to the manual ones above.
Activate the sage-sh virtualenv:
$ sage -sh
Install the required libraries - GMP or MPIR and MPFR - if not available already. You may also want to install QD.
Install fplll:
$ (sage-sh) ./install-dependencies.sh $SAGE_LOCAL
Some OSX users report that they required
export CXXFLAGS="-stdlib=libc++ -mmacosx-version-min=10.7"
andexport CXX=clang++
(after installing a recent clang with brew) since the default GCC installed by Apple does not have full C++11 support.Then, execute:
$ (sage-sh) pip3 install Cython $ (sage-sh) pip3 install -r requirements.txt
to install the required Python packages (see above).
If you are so inclined, run:
$ (sage-sh) pip3 install -r suggestions.txt
to install suggested Python packages as well (optional).
Build the Python extension:
$ (sage-sh) export PKG_CONFIG_PATH="$SAGE_LOCAL/lib/pkgconfig:$PKG_CONFIG_PATH" $ (sage-sh) python3 setup.py build_ext $ (sage-sh) python3 setup.py install $ (sage-sh) exit
Verify the upgrade went well:
$ sage sage: import fpylll sage: print(fpylll.__version__)
The output should match the value of __version__ in src/fpylll/__init__.py.
fpylll supports parallelisation on multiple cores. For all C++ support to drop the GIL is enabled, allowing the use of threads to parallelise. Fplll is thread safe as long as each thread works on a separate object such as IntegerMatrix
or MatGSO
. Also, fpylll does not actually drop the GIL in all calls to C++ functions yet. In many scenarios using multiprocessing, which sidesteps the GIL and thread safety issues by using processes instead of threads, will be the better choice.
The example below calls LLL.reduction
on 128 matrices of dimension 30 on four worker processes.
from fpylll import IntegerMatrix, LLL
from multiprocessing import Pool
d, workers, tasks = 30, 4, 128
def run_it(p, f, A, prefix=""):
"""Print status during parallel execution."""
import sys
r = []
for i, retval in enumerate(p.imap_unordered(f, A, 1)):
r.append(retval)
sys.stderr.write('\r{0} done: {1:.2%}'.format(prefix, float(i)/len(A)))
sys.stderr.flush()
sys.stderr.write('\r{0} done {1:.2%}\n'.format(prefix, float(i+1)/len(A)))
return r
A = [IntegerMatrix.random(d, "uniform", bits=30) for _ in range(tasks)]
A = run_it(Pool(workers), LLL.reduction, A)
To test threading simply replace the line from multiprocessing import Pool
with from multiprocessing.pool import ThreadPool as Pool
. For calling BKZ.reduction
this way, which expects a second parameter with options, using functools.partial is a good choice.
fpylll welcomes contributions, cf. the list of open issues. To contribute, clone this repository, commit your code on a separate branch and send a pull request. Please write tests for your code. You can run them by calling:
$ (fpylll) PY_IGNORE_IMPORTMISMATCH=1 py.test
from the top-level directory which runs all tests in tests/test_*.py
. We run flake8 on every commit automatically, In particular, we run:
$ (fpylll) flake8 --max-line-length=120 --max-complexity=16 --ignore=E22,E241 src
Note that fpylll supports Python 2 and 3. In particular, tests are run using Python 2.7 and 3.5. See .travis.yml for details on automated testing.
fpylll is maintained by Martin Albrecht.
The following people have contributed to fpylll
- Eamonn Postlethwaite
- E M Bray
- Fernando Virdia
- Guillaume Bonnoron
- Jeroen Demeyer
- Jérôme Benoit
- Konstantinos Draziotis
- Leo Ducas
- Martin Albrecht
- Michael Walter
- Omer Katz
We copied a decent bit of code over from Sage, mostly from it's fpLLL interface.
fpylll is licensed under the GPLv2+.