klefki.numbers

Package Contents

Functions

rsa_lambda(p, q)

rsa_phi(p, q)

fn_lambda(n)

Carmichael Function

fn_phi(n)

Eulers Totient Function

lcm(a, b)

length(n, base=10)

Blength(n, base=2)

Dlength(n, base=10)

power(base, exp)

Fast power calculation using repeated squaring

invmod(a, p)

modpow(base, exponent, modulus)

Modular exponent:

modular_sqrt(a, p)

ref: https://gist.github.com/nakov/60d62bdf4067ea72b7832ce9f71ae079

legendre_symbol(a, p)

Compute the Legendre symbol a|p using

crt(a_list, n_list) → int

Applies the Chinese Remainder Theorem to find the unique x such that x = a_i (mod n_i) for all i.
klefki.numbers.rsa_lambda(p, q)
klefki.numbers.rsa_phi(p, q)
klefki.numbers.fn_lambda(n)

Carmichael Function A number n is said to be a Carmichael number if it satisfies the following modular arithmetic condition: power(b, n-1) MOD n = 1, for all b ranging from 1 to n such that b and n are relatively prime, i.e, gcd(b, n) = 1

klefki.numbers.fn_phi(n)

Eulers Totient Function https://stackoverflow.com/questions/18114138/computing-eulers-totient-function

klefki.numbers.carmichael
klefki.numbers.totient
klefki.numbers.lcm(a, b)
klefki.numbers.length(n, base=10)
klefki.numbers.Blength(n, base=2)
klefki.numbers.Dlength(n, base=10)
klefki.numbers.power(base, exp)

Fast power calculation using repeated squaring

klefki.numbers.invmod(a, p)
klefki.numbers.modpow(base, exponent, modulus)
Modular exponent:

c = b ^ e mod m

Returns c. (http://www.programmish.com/?p=34)

klefki.numbers.modular_sqrt(a, p)

ref: https://gist.github.com/nakov/60d62bdf4067ea72b7832ce9f71ae079 Find a quadratic residue (mod p) of ‘a’. p must be an odd prime. Solve the congruence of the form: x^2 = a (mod p) And returns x. Note that p - x is also a root. 0 is returned is no square root exists for these a and p. The Tonelli-Shanks algorithm is used (except for some simple cases in which the solution is known from an identity). This algorithm runs in polynomial time (unless the generalized Riemann hypothesis is false).

klefki.numbers.legendre_symbol(a, p)

Compute the Legendre symbol a|p using Euler’s criterion. p is a prime, a is relatively prime to p (if p divides a, then a|p = 0) Returns 1 if a has a square root modulo p, -1 otherwise.

klefki.numbers.crt(a_list, n_list) → int

Applies the Chinese Remainder Theorem to find the unique x such that x = a_i (mod n_i) for all i. :param a_list: A list of integers a_i in the above equation. :param n_list: A list of integers b_i in the above equation. :return: The unique integer x such that x = a_i (mod n_i) for all i. copy from:: https://github.com/cryptovoting/damgard-jurik/blob/master/damgard_jurik/utils.py#L100