klefki.algorithms

Module Contents

Functions

extended_euclidean_algorithm(a: int, b: int, one=1, zero=0) → Tuple[int, int, int]	Returns a three-tuple (gcd, x, y) such that
double_and_add_algorithm(times: int, x: T, init: T) → T	Returns the result of n * x, computed using

klefki.algorithms.extended_euclidean_algorithm(a: int, b: int, one=1, zero=0) → Tuple[int, int, int]

Returns a three-tuple (gcd, x, y) such that a * x + b * y == gcd, where gcd.

This function implements the extended Euclidean algotithm and runs in O(log b) in the worst case

klefki.algorithms.double_and_add_algorithm(times: int, x: T, init: T) → T

Returns the result of n * x, computed using the double and add algorithm.