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
1 maintainer
Metadata
1 maintainer
Release files for discretelog 0.1.1
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | |
|---|---|---|---|
| discretelog-0.1.1.tar.gz | 17.2 kB | Details |
Built distribution (wheel)
| File | Interpreter | ABI | Platform | Reset |
|---|---|---|---|---|
| discretelog-0.1.1-py3-none-any.whl | Python 3 | none | any | Details |
Total release size: 36.1 kB
Release files / discretelog-0.1.1.tar.gz
| Download URL | discretelog-0.1.1.tar.gz |
|---|---|
| Size | 17.2 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
5604bb650b4bb39b10d351ac2c16c2e68371a327d9a624e3ddb543af99aaf249
|
|
BLAKE2b-256 checksum How to use checksums |
ab2afde1c635c2e00a812940401c6e8d6a8929396da0ebe05599278c5be54728
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/1.8.2 CPython/3.12.3 Linux/6.8.7-arch1-2
|
Release files / discretelog-0.1.1-py3-none-any.whl
| Download URL | discretelog-0.1.1-py3-none-any.whl |
|---|---|
| Size | 18.8 kB |
| Tags | Python 3 |
|
SHA-256 checksum How to use checksums |
bd1db4a4833f659c2bea749e3f7dcbb07288886bf906c0762b6e82dae9d8f585
|
|
BLAKE2b-256 checksum How to use checksums |
5c805312c8e09aa1a07791fd950ae779e774c2a4dddcdf8eff3f8a74714c2074
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
poetry/1.8.2 CPython/3.12.3 Linux/6.8.7-arch1-2
|
