py3nt.core package

Submodules

py3nt.core.base module

Base classes

class py3nt.core.base.BaseFactorization

Bases: ABC

Abstract base class for factorization.

factorize:

Factorize a positive integer.

abstract factorize(n) → dict[int, int]

Factorize positive integers not exceeding 10^70.

Parameters:

n (int) – Positive integer to be factorized.

Returns:

Dictionary of canonical prime factorization. Keys correspond to prime factors and values correspond to their multiplicity.

Return type:

dict

class py3nt.core.base.BaseSieve(limit: int, num_primes: int = 0)

Bases: ABC

Abstract base class for sieve.

generate_primes:

Generate primes when size is small.

abstract generate_primes() → None

Generate primes when size is small.

limit: int

num_primes: int = 0

primes_: ndarray

class py3nt.core.base.BaseSieveFactorization(sieve: BaseSieve, largest_small_number: int = 100000000000000)

Bases: BaseFactorization

Base Factorization class with sieve.

regenerate_primes:

Generate primes if necessary.

largest_small_number: int = 100000000000000

regenerate_primes() → None

Generate primes if necessary.

sieve: BaseSieve

py3nt.core.factorize module

Factorize integers

class py3nt.core.factorize.BigIntFactorization

Bases: BaseFactorization

Factorize large positive integers not exceeding a default biggest number.

factorize:

Factorize a positive integer using Pollard’s rho algorithm.

factorize(n) → dict[int, int]

Factorize positive integers not exceeding 10^70.

Parameters:

n (int) – Positive integer to be factorized.

Returns:

Dictionary of canonical prime factorization. Keys correspond to prime factors and values correspond to their multiplicity.

Return type:

dict

class py3nt.core.factorize.FactorizationFactory(N: int, with_sieve: bool = True)

Bases: object

Factorize positive integers not exceeding the default biggest number.

factorize:

Factorize a positive integer.

Raises:

ValueError – If n is negative or exceeds the default biggest number.

N: int

factorize(n: int) → dict[int, int]

Factorize positive integers.

Parameters:

n (int) – A positive integer.

Returns:

Key value pairs of prime factorization. Keys are prime factors. Values are multiplicities of corresponding prime factors.

Return type:

dict[int, int]

Raises:

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

factorizer: BaseFactorization

with_sieve: bool = True

class py3nt.core.factorize.LognSieveFactorization(sieve: BaseSieve, largest_small_number: int = 100000000000000)

Bases: BaseSieveFactorization

Factorize small numbers in logn complexity.

factorize:

Factorize a positive integer using pre-stored prime factors.

factorize(n: int) → dict[int, int]

Factorize positive integers not exceeding 10^70.

Parameters:

n (int) – Positive integer to be factorized.

Returns:

Dictionary of canonical prime factorization. Keys correspond to prime factors and values correspond to their multiplicity.

Return type:

dict

class py3nt.core.factorize.NaiveSqrtFactorization

Bases: BaseFactorization

Factorize small numbers in sqrt(n) complexity.

factorize:

Factorize a positive integer using naive sqrt method.

factorize(n: int) → dict[int, int]

Factorize positive integers not exceeding 10^70.

Parameters:

n (int) – Positive integer to be factorized.

Returns:

Dictionary of canonical prime factorization. Keys correspond to prime factors and values correspond to their multiplicity.

Return type:

dict

class py3nt.core.factorize.SieveSqrtFactorization(sieve: BaseSieve, largest_small_number: int = 100000000000000)

Bases: BaseSieveFactorization

Factorization using naive sieve and primes not exceeding \(\sqrt{n}\).

factorize:

Factorize a positive integer using sieve generated primes not exceeding \(\sqrt{n}\).

factorize(n: int) → dict[int, int]

Factorize positive integers not exceeding 10^70.

Parameters:

n (int) – Positive integer to be factorized.

Returns:

Dictionary of canonical prime factorization. Keys correspond to prime factors and values correspond to their multiplicity.

Return type:

dict

py3nt.core.factorize.is_prime_power(n: int) → tuple[int, int]

Check if \(n\) is a prime power or not.

Parameters:

n (int) – A positive integer.

Returns:

\((p, e)\) where \(n=p^{e}\).

Return type:

tuple[int, int]

py3nt.core.primality_test module

Define primality tests

py3nt.core.primality_test.is_prime(n: int) → bool

Check if a positive integer is prime.

Parameters:

n (int) – A positive integer.

Returns:

If True, then \(n\) is a prime (probable if \(n\) is large). Otherwise composite.

Return type:

bool

py3nt.core.primality_test.is_prime_naive(n: int) → bool

Test numbers not exceeding \(\sqrt{n}\) for primality.

Parameters:

n (int) – A positive integer for primality testing.

Returns:

True if \(n\) is prime, False otherwise.

Return type:

bool

Raises:

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

py3nt.core.primality_test.miller_rabin(n: int, n_witnesses: int = 5) → bool

Miller-Rabin primality test.

Parameters:

• n (int) – A positive integer.

• n_witnesses (int, optional) – Number of witnesses for the test, by default 5.

Returns:

True if \(n\) is prime, False otherwise.

Return type:

bool

py3nt.core.primality_test.solovay_strassen(n: int, max_iter: int = 10) → bool

Solovay-Strassen primality test.

Parameters:

• n (int) – A positive integer.

• max_iter (int, optional) – Number of retries, by default 10

Returns:

True if \(n\) is prime, False otherwise.

Return type:

bool

py3nt.core.sieve module

Generate primes using sieve

class py3nt.core.sieve.SieveOfEratosthenes(limit: int, num_primes: int = 0)

Bases: BaseSieve

Sieve of Eratosthenes for generating primes. Usually used for factorizing by division of primes not exceeding \(\sqrt{n}\). So, in most cases limit should be set to \(\ceil{\sqrt{n}}\).

generate_primes:

Generate primes up to limit using sieve of Eratosthenes.

generate_primes() → None

Generate primes and set it in self.primes_

class py3nt.core.sieve.SieveOfEratosthenesOptimized(limit: int, num_primes: int = 0)

Bases: BaseSieve

We can store smallest prime factors for \(\log{n}\) factorization. Therefore, \(n\) must be in sieve range.

generate_primes:

Generate primes using pre-stored prime factors of positive integers.

generate_primes() → None

Generate primes using largest prime factors

largest_prime_factors_: ndarray

Module contents