modular-towers
An algorithm that computes modular nested exponents (or towers) efficiently.
🚩 Table of Contents
🗺️ Overview
modular-towers exports a Python function mod_tower that takes as input an arbitrarily long sequence of positive integers 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).
🏳️ Prerequisites
sympy is currently required as the algorithm uses its totient function. In the future, a custom totient function will be added so that sympy is not required, making the module self-contained.
For best performance, install gmpy2:
$ apt install libgmp-dev libmpfr-dev libmpc-dev # required for gmpy2
$ pip install gmpy2
gmpy2 is not required but it offers more efficient versions of some of Python's built-in math functions. If gmpy2 is not installed, the module simply uses the built-in functions.
🔧 Installation
Installing with pip is the easiest:
$ pip install modular-towers
A development version can be installed from GitHub
using setuptools, provided you have sympy installed already:
$ git clone https://github.com/avivbrook/modular-towers
$ cd modular-towers
$ python setup.py install
💡 Examples
>>> from modular_towers import mod_tower as modtow
>>> modtow([6,5,4,3,2], 1948502738) # 6^(5^(4^(3^2))) mod 1948502738
951546056
To benchmark the main function:
>>> from modular_towers.core.tests import test_core
>>> test_core(list_lengths=(10, 100, 1000), bit_lengths=(16, 128, 1024), mod_bit_lengths=(16, 32, 64))
1 maintainer
Release files for modular-towers 0.1.4
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | |
|---|---|---|---|
| modular-towers-0.1.4.tar.gz | 20.6 kB | Details |
Built distribution (wheel)
| File | Interpreter | ABI | Platform | Reset |
|---|---|---|---|---|
| modular_towers-0.1.4-py3-none-any.whl | Python 3 | none | any | Details |
Total release size: 41.4 kB
Release files / modular-towers-0.1.4.tar.gz
| Download URL | modular-towers-0.1.4.tar.gz |
|---|---|
| Size | 20.6 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
7d3a4084391c1b6b900d799d10c0a5d01d2fcc182dd553f72b32228ec1253ce9
|
|
BLAKE2b-256 checksum How to use checksums |
7b94be81496fb2af45538db33ab7e1796ef71e4dcb3cd9decb6b8f10652f0a94
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is 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.59.0 CPython/3.9.2
|
Release files / modular_towers-0.1.4-py3-none-any.whl
| Download URL | modular_towers-0.1.4-py3-none-any.whl |
|---|---|
| Size | 20.8 kB |
| Tags | Python 3 |
|
SHA-256 checksum How to use checksums |
7dfae9fe954bac8c07285b55c64366b5940b6fd4431b1a596bac3eb3c4b41059
|
|
BLAKE2b-256 checksum How to use checksums |
cf23124ccd6eba840eb5ca9ff29ec4c00bfc279cb15fa9b6c91c6525c6106a69
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is 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.59.0 CPython/3.9.2
|
