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

# cpython makes the computations more efficient
$ 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

To-do

• add a factorisation module in case the user does not have sympy installed