# 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`:
```bash
python -m discretelog 25 641629670911834423534 1540571422742786915303
```
### Installation
The library is available in `pypi`, therefore can be installed with:
```bash
python -m pip install discretelog
```
### Building from source
Using `poetry` to generate a wheel file:
```bash
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
Raw data
{
"_id": null,
"home_page": "https://github.com/gilcu3/discretelog",
"name": "discretelog",
"maintainer": null,
"docs_url": null,
"requires_python": "<4.0,>=3.10",
"maintainer_email": null,
"keywords": "discrete logarithm, number theory, cryptography",
"author": "gilcu3",
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/ab/2a/fde1c635c2e00a812940401c6e8d6a8929396da0ebe05599278c5be54728/discretelog-0.1.1.tar.gz",
"platform": null,
"description": "# discretelog\n\nA pure python package to compute discrete logs in the ring of integers\nmodulo n. It aims to provide relatively performant code with simple\nimplementations of well-known algorithms, inspired by the popular `primefac`\nlibrary.\n\n## Usage\nTo find the discrete log of `v=641629670911834423534` modulo\n`n=1540571422742786915303` with base `g=25`:\n```bash\npython -m discretelog 25 641629670911834423534 1540571422742786915303\n```\n\n### Installation\nThe library is available in `pypi`, therefore can be installed with:\n```bash\npython -m pip install discretelog\n```\n\n### Building from source\nUsing `poetry` to generate a wheel file:\n```bash\ngit clone https://github.com/gilcu3/discretelog\ncd discretelog\npoetry build\n```\n\n\n## Status\n\nThis is a work in progress. Several issues will be worked on in the future:\n\n- Looking at a similar library within `Pari/GP`, probably better performance\ncan be achieved\n- Several parts can be trivially made parallel\n- For the moment documentation is missing\n- The library should either fail gracefully or continue computing indefinitly\nin case of big inputs. At the moment it simply crashes\n\n### Discrete log algorithms implemented\n\n- Baby steps giant steps\n- Pollard rho\n- Pohlig Hellman\n- Naive index calculus\n- Linear sieve index calculus\n\n## External tools\n\nFor large inputs the library uses external `c++` implementations of state\nof the art algorithms. In order to use them the user needs to install\nthem separately. See `docs/external.md` for details\n",
"bugtrack_url": null,
"license": "Apache Software License 2.0",
"summary": "Discrete logarithms in the ring of integers modulo n",
"version": "0.1.1",
"project_urls": {
"Homepage": "https://github.com/gilcu3/discretelog",
"Repository": "https://github.com/gilcu3/discretelog"
},
"split_keywords": [
"discrete logarithm",
" number theory",
" cryptography"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "5c805312c8e09aa1a07791fd950ae779e774c2a4dddcdf8eff3f8a74714c2074",
"md5": "acfa80807c9ce8db1ebcbd3ad587e785",
"sha256": "bd1db4a4833f659c2bea749e3f7dcbb07288886bf906c0762b6e82dae9d8f585"
},
"downloads": -1,
"filename": "discretelog-0.1.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "acfa80807c9ce8db1ebcbd3ad587e785",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": "<4.0,>=3.10",
"size": 18845,
"upload_time": "2024-05-11T15:03:38",
"upload_time_iso_8601": "2024-05-11T15:03:38.959361Z",
"url": "https://files.pythonhosted.org/packages/5c/80/5312c8e09aa1a07791fd950ae779e774c2a4dddcdf8eff3f8a74714c2074/discretelog-0.1.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "ab2afde1c635c2e00a812940401c6e8d6a8929396da0ebe05599278c5be54728",
"md5": "91cc8b93f2beb0ae5a163735176fee08",
"sha256": "5604bb650b4bb39b10d351ac2c16c2e68371a327d9a624e3ddb543af99aaf249"
},
"downloads": -1,
"filename": "discretelog-0.1.1.tar.gz",
"has_sig": false,
"md5_digest": "91cc8b93f2beb0ae5a163735176fee08",
"packagetype": "sdist",
"python_version": "source",
"requires_python": "<4.0,>=3.10",
"size": 17233,
"upload_time": "2024-05-11T15:03:40",
"upload_time_iso_8601": "2024-05-11T15:03:40.522759Z",
"url": "https://files.pythonhosted.org/packages/ab/2a/fde1c635c2e00a812940401c6e8d6a8929396da0ebe05599278c5be54728/discretelog-0.1.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-05-11 15:03:40",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "gilcu3",
"github_project": "discretelog",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "discretelog"
}
JSON
