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
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.0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 877c9b4c930e6f19ac4788d25d825b521b48d70bfb1258c1993f42d61bfac77f |
|
MD5 | d9e265e6a92494e9b7ef9d2fe7ae6fd2 |
|
BLAKE2b-256 | 15edb050c554b65cf2515df14d14f116c6d7f184af16787535e99616968b555d |