Documentation Index
User documentation
Generalities
The (number theory) library contains basic functions from number theory.
We follow Cohen (1993), Gathen (2013), Shoup (2017).
Functions Avaiable For Use
Fundamental Number-Theoretic Algorithms
- Least Common Multiple for integers is already included in Scheme with name
lcm. - Also
(expt-mod b e m)is included in Scheme, and computesb^e mod m. - Euclid's algorithm for integers is already included in Scheme with name
gcdand takes any number of inputs. Returns0with no arguments. - Euclid's Extended algorithm is implemented for two arguments,
nandm;(euclid-extended n m)returns three values'(d u v)such thatd = u*n + v*m. - Legendre symbol
(legendre a n). - Kronecker symbol
(kronecker a n). integer-square-rootcomputes the square root of an integer using Newton's method ([Cohen93] - Algorithm 1.7.1).
Power detection
square?use Square Test ([Cohen93] - Algorithm 1.7.3) to decide if given integer is a square.
Primality testing
*primes-less-than-10000*is a table of primes.miller-rabin-prime?decide if Miller-Rabin pseudo prime.solovay-strassen-prime?decide if probable prime.baillie-pomenance-selfridge-wagstaff-prime?decide if strong prbable prime using the algorithm by Baillie-PSW with aid of Lucas probable prime test (not the strong version).prime?use thebaillie-pomenance-selfridge-wagstaff-prime?test to decide if prime.
Wanted functions
- Fundamental Number-Theoretic Algorithms
- Generic Powering algorithms?
- Continued fractions
- Tonelli-Shanks
- Power detection
- Prime power
- Sum of squares
- Divisors
- Primes
(factors n)find the complete factorization ofn.- Pollard's rho
- SQUFOF
- CFRAC
- ECM
- MPQS
- NFS
- More functions
- Euler's phi
- Discrete logarithm algorithms
- Brute force
- Baby step giant step method
- Pohlig-Hellman
Maintaner Documentation
prime?do not prove it is prime.
Bugs, Shortcomings, etc.
factorsuse ECM factorization that has not been debugged yet.