Discrete logarithms in the ring of integers modulo n
Project description
discretelog
A pure python package to compute discrete logs in the ring of integers
modulo n. It aims to provide relatively performant code with simple
implementations of well-known algorithms, inspired by the popular primefac
library.
Usage
To find the discrete log of v=641629670911834423534
modulo
n=1540571422742786915303
with base g=25
:
python -m discretelog 25 641629670911834423534 1540571422742786915303
Installation
The library is available in pypi
, therefore can be installed with:
python -m pip install discretelog
Building from source
Using poetry
to generate a wheel file:
git clone https://github.com/gilcu3/discretelog
cd discretelog
poetry build
Status
This is a work in progress. Several issues will be worked on in the future:
- Looking at a similar library within
Pari/GP
, probably better performance can be achieved - Several parts can be trivially made parallel
- For the moment documentation is missing
- The library should either fail gracefully or continue computing indefinitly in case of big inputs. At the moment it simply crashes
Discrete log algorithms implemented
- Baby steps giant steps
- Pollard rho
- Pohlig Hellman
- Naive index calculus
- Linear sieve index calculus
External tools
For large inputs the library uses external c++
implementations of state
of the art algorithms. In order to use them the user needs to install
them separately. See docs/external.md
for details
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for discretelog-0.1.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bd1db4a4833f659c2bea749e3f7dcbb07288886bf906c0762b6e82dae9d8f585 |
|
MD5 | acfa80807c9ce8db1ebcbd3ad587e785 |
|
BLAKE2b-256 | 5c805312c8e09aa1a07791fd950ae779e774c2a4dddcdf8eff3f8a74714c2074 |