modular-towers

An algorithm that computes modular nested exponents (or towers) efficiently.

🚩 Table of Contents

• Overview
• Prerequisites
• Installation
• Examples

🗺️ 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))