README

March 13, 2026 · View on GitHub

Math::Prime::Util version 0.75

A comprehensive number theory module for Perl, also available as "ntheory". It provides over 370 functions covering:

Prime sieving, generation, and iteration
Primality testing (BPSW, Miller-Rabin, Lucas, Frobenius, AKS) and proving
Integer factoring (trial, Pollard rho, p-1, p+1, SQUFOF, ECM)
Prime counting: exact (Lehmer/LMO), bounds, and approximations
Nth prime, twin primes, almost primes, semiprimes
Random prime generation (cryptographic CSPRNG)
Combinatorics: binomial, factorial, Stirling, partitions, permutations
Multiplicative functions: euler_phi, moebius, divisor_sum, liouville, etc.
Modular arithmetic: powmod, sqrtmod, chinese (CRT), znorder, znlog
Integer arithmetic: addint, mulint, divint, powint, etc. (arbitrary size)
Special functions: Riemann zeta, R, Li, Lambert W, Chebyshev theta/psi
Iterators: forprimes, forcomposites, fordivisors, forcomb, forpart, etc.
Integer set operations: union, intersection, minus, delta, sumset, etc.

Performance-critical code is written in C (XS). A pure Perl backend is included for portability. For bignum inputs, installing the optional Math::Prime::Util::GMP module gives a large additional speedup.

The default sieving and factoring are intended to be the fastest on CPAN, and are faster than Math::Prime::XS, Math::Prime::FastSieve, Math::Factor::XS, Math::Big, Math::Factoring, Math::Primality, and Crypt::Primes. For native-size integers it is typically faster than Math::Pari. With Math::Prime::Util::GMP installed it is usually faster than Math::Pari for bigints as well.

SYNOPSIS

use Math::Prime::Util qw/:all/;

or: use ntheory qw/:all/;

Sieving and iteration

my $aref = primes(100_000_000); # array ref of primes my @twins = @{ twin_primes(1000, 2000) }; # twin primes in range forprimes { say } 1e6, 1e6+1000; # iterate over primes

Primality

say is_prime(1000000007) ? "prime" : "composite"; say is_provable_prime($n) ? "proven prime" : "not prime";

Factoring

my @factors = factor(1234567890); my @fexp = factor_exp("290375823984720394875209384750932");

Prime counting

say prime_count(1e11); # exact: 4118054813 say prime_count_approx(int(1e18)); # fast approximation

Number-theoretic functions

say euler_phi(240); # 64 say moebius(30); # -1 say carmichael_lambda(1002); # 166

Modular arithmetic

say powmod(2, 1000, 1009); # $2^{1000}$ mod 1009 say chinese([14,643], [254,419]); # CRT say znorder(2, 1009); # multiplicative order

See the POD documentation for full details on all functions: perldoc Math::Prime::Util

INSTALLATION

To install this module:

perl Makefile.PL make make test make install

You will need a C compiler compatible with the compiler used to build Perl. Since the routines are meant to be used from Perl, the data types will match the ones used with the Perl you are installing for. This means a 32-bit Perl running on a 64-bit machine will result in a 32-bit library.

DEPENDENCIES

Perl 5.6.2 or later (5.8 or later is preferred).

C89 compiler, 32-bit or 64-bit.

Optional: Math::Prime::Util::GMP for faster bignum operations.

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.