NumTheory

© 2009,2012-2013,2016-2018,2021,2022 John Abbott, Anna M. Bigatti
GNU Free Documentation License, Version 1.2



CoCoALib Documentation Index

User documentation

Generalities

The functions in the NumTheory file are predominantly basic operations from number theory. Most of the functions may be applied to machine integers or big integers (i.e. values of type BigInt). Please recall that computational number theory is not the primary remit of CoCoALib, so do not expect to find a complete collection of operations here -- you would do better to look at Victor Shoup's NTL (Number Theory Library), or PARI/GP, or some other specialized library/system.

See also BigIntOps for very basic arithmetic operations on integers, and BigRat for very basic arithmetic operations on rational numbers.

Examples

The Functions Available For Use

Several of these functions give errors if they are handed unsuitable values: unless otherwise indicated below the error is of type ERR::BadArg. All functions expecting a modulus will throw an error if the modulus is less than 2 (or an unsigned long value too large to fit into a long).

GCD, LCM, etc.

The main functions available are:

There is a class called CoprimeFactorBasis_BigInt for computing a coprime factor basis of a set of integers:

Prime generation and tests

These functions are in NumTheory-prime. The functions NextPrime, PrevPrime, RandomNBitPrime and RandomSmallPrime each produce a result of type SmallPrime (essentially a long which is known to be prime).

There are also iterators for generating primes (or almost primes) in increasing order:

If pseq is one of these iterator objects then

Factorization

Pollard Rho Sequence

Other Functions on Integers

Functions on Rationals

Continued Fractions

Several of these functions give errors if they are handed unsuitable values: unless otherwise indicated below the error is of type ERR::BadArg.

Recall that any real number has an expansion as a continued fraction (e.g. see Hardy & Wright for definition and many properties). This expansion is finite for any rational number. We adopt the following conventions which guarantee that the expansion is unique:

For example, with these conventions the expansion of -7/3 is (-3, 1, 2).

The main functions available are:

Chinese Remaindering -- Integer Reconstruction

CoCoALib offers the class CRTMill for reconstructing an integer from several residue-modulus pairs via Chinese Remaindering. At the moment the moduli from distinct pairs must be coprime.

The operations available are:

Rational Reconstruction

CoCoALib offers two heuristic methods for reconstructing rationals from residue-modulus pairs; they have the same user interface but internally one algorithm is based on continued fractions while the other uses lattice reduction. The methods are heuristic, so may (rarely) produce an incorrect result.

NOTE the heuristic requires the (combined) modulus to be a certain amount larger than strictly necessary to reconstruct the correct answer (assuming perfect bounds are known). In practice, this means that the methods always fail if the combined modulus is too small.

The constructors available are:

The operations available are:

There is also a function for deterministic rational reconstruction which requires certain bounds to be given in input. It uses the continued fraction method.

Maintainer Documentation

Bugs, Shortcomings, etc.

Main changes

2022