Univariate Polynomial Evaluation using Horner Scheme

A linear-space linear-time sequential recursive algorithm for evaluating a univariate polynomial (a polynomial of one variable) is the Horner scheme: Function evaluate : (A, x) : y is, where a is the top of A, If A is empty, y is zero. Otherwise if A is a singleton, y is a. Otherwise, y is a [...]

Modular Exponentiation

Function modex : (base, power, modulo) : result is If power = 0, result is 1. Otherwise if power = 1, result is base. Otherwise, result is modex(base, power div 2, modulo) squared, modulo modulo, multiplied by modex(base, power mod 2, modulo), modulo modulo.