mod-nest-exp 1.0.9

An algorithm that computes modular nested exponentiation efficiently.

modular-nested-exponentiation

An algorithm that computes modular nested exponentiation efficiently.

🚩 Table of Contents

• Overview
• Prerequisites
• Installation
• Examples

🗺️ Overview

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).

🏳️ 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 mod-nest-exp

A development version can be installed from GitHub using setuptools, provided you have sympy installed already:

$ git clone https://github.com/avivbrook/modular-nested-exponentiation
$ cd modular-nested-exponentiation
$ python setup.py install

💡 Examples

>>> from mod_nest_exp import mod_nest_exp
>>> mod_nest_exp([6,5,4,3,2], 1948502738) # 6^(5^(4^(3^2))) mod 1948502738
951546056

To benchmark the main function:

>>> from mod_nest_exp.core.tests import test_core
>>> test_core(list_lengths=(10, 100, 1000), bit_lengths=(16, 128, 1024), mod_bit_lengths=(16, 32, 64))