Danger

Nothing here should be used for any security purposes.

  • If you need cryptographic tools in a Python environment use pyca.

  • If you need efficient and reliable abstract math utilities in a Python-like environment consider using SageMath.

Number Theory#

This module is imported with:

import toy_crypto.nt

The module contains pure Python classes and functions for a handful of integer math utilities. The SymPy ntheory module is almost certainly going to have better versions of everything here.

The FactorList class#

Some of the methods here are meant to mimic what we see in SageMath’s Factorization class, but it only does so partially, and only for int. If you need something as reliable and general and fast as SageMath’s Factorization tools, use SageMath.

The actual factoring is done by the primefac package.

class toy_crypto.nt.FactorList(prime_factors: list[tuple[int, int]] = [], check_primes: bool = False) → None[source]#

A FactorList is an list of (prime, exponent) tuples.

It represents the prime factorization of a number.

Parameters:

prime_factors should be a list of (prime, exponent) tuples.

Either you ensure that the primes really are prime or use check_primes = True.

Parameters:
coprimes() → Iterator[int][source]#

Iterator of coprimes.

Return type:

Iterator[int]

property factors_are_prime: bool#

True iff all the alleged primes are prime.

is_integral() → bool[source]#

Always true for integer factorization.

Return type:

bool

property n: int#

The integer that this is a factorization of

normalize(check_primes: bool = False) → Self[source]#

Deduplicates and sorts in prime order, removing exponent == 0 cases.

Raises:

This only checks that primes are prime if check_primes is True.

Parameters:

check_primes (bool, default: False)

Return type:

Self

property phi: int#

Returns Euler’s Totient (phi)

\(\phi(n)\) is the number of numbers less than n which are coprime with n.

This assumes that the factorization (self) is a prime factorization.

pow(n: int) → FactorList[source]#

Return (self)^n, where n is positive int.

Parameters:

n (int)

Return type:

FactorList

radical() → FactorList[source]#

All exponents on factors set to 1

Return type:

FactorList

radical_value() → int[source]#

Product of factors each used only once.

Return type:

int

unit() → int[source]#

Unit is always 1 for positive integer factorization.

Return type:

int

value() → int[source]#

Same as n().

Return type:

int

toy_crypto.nt.factor(n: int, ith: int = 0) → FactorList[source]

Returns list (prime, exponent) factors of n. Starts trial div at ith prime.

This wraps primefac.primefac(), but creates our FactorList

Parameters:

  • n (int)

  • ith (int, default: 0)

Return type:

FactorList

Functions#

toy_crypto.nt.egcd(a: int, b: int) → tuple[int, int, int][source]#

returns (g, x, y) such that \(ax + by = \gcd(a, b) = g\).

Parameters:
Return type:

tuple[int, int, int]

toy_crypto.nt.probably_prime(n: int, k: int = 4) → bool[source]#

Returns True if n is prime or if you had really bad luck.

Runs the Miller-Rabin primality test with k trials.

If you need a real primality check, use sympy.isprime() instead.

Parameters:
Return type:

bool

toy_crypto.nt.get_prime(bit_size: int, k: int = 4, leading_1_bits: int = 1, e: int = 1) → int[source]#

Return a randomly chosen prime of bit_size bits.

Parameters:

  • bit_size (int) – Size in bits of the prime to be generated

  • k (int, default: 4) – Number of witnesses to primality we require.

  • leading_1_bits (int, default: 1) – How many most significant bits should be set.

  • e (int, default: 1) – Number which gcd(prime -1, e) must be 1. Default of 1 places no restriction on the prime.

Return type:

int

The produces primes for which the leading two bits are 1. So it is not a uniform distribution of primes in the range

class toy_crypto.nt.Modulus#

type Modulus is an int greater than 1

alias of int

toy_crypto.nt.is_modulus(n: Any) → TypeGuard[Modulus][source]#
Parameters:

n (Any)

Return type:

TypeGuard[NewType(Modulus, int)]

Wrapping some math#

There are functions which either weren’t part of the Python standard library at the time I started putting some things together, or I wasn’t aware of their existence, or I just wanted to write for myself some reason or the other.

But now, at least in this module, I wrap those.

toy_crypto.nt.gcd(*integers: int) → int[source]#

Returns greatest common denominator of arguments.

Parameters:

integers (int)

Return type:

int

toy_crypto.nt.lcm(*integers: int) → int[source]#

Least common multiple

Parameters:

integers (int)

Return type:

int

toy_crypto.nt.modinv(a: int, m: int) → int[source]#

Returns b such that \(ab \equiv 1 \pmod m\).

Raises:

ValueError – if a is not coprime with m

Parameters:
Return type:

int

Wrapping from primefac#

Functions here wrap functions from the primefac Python package. Note that the wrapping is not completely transparent in some cases. That is, the interface and behavior may differ.

toy_crypto.nt.factor(n: int, ith: int = 0) → FactorList[source]#

Returns list (prime, exponent) factors of n. Starts trial div at ith prime.

This wraps primefac.primefac(), but creates our FactorList

Parameters:

  • n (int)

  • ith (int, default: 0)

Return type:

FactorList

toy_crypto.nt.mod_sqrt(a: int, m: int) → list[int][source]#

Modular square root.

For prime m, this generally returns a list with either two members, \([r, m - r]\) such that \(r^2 = {(m - r)}^2 = a \pmod m\) if such an a is a quadratic residue the empty list if there is no such r.

However, for compatibility with SageMath this can return a list with just one element in some special cases

  • returns [0] if \(m = 3\) or \(a = 0\).

  • returns [a % m] if \(m = 2\).

Otherwise it returns a list with the two quadratic residues if they exist or and empty list otherwise.

Warning: The behavior is undefined if m is not prime.

Parameters:
Return type:

list[int]

toy_crypto.nt.is_square(n: int) → bool[source]#

True iff n is a perfect square.

Parameters:

n (int)

Return type:

bool

toy_crypto.nt.isqrt(n: int) → int[source]#

returns the greatest r such that r * r =< n

Parameters:

n (int)

Return type:

int

toy_crypto.nt.isprime(n: int) → bool[source]#

False if composite; True if very probably prime.

Parameters:

n (int)

Return type:

bool