Skip to content

Python code to implement various number theory, elliptic curve and finite field computations.

License

Notifications You must be signed in to change notification settings

Robert-Campbell-256/Number-Theory-Python

Repository files navigation

Number Theory Python

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

About

Python code to implement various number theory, elliptic curve and finite field computations.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages