py3nt.congruence package

Submodules

py3nt.congruence.basics module

Some basic functions in modular arithmetic.

py3nt.congruence.basics.chinese_remainder_theorem(r: Sequence[int], m: Sequence[int]) → int

Chinese Remainder Theorem. Given \(x\equiv r_{i}\pmod{m_{i}}\) where \(\gcd(m_{i},m_{j})=1\) for \(i\neq j\).

Parameters:

• r (Sequence[int]) – Remainders.

• m (Sequence[int]) – Modulis.

Returns:

Minimum \(x\) that satisfies the congruences.

Return type:

int

Raises:

ValueError – If \(\gcd(m_{i},m_{j})\neq1\) for some \(i\neq j\). Or if the remainders and modulis have different length.

py3nt.congruence.basics.extended_euclidean(a: int, b: int) → tuple[int, int, int]

Given \(a,b\). Find \(x,y\) such that \(ax+by=\gcd(a,b)\). Such \(x,y\) exists by Bézout’s identity. Use Extended Euclidean algorithm.

Parameters:

• a (int) – An integer.

• b (int) – An integer.

Returns:

\(x,y,\gcd(x,y)\).

Return type:

tuple[int, int, int]

py3nt.congruence.basics.inverse(a: int, n: int, is_prime: bool = False) → int

Calculate modular inverse of \(a\pmod{n}\). Use Extended algorithm when \(\gcd(a,n)=1\).

Parameters:

• a (int) – An integer.

• n (int) – A positive integer greater than 1.

• is_prime (bool, optional) –

  Whether \(n\) is prime or not, by default False. If prime, then Fermat’s little theorem is used to calculate inverse.

  \[a^{p-2} \equiv a^{-1}\pmod{p}\]

Returns:

\(x\) such that \(ax\equiv1\pmod{n}\).

Return type:

int

Raises:

ValueError – If \(\gcd(a,n) > 1\) or \(n<2\).

py3nt.congruence.binomial module

Congruence of binomial coefficients

py3nt.congruence.binomial.binomial_modulo_small_prime(n: int, k: int, p: int) → int

Uses Lucas theorem to calculate binomial coefficients modulo primes. If

\[\begin{split}n = (n_{r}\ldots n_{0})_{p}\\ k = (k_{r}\ldots k_{0})_{p}\end{split}\]

then

\[\binom{n}{k} \equiv \binom{n_{r}}{k_{r}}\cdots\binom{n_{0}}{k_{0}}\pmod{p}\]

Parameters:

• n (int) – An integer.

• k (int) – An integer.

• p (int) – A prime.

• factorials (np.ndarray, optional) – Array of precalculated factorials \(\pmod{p}\)., by default None

Returns:

\(\binom{n}{k}\pmod{p}\) when \(n,k< p\).

Return type:

int

py3nt.congruence.binomial.small_binomial_modulo_prime(n: int, k: int, p: int, factorials: None | ndarray = None) → int

Parameters:

• n (int) – An integer.

• k (int) – An integer.

• p (int) – A prime.

• factorials (Optional[np.ndarray], optional) – Array of precalculated factorials \(\pmod{p}\)., by default None

Returns:

\(\binom{n}{k}\pmod{p}\) when \(n,k< p\).

Return type:

int

Raises:

ValueError – If \(n\) or \(k\) is negative.

py3nt.congruence.primitives module

Order/primitive root functions

py3nt.congruence.primitives.highest_power_of_2(a: int) → int

Calculate \(\nu_{2}(a)\).

Parameters:

a (int) – An integer.

Returns:

Highest power of 2 that divides \(a\).

Return type:

int

py3nt.congruence.primitives.least_primitive_root_modulo_prime(p: int, factorizer: FactorizationFactory) → int

Find the least primitive root \(\pmod{p}\).

Parameters:

• p (int) – A prime.

• factorizer (FactorizationFactory) – Used to calculate order \(\pmod{p}\).

Returns:

Least primitive root.

Return type:

int

Raises:

ValueError – If \(p\) is not a prime.

py3nt.congruence.primitives.order_modulo_n(a: int, n: int, factorizer: FactorizationFactory) → int

Caculate \(\mbox{ord}_{n}(a)\). The smallest positive integer such that

\[a^{\mbox{ord}_{n}(a)} \equiv1\pmod{n}\]

Parameters:

• a (int) – An integer.

• n (int) – A positive integer.

• factorizer (FactorizationFactory) – Used to factorize \(n\).

Returns:

\(\mbox{ord}_{n}(a)\).

Return type:

int

Raises:

ValueError – If \(\gcd(a,n) > 1\).

py3nt.congruence.primitives.order_modulo_power_of_2(a: int, k: int) → int

Calculate \(\mbox{ord}_{2^{k}}(a)\). The smallest positive integer such that

\[a^{\mbox{ord}_{2^{k}}(a)} \equiv1\pmod{2^{k}}\]

Parameters:

• a (int) – _description_

• k (int) – _description_

Returns:

_description_

Return type:

int

Raises:

ValueError – _description_

py3nt.congruence.primitives.order_modulo_prime_power(a: int, p: int, e: int, factorizer: FactorizationFactory) → int

Caculate \(\mbox{ord}_{p^{e}}(a)\). The smallest positive integer such that

\[a^{\mbox{ord}_{p^{e}}(a)} \equiv1\pmod{p^{e}}\]

Parameters:

• a (int) – An integer.

• p (int) – A prime.

• e (int) – A positive integer. \(p^{e}\) must not exceed the default biggest number.

• factorizer (FactorizationFactory) – Used to factorize p-1.

Returns:

\(\mbox{ord}_{p}(a)\).

Return type:

int

py3nt.congruence.primitives.primitive_root_modulo_n(n: int, factorizer: FactorizationFactory) → int

Primitive root \(n\) if it exists.

Parameters:

• n (int) – A positive integer.

• factorizer (FactorizationFactory) – Used to calculate primitive root \(\pmod{p}\).

Returns:

A primitive root.

Return type:

int

Raises:

ValueError – If \(n<3\) or \(n\) does not have a primitive root.

py3nt.congruence.primitives.primitive_root_modulo_prime_power(p: int, e: int, factorizer: FactorizationFactory) → int

Find the least primitive root \(\pmod{p^{e}}\).

Parameters:

• p (int) – A prime.

• e (int) – A positive integer.

• factorizer (FactorizationFactory) – Used to calculate order \(\pmod{p^{e}}\).

Returns:

Least primitive root.

Return type:

int

py3nt.congruence.quadratic module

Quadratic residues and symbols.

py3nt.congruence.quadratic.jacobi_symbol(a: int, n: int) → int

Calculate Jacobi symbol.

Parameters:

• a (int) – An integer.

• n (int) – A positive odd integer.

Returns:

Jacobi symbol \((\frac{a}{n})\in\{-1,0,1\}\).

Return type:

int

Raises:

ValueError – If \(n\) is not positive or odd.

py3nt.congruence.quadratic.legendre_symbol(a: int, p: int) → int

Calculate Legendre symbol.

Parameters:

• a (int) – An integer.

• p (int) – A prime.

Returns:

Legendre symbol \((\frac{a}{p})\in\{-1,0,1\}\).

Return type:

int

Module contents