An algorithm that computes modular nested exponentiation efficiently
Project description
modular-nested-exponentiation
An algorithm that computes modular nested exponentiation efficiently.
| License |  |
Version |  |
| Wheel |  |
Implementation |  |
| Status |  |
Supported versions |  |
Generalised modular exponentiation
We present an algorithm that takes as input an arbitrarily long sequence of positive integers a₁, a₂, a₃, ..., aₙ and a positive integer m and computes a₁^(a₂^(···^aₙ)) mod m efficiently (that is, without computing the value of the nested exponent).
Without this algorithm, this type of computation is unfeasible for modern computers even for short input sequences containing small integers.
Prerequisites
$ apt install libgmp-dev libmpfr-dev libmpc-dev
$ pip install sympy gmpy2
Install
$ pip install mod-nest-exp
Usage
$ python
>>> from mod_nest_exp import mod_nest_exp
>>> mod_nest_exp([6, 5, 4, 3, 2], 1948502738)
mpz(951546056) # uses gmpy2 if available
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
mod-nest-exp-1.0.3.tar.gz
(5.2 kB
view details)
Built Distribution
File details
Details for the file mod-nest-exp-1.0.3.tar.gz.
File metadata
- Download URL: mod-nest-exp-1.0.3.tar.gz
- Upload date:
- Size: 5.2 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.4.1 importlib_metadata/3.7.3 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.51.0 CPython/3.9.1+
File hashes
| Algorithm | Hash digest | |
|---|---|---|
| SHA256 | c95403e045a0f02a7cb6d5fc9e904f31daeb1304ee2b38263fd9f6ee865b62bf |
|
| MD5 | 29d1a41d67946915211d770d84c41ab6 |
|
| BLAKE2b-256 | 3d0b9c99b6b0f7fc441df9db4fba9a2ae183df6dd9c821da8d7478c721ae2c12 |
File details
Details for the file mod_nest_exp-1.0.3-py3-none-any.whl.
File metadata
- Download URL: mod_nest_exp-1.0.3-py3-none-any.whl
- Upload date:
- Size: 17.8 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.4.1 importlib_metadata/3.7.3 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.51.0 CPython/3.9.1+
File hashes
| Algorithm | Hash digest | |
|---|---|---|
| SHA256 | bf677cd7c9ecf5ce7da75dcd2a29ab9447cbf715f497b7fe2f2d4bc3ca60bac9 |
|
| MD5 | 359025c3c4213a5572f5368332c8595d |
|
| BLAKE2b-256 | ca25fa3ab30e11539227262fb596cc6735faf8d0eb7fa7fbb15ac3e2ae8e14fc |
