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