ecdsa.numbertheory module

exception ecdsa.numbertheory.Error

Bases: Exception

Base class for exceptions in this module.

add_note()

Exception.add_note(note) – add a note to the exception

args

with_traceback()

Exception.with_traceback(tb) – set self.__traceback__ to tb and return self.

exception ecdsa.numbertheory.JacobiError

Bases: Error

add_note()

Exception.add_note(note) – add a note to the exception

args

with_traceback()

Exception.with_traceback(tb) – set self.__traceback__ to tb and return self.

exception ecdsa.numbertheory.NegativeExponentError

Bases: Error

add_note()

Exception.add_note(note) – add a note to the exception

args

with_traceback()

Exception.with_traceback(tb) – set self.__traceback__ to tb and return self.

exception ecdsa.numbertheory.SquareRootError

Bases: Error

add_note()

Exception.add_note(note) – add a note to the exception

args

with_traceback()

Exception.with_traceback(tb) – set self.__traceback__ to tb and return self.

ecdsa.numbertheory.carmichael(n)

Return Carmichael function of n.

Carmichael(n) is the smallest integer x such that m**x = 1 mod n for all m relatively prime to n.

ecdsa.numbertheory.carmichael_of_factorized(f_list)

Return the Carmichael function of a number that is represented as a list of (prime,exponent) pairs.

ecdsa.numbertheory.carmichael_of_ppower(pp)

Carmichael function of the given power of the given prime.

ecdsa.numbertheory.factorization(n)

Decompose n into a list of (prime,exponent) pairs.

ecdsa.numbertheory.gcd(*a)

Greatest common divisor.

Usage: gcd([ 2, 4, 6 ]) or: gcd(2, 4, 6)

ecdsa.numbertheory.inverse_mod(a, m)

Inverse of a mod m.

ecdsa.numbertheory.is_prime(n)

Return True if x is prime, False otherwise.

We use the Miller-Rabin test, as given in Menezes et al. p. 138. This test is not exact: there are composite values n for which it returns True.

In testing the odd numbers from 10000001 to 19999999, about 66 composites got past the first test, 5 got past the second test, and none got past the third. Since factors of 2, 3, 5, 7, and 11 were detected during preliminary screening, the number of numbers tested by Miller-Rabin was (19999999 - 10000001)*(2/3)*(4/5)*(6/7) = 4.57 million.

ecdsa.numbertheory.jacobi(a, n)

Jacobi symbol

ecdsa.numbertheory.kinda_order_mod(x, m)

Return the order of x in the multiplicative group mod m’, where m’ is the largest factor of m relatively prime to x.

ecdsa.numbertheory.largest_factor_relatively_prime(a, b)

Return the largest factor of a relatively prime to b.

ecdsa.numbertheory.lcm(*a)

Least common multiple.

Usage: lcm([ 3, 4, 5 ]) or: lcm(3, 4, 5)

ecdsa.numbertheory.lcm2(a, b)

Least common multiple of two integers.

ecdsa.numbertheory.modular_exp(base, exponent, modulus)

Raise base to exponent, reducing by modulus

ecdsa.numbertheory.next_prime(starting_value)

Return the smallest prime larger than the starting value.

ecdsa.numbertheory.order_mod(x, m)

Return the order of x in the multiplicative group mod m.

ecdsa.numbertheory.phi(n)

Return the Euler totient function of n.

ecdsa.numbertheory.polynomial_exp_mod(base, exponent, polymod, p)

Polynomial exponentiation modulo a polynomial over ints mod p.

Polynomials are represented as lists of coefficients of increasing powers of x.

ecdsa.numbertheory.polynomial_multiply_mod(m1, m2, polymod, p)

Polynomial multiplication modulo a polynomial over ints mod p.

Polynomials are represented as lists of coefficients of increasing powers of x.

ecdsa.numbertheory.polynomial_reduce_mod(poly, polymod, p)

Reduce poly by polymod, integer arithmetic modulo p.

Polynomials are represented as lists of coefficients of increasing powers of x.

ecdsa.numbertheory.square_root_mod_prime(a, p)

Modular square root of a, mod p, p prime.