A collection of Python modules implementing number theory stuff.
The Number-Theory-Python package currently includes:
- NumbThy.pdf: A short course in number theory
- numbthy.py: Basic number theory functions
- gaussint.py: Basic operations over the Gaussian integers
- finitefield.py: Finite fields of prime power order
- CPimport.txt: Data file of finite field defining polynomials
- ellipticcurve.py: Elliptic curves in affine reduced Weierstrass form over prime order fields
- ECDSA.py: Elliptic curve signatures
Functions implemented in numbthy.py are:
- gcd(a,b) - Compute the greatest common divisor of a and b.
- xgcd(a,b) - Find [g,x,y] such that g=gcd(a,b) and g = ax + by.
- power_mod(b,e,n) - Compute b^e mod n efficiently.
- inverse_mod(b,n) - Compute 1/b mod n.
- is_prime(n) - Test whether n is prime using a variety of pseudoprime tests.
- euler_criterion(a, p) - Test whether a is a quadratic residue mod p.
- euler_phi(n) - Compute Euler's Phi function of n - the number of integers strictly less than n which are coprime to n.
- carmichael_lambda(n) - Compute Carmichael's Lambda function of n - the smallest exponent e such that b**e = 1 for all b coprime to n.
- factor(n) - Return a sorted list of the prime factors of n with exponents.
- prime_divisors(n) - Returns a sorted list of the prime divisors of n.
- is_primitive_root(g,n) - Test whether g is primitive - generates the group of units mod n.
- sqrtmod(a,n) - Compute sqrt(a) mod n using various algorithms.
- TSRsqrtmod(a,grpord,n) - Compute sqrt(a) mod n using Tonelli-Shanks-RESSOL algorithm.
Classes implemented in finitefield.py are:
- FiniteField(p,polycoeffs) is the finite field of characteristic p and given defining polynomial. The methods defined for this class are:
- str(ff), format(ff) and repr(ff) - also implicitly used by print and display functions
- Coerce integer or array of integers to element
- Iterator over all elements of the finite field
- ff.random() - Random element of the finite field
- If a defining polynomial is not specified, the Conway polynomial is used
- FiniteFieldElt(ff,polycoeffs) is the element in the specified finite field. The methods defined for this class are:
- str(elt), format(elt) and repr(elt) - also implicitly used by print and display functions
- elt1.add(elt2) - Add two elements - also overloads the + operator, so elt1 + elt2 (and elt1 += elt2)
- elt1.mul(elt2) - Multiply two elements - also overloads the * operator, so elt1 * elt2 (and elt1 *= elt2)
- elt1.neg() - Additive inverse (aka negative) of an element - also overloads the unary - operator, so -elt1
- elt1.inv() - Multiplicative inverse of an element
- elt1.div(elt2) - Divide two elements - also overloads the / operator, so elt1 / elt2 (and elt1 /= elt2)
- elt1.pow(n) - The nth power of an element - also overloads the ** operator, so elt1**n
- elt1.is_primitive() - Does elt1 generate the multiplicative group
- elt1.order() - Compute the multiplicative order of elt1
Classes implemented in ellipticcurve.py are:
- EllipticCurve(p,[a,b]) is the elliptic curve in Weierstrass form y^2 = x^3 +ax + b (mod p) over the finite field of prime order p. The methods defined for this class are:
- str(ec), format(ec) and repr(ec) - also implicitly used by print and display functions
- EllipticCurveElt(ec,[x,y]) is a point on the specified elliptic curve. The methods defined for this class are:
- str(pt), format(pt) and repr(pt) - also implicitly used by print and display functions
- pt1.add(pt2) - Add two points - also overloads the + operator, so pt1 + pt2 (and pt1 += pt2)
- pt1.neg() - Additive inverse (aka negative) of a point - also overloads the unary - operator, so -pt1
- pt1.mult(n) - The nth multiple of a point - also overloads the * operator, so n*pt1
Classes implemented in ECDSA.py are:
- ECDSA(size,d=key) defines signatures over the NIST curve of size bits, using the optional value d as a private key (otherwise it is randomly generated). The methods defined for this class are:
- ecdsa.sign(msg,k=nonce) - Signs the message string, using the optional value k as a signing nonce (othewise it is randomly generated).
- ecdsa.verify(msg,thesign) - Verifies that thesign is a valid signature for the string msg.
Classes implemented in gaussint.py are:
- GaussInt(a,b) is the Gaussian integer a + bI, where a and b are integers. The methods defined for this class are:
- str(ff) and repr(ff) - also implicitly used by print and display functions
- Coerce integer or complex to element
- elt1.add(elt2) - Add two elements - also overloads the + operator, so elt1 + elt2 (and elt1 += elt2)
- elt1.mult(elt2) - Multiply two elements - also overloads the * operator, so elt1 * elt2 (and elt1 *= elt2)
- elt1.neg() - Additive inverse (aka negative) of an element - also overloads the unary - operator, so -elt1
- elt1.div(elt2) - Divide two elements - also overloads the / operator, so elt1 / elt2 (and elt1 /= elt2)
- elt1.mod(elt2) - Reduce one element mod another - also overloads the % operator, so elt1 % elt2 (and elt1 %= elt2)
- elt1.divmod(elt2) - Divide two elements, returning both quotient and remainder
- elt1.gcd(elt2) - The gcd of two elements
- elt1.xgcd(elt2) - The extended gcd of two elements
- elt1.pow(n) - The nth power of an element - also overloads the ** operator, so elt1**n
- elt1.isprime() - Tests whether elt1 is prime (as a Gaussian integer)
- elt1.factors() - Return a list of the prime factors of elt1
- elt1.factor() - Return a single prime factor of elt1
