Source code for tryalgo.fast_exponentiation

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Fast Exponentiation
jill-jenn vie et christoph durr and louis abraham - 2014-2018
"""


[docs]def fast_exponentiation2(a, b, q): """Compute (a pow b) % q :param int a b: non negative :param int q: positive :complexity: O(log b) """ assert a >= 0 and b >= 0 and q >= 1 p = 0 # only for documentation p2 = 1 # 2 ** p ap2 = a % q # a ** (2 ** p) result = 1 while b > 0: if p2 & b > 0: # b's binary decomposition contains 2 ** p b -= p2 result = (result * ap2) % q p += 1 p2 *= 2 ap2 = (ap2 * ap2) % q return result
# snip{
[docs]def fast_exponentiation(a, b, q): """Compute (a pow b) % q, alternative shorter implementation :param int a b: non negative :param int q: positive :complexity: O(log b) """ assert a >= 0 and b >= 0 and q >= 1 result = 1 while b: if b % 2 == 1: result = (result * a) % q a = (a * a) % q b >>= 1 return result
# snip}