Skip to main content

An algorithm that computes modular nested exponentiation efficiently.

Project description

Modular nested exponentiation

An algorithm that computes modular nested exponentiation efficiently.

PyPI - License Source codecov PyPI PyPI - Python Version

Downloads

🚩 Table of Contents

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

To date, this problem was not solvable by computers in the general case.

🏳️ Prerequisites

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

The libraries offer more efficient alternatives to a number of functions used as subroutines in the core module.

🔧 Installation

The recommended installation method is from PyPI:

$ pip install mod-nest-exp

A development version can be installed from GitHub source using setuptools:

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

💡 Examples

Small inputs

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

Larger inputs

Here we demonstrate a computation that is not possible with simple modular exponentiation functions such as pow:

>>> from random import randint
>>> seq = [randint(1, 2**64) for _ in range(5)]
>>> seq
[6038140174510300905, 11769918488496772646, 2874847465098133786, 9008748983185995190, 13009674817390511365]
>>> m = randint(1, 2**64)
>>> m
6790053138492639247
>>> mod_nest_exp(seq, m)
3426314670852891859

Benchmark the main function

>>> from mod_nest_exp.core.benchmarks import benchmark_core
>>> benchmark_core(list_lengths=(10, 100, 1000), bit_lengths=(16, 128, 1024), mod_bit_lengths=(16, 32, 64))
Running mod_nest_exp on sequences of l pseudorandom b-bit positive integers over a B-bit modulus (1000 runs per table entry)
=================================================================
                            sequence length l
                  10               100               1000
          ----------------- ----------------- -----------------
  B     b     mean    stdev     mean    stdev     mean    stdev
-----------------------------------------------------------------
       16 |   0.08     0.04     0.08     0.03     0.10     0.03
 16   128 |   0.08     0.11     0.08     0.03     0.10     0.04
     1024 |   0.08     0.03     0.08     0.03     0.11     0.04
-----------------------------------------------------------------
       16 |   0.34     0.32     0.34     0.24     0.35     0.24
 32   128 |   0.33     0.23     0.34     0.23     0.36     0.23
     1024 |   0.33     0.22     0.33     0.24     0.37     0.24
-----------------------------------------------------------------
       16 |   8.82    34.83     6.20    21.27     7.18    30.35
 64   128 |   7.66    30.70     6.71    22.72     7.60    26.92
     1024 |   5.94    25.10     6.67    20.78     6.76    26.28
=================================================================

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

mod-nest-exp-1.1.1.tar.gz (24.8 kB view hashes)

Uploaded source

Built Distribution

mod_nest_exp-1.1.1-py3-none-any.whl (25.7 kB view hashes)

Uploaded py3

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page