modular-nested-exponentiation¶
An algorithm that computes modular nested exponentiation efficiently.
mod-nest-exp exports a Python function mod_nest_exp 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).
To date, this problem was not solvable by computers in the general case.
Setup¶
Run pip install mod-nest-exp in a shell to download the latest release from PyPI, or have a look at the
Installation page to find other ways to install mod-nest-exp.
Note
mod-nest-exp requires Python v3.6+. For best performance, install gmpy2 and sympy:
$ apt install libgmp-dev libmpfr-dev libmpc-dev # required for gmpy2
$ pip install gmpy2 sympy