py3nt.numbers package

Submodules

py3nt.numbers.integer module

Integers

class py3nt.numbers.integer.Integer[source]

Bases: int

Integer class

multiply_modular:

Modular multiplication of current integer with another integer.

pollard_rho_factor:

Find a divisor of current integer using Pollard’s rho factor algorithm.

brent_pollard_rho_factor() → int[source]

Brent’s optimization of Pollard’s rho algorithm.

Returns:

A non-trivial factor of \(n\) when \(n\) is not a prime.

Return type:

int

kthroot(k: int) → int[source]
Parameters:

k (int) – A positive integer.

Returns:

A positive integer \(r\) such that \(r^{k}\leq n<r^{k+1}\).

Return type:

int

multiply_modular(other: int, modulus: int) → int[source]

Calculate self*other%modulus. This remainder will always be non-negative. If negative integers are provided, they will be converted to positive first.

Parameters:

  • other (int) – Multiplier.

  • modulus (int) – Modulo used for multiplcation.

Returns:

Multiplication of self and other modulo modulus.

Return type:

int

pollard_rho_factor(a: int, c: int, max_iter: int = 5) → int[source]

Find a factor of n greater than 1 using Pollard’s rho factorization. Use \(f(x) = x^2+c\)

Parameters:

  • a (int) – Initial value of x.

  • c (int) – Constant in the polynomial.

  • max_iter (int, optional) – Maximum number of iteration to find a non-trivial divisor, by default 5

Returns:

A non-trivial divisor of n if n is not a prime.

Return type:

int

Raises:

ValueError – If n can be factorized using classical sieve or is larger than the biggest number.

Module contents