Danger
Nothing here should be used for any security purposes.
Number Theory¶
This module is imported with:
import toy_crypto.nt
The module contains classes for the factorization of numbers and for creating a sieve of Eratosthenes.
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.
- class toy_crypto.nt.FactorList(prime_factors: list[tuple[int, int]] = [], check_primes: bool = False)¶
A FactorList is an list of (prime, exponent) tuples.
It represents the prime factorization of a number.
prime_factors should be a list of (prime, exponent) tuples.
Either you ensure that the primes really are prime or use
check_primes = True.- normalize(check_primes: bool = False) Self¶
Deduplicates and sorts in prime order, removing exponent == 0 cases.
- Raises:
TypeError – if prime and exponents are not ints
ValueError – if p < 2 or e < 0
- Parameters:
check_primes (bool)
- Return type:
This only checks that primes are prime if
check_primesis True.
- 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¶
Return (self)^n, where n is positive int.
- Parameters:
n (int)
- Return type:
- radical() FactorList¶
All exponents on factors set to 1
- Return type:
- toy_crypto.nt.factor(n: int, ith: int = 0) FactorList
Returns list (prime, exponent) factors of n. Starts trial div at ith prime.
This wraps
primefac.primefac(), but creates our FactorList- Parameters:
- Return type:
The Sieve class¶
- class toy_crypto.nt.Sieve(n: int)¶
Sieve of Eratosthenes.
The good parts of this implementation are lifted from the example provided with the bitarray package source.
Creates sieve covering the first n integers.
- Raises:
TypeError – if n in not an int.
ValueError – if n < 2.
- Parameters:
n (int)
- property array: bitarray¶
The sieve as a bitarray.
- classmethod clear() None¶
Resets the cached array.
There is no reason to ever use this outside of performance testing.
- Return type:
None
- nth_prime(n: int) int¶
Returns n-th prime.
- Raises:
ValueError – if n exceeds count.
- Parameters:
n (int)
- Return type:
Functions¶
- toy_crypto.nt.egcd(a: int, b: int) tuple[int, int, int]¶
returns (g, x, y) such that \(ax + by = \gcd(a, b) = g\).
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.
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¶
Returns list (prime, exponent) factors of n. Starts trial div at ith prime.
This wraps
primefac.primefac(), but creates our FactorList- Parameters:
- Return type:
- toy_crypto.nt.mod_sqrt(a: int, m: int) list[int]¶
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.