<commit_before>			Number theory algorithms

*INTRO This chapter describes the algorithms used for computing various number-theoretic functions.
We call "number-theoretic" any function that takes integer arguments,
produces integer values, and is of interest to number theory.

		Euclidean GCD algorithms

*A GCD!binary Euclidean method

The main algorithm for the calculation of the GCD of two integers
is the binary Euclidean algorithm.
It is based on the following identities: $ Gcd(a,b) = Gcd(b,a) $,
$ Gcd(a,b) = Gcd(a-b,b)$, and for odd $b$, $Gcd(2*a,b) = Gcd(a,b)$.
Thus we can produce a sequence of pairs with the same GCD as the original two numbers, and each pair will be at most half the size of the previous pair.
The number of steps is logarithmic in the number of digits in $a$, $b$.
The only operations needed for this algorithm are binary shifts and subtractions (no modular division is necessary).
The low-level function for this is {MathGcd}.

To speed up the calculation when one of the numbers is much larger than another, one could use the property $Gcd(a,b)=Gcd(a,Mod(a,b))$.
This will introduce an additional modular division into the algorithm; this is a slow operation when the numbers are large.

		Prime numbers: the Miller-Rabin test and its improvements

*A primality testing

Small prime numbers
*EVAL "$p<=" : (ToString()Write(FastIsPrime(0))) : "$"
are simply stored in a precomputed table as an array of bits; the bits corresponding to prime numbers are set to 1.
This makes primality testing on small numbers very quick.
This is implemented by the function {FastIsPrime}.

Primality of larger numbers is tested by the function {IsPrime} that uses the
Miller-Rabin algorithm.
*FOOT Initial implementation and documentation was supplied by <NAME>.
This algorithm is deterministic (guaranteed correct within a certain running time) for
"small" numbers $n<3.4*10^13$ and probabilistic
(correct with high probability but not guaranteed) for larger numbers.
In other words, the Miller-Rabin test
could sometimes flag a large number $n$ as prime when in fact $n$ is
composite; but the probability for this to happen can be made extremely
small. The basic reference is [Rabin 1980].
We also implemented some of the improvements suggested in [Davenport 1992].

*A primality testing!Fermat test
*A primality testing!Miller-Rabin algorithm

The idea of the Miller-Rabin algorithm is to improve the Fermat primality test. If $n$ is prime, then for any $x$ we have $Gcd(n,x)=1$. Then by Fermat's "little theorem", $x^(n-1):=Mod(1,n)$. (This is really a simple statement; if $n$ is prime, then $n-1$ nonzero remainders modulo $n$: 1, 2, ..., $n-1$ form a cyclic multiplicative group.) Therefore we pick some "base" integer $x$ and compute $Mod(x^(n-1), n)$; this is a quick computation even if $n$ is large. If this value is not equal to $1$ for some base $x$, then $n$ is definitely not prime.
However, we cannot test <i>every</i> base $x<n$; instead we test only some $x$, so it may happen that we miss the right values of $x$ that would expose the non-primality of $n$.
So Fermat's test sometimes fails, i.e. says that $n$ is a prime when $n$ is in fact not a prime.
Also there are infinitely many integers called "Carmichael numbers" which are not prime but pass the Fermat test for every base.

The Miller-Rabin algorithm improves on this by using the property that for prime $n$ there are no nontrivial square roots of unity in the ring of integers modulo $n$ (this is Lagrange's theorem). In other words, if $x^2:=Mod(1,n)$ for some $x$, then $x$ must be equal to $1$ or $-1$ modulo $n$. (Note that $n-1$ is equal to $-1$ modulo $n$, so $n-1$ is a trivial square root of unity modulo $n$.) In fact, if $n$ is prime, there must be no divisors of $1$ at all, i.e. no numbers $x$ and $y$, not equal to $1$ or $-1$ modulo $n$, such that $x*y:=Mod(1,n)$. If we find such $x$, $y$, then $Gcd(x,n)>1$ or $Gcd(y,n)>1$ and $n$ is not prime.

We can check that $n$ is odd before applying any primality test. (A test $n^2:=Mod(1,24)$ guarantees that $n$ is not divisible by $2$ or $3$.
For large $n$ it is faster to first compute $Mod(n,24)$ rather than $n^2$, or test $n$ directly.)
Then we note that in Fermat's test the number $n-1$ is certainly a composite number because $n-1$ is even. So if we first find the largest power of $2$ in $n-1$ and decompose $n-1=2^r*q$ with $q$ odd, then $x^(n-1):=Mod(a^(2^r),n)$ where $a:=Mod(x^q,n)$. (Here $r>=1$ since $n$ is odd.) In other words, the number $Mod(x^(n-1),n)$ is obtained by repeated squaring of the number $a$.
We get a sequence of $r$ repeated squares: $a$, $a^2$, ..., $a^(2^r)$.
The last element of this sequence must be $1$ if $n$ passes the Fermat test.
(If it does not pass, $n$ is definitely a composite number.)
If $n$ passes the Fermat test, the last-but-one element $a^(2^(r-1))$ of the sequence of squares is a square root of unity modulo $n$.
We can check whether this square root is non-trivial (i.e. not equal to $1$ or $-1$ modulo $n$). If it is non-trivial, then $n$ definitely cannot be a prime. If it is trivial and equal to $1$, we can check the preceding element, and so on. If an element is equal to $-1$, we cannot say anything, i.e. the test passes ($n$ is "probably a prime").
 
This procedure can be summarized like this:
*	1. Find the largest power of $2$ in $n-1$ and an odd number $q$ such that $n-1=2^r*q$.
*	2. Select the "base number" $x<n$. Compute the sequence $a:=Mod(x^q,n)$, $a^2$, $a^4$, ..., $a^(2^r)$ by repeated squaring modulo $n$. This sequence contains at least two elements since $r>=1$.
*	3. If $a=1$ or $a=n-1$, the test passes on the base number $x$. Otherwise, the test passes if at least one of the elements of the sequence is equal to $n-1$ and fails if none of them are equal to $n-1$. 
This simplified procedure works because the first element that is equal to $1$ <i>must</i> be preceded by a $-1$, or else we would find a nontrivial root of unity.

Here is a more formal definition.
An odd integer $n$ is called <i>strongly-probably-prime</i> for base $b$ if
$b^q:=Mod(1,n)$
or
$b^(q*2^i):=Mod(n-1,n)$ for some $i$ such that $0 <= i < r$,<commit_msg>corrected mathematical error in Rabin-Miller description.<commit_after>			Number theory algorithms

*INTRO This chapter describes the algorithms used for computing various number-theoretic functions.
We call "number-theoretic" any function that takes integer arguments,
produces integer values, and is of interest to number theory.

		Euclidean GCD algorithms

*A GCD!binary Euclidean method

The main algorithm for the calculation of the GCD of two integers
is the binary Euclidean algorithm.
It is based on the following identities: $ Gcd(a,b) = Gcd(b,a) $,
$ Gcd(a,b) = Gcd(a-b,b)$, and for odd $b$, $Gcd(2*a,b) = Gcd(a,b)$.
Thus we can produce a sequence of pairs with the same GCD as the original two numbers, and each pair will be at most half the size of the previous pair.
The number of steps is logarithmic in the number of digits in $a$, $b$.
The only operations needed for this algorithm are binary shifts and subtractions (no modular division is necessary).
The low-level function for this is {MathGcd}.

To speed up the calculation when one of the numbers is much larger than another, one could use the property $Gcd(a,b)=Gcd(a,Mod(a,b))$.
This will introduce an additional modular division into the algorithm; this is a slow operation when the numbers are large.

		Prime numbers: the Miller-Rabin test and its improvements

*A primality testing

Small prime numbers
*EVAL "$p<=" : (ToString()Write(FastIsPrime(0))) : "$"
are simply stored in a precomputed table as an array of bits; the bits corresponding to prime numbers are set to 1.
This makes primality testing on small numbers very quick.
This is implemented by the function {FastIsPrime}.

Primality of larger numbers is tested by the function {IsPrime} that uses the
Miller-Rabin algorithm.
*FOOT Initial implementation and documentation was supplied by <NAME>.
This algorithm is deterministic (guaranteed correct within a certain running time) for
"small" numbers $n<3.4*10^13$ and probabilistic
(correct with high probability but not guaranteed) for larger numbers.
In other words, the Miller-Rabin test
could sometimes flag a large number $n$ as prime when in fact $n$ is
composite; but the probability for this to happen can be made extremely
small. The basic reference is [Rabin 1980].
We also implemented some of the improvements suggested in [Davenport 1992].

*A primality testing!Fermat test
*A primality testing!Miller-Rabin algorithm

The idea of the Miller-Rabin algorithm is to improve the Fermat primality test. If $n$ is prime, then for any $x$ we have $Gcd(n,x)=1$. Then by Fermat's "little theorem", $x^(n-1):=Mod(1,n)$. (This is really a simple statement; if $n$ is prime, then $n-1$ nonzero remainders modulo $n$: 1, 2, ..., $n-1$ form a cyclic multiplicative group.) Therefore we pick some "base" integer $x$ and compute $Mod(x^(n-1), n)$; this is a quick computation even if $n$ is large. If this value is not equal to $1$ for some base $x$, then $n$ is definitely not prime.
However, we cannot test <i>every</i> base $x<n$; instead we test only some $x$, so it may happen that we miss the right values of $x$ that would expose the non-primality of $n$.
So Fermat's test sometimes fails, i.e. says that $n$ is a prime when $n$ is in fact not a prime.
Also there are infinitely many integers called "Carmichael numbers" which are not prime but pass the Fermat test for every base.

The Miller-Rabin algorithm improves on this by using the property that for prime $n$ there are no nontrivial square roots of unity in the ring of integers modulo $n$ (this is Lagrange's theorem). In other words, if $x^2:=Mod(1,n)$ for some $x$, then $x$ must be equal to $1$ or $-1$ modulo $n$. (Since $n-1$ is equal to $-1$ modulo $n$, we have $n-1$ as a trivial square root of unity modulo $n$.
Note that even if $n$ is prime there may be nontrivial divisors of $1$, for example, $2*49:=Mod(1,97)$.)

We can check that $n$ is odd before applying any primality test. (A test $n^2:=Mod(1,24)$ guarantees that $n$ is not divisible by $2$ or $3$.
For large $n$ it is faster to first compute $Mod(n,24)$ rather than $n^2$, or test $n$ directly.)
Then we note that in Fermat's test the number $n-1$ is certainly a composite number because $n-1$ is even. So if we first find the largest power of $2$ in $n-1$ and decompose $n-1=2^r*q$ with $q$ odd, then $x^(n-1):=Mod(a^(2^r),n)$ where $a:=Mod(x^q,n)$. (Here $r>=1$ since $n$ is odd.) In other words, the number $Mod(x^(n-1),n)$ is obtained by repeated squaring of the number $a$.
We get a sequence of $r$ repeated squares: $a$, $a^2$, ..., $a^(2^r)$.
The last element of this sequence must be $1$ if $n$ passes the Fermat test.
(If it does not pass, $n$ is definitely a composite number.)
If $n$ passes the Fermat test, the last-but-one element $a^(2^(r-1))$ of the sequence of squares is a square root of unity modulo $n$.
We can check whether this square root is non-trivial (i.e. not equal to $1$ or $-1$ modulo $n$). If it is non-trivial, then $n$ definitely cannot be a prime. If it is trivial and equal to $1$, we can check the preceding element, and so on. If an element is equal to $-1$, we cannot say anything, i.e. the test passes ($n$ is "probably a prime").
 
This procedure can be summarized like this:
*	1. Find the largest power of $2$ in $n-1$ and an odd number $q$ such that $n-1=2^r*q$.
*	2. Select the "base number" $x<n$. Compute the sequence $a:=Mod(x^q,n)$, $a^2$, $a^4$, ..., $a^(2^r)$ by repeated squaring modulo $n$. This sequence contains at least two elements since $r>=1$.
*	3. If $a=1$ or $a=n-1$, the test passes on the base number $x$. Otherwise, the test passes if at least one of the elements of the sequence is equal to $n-1$ and fails if none of them are equal to $n-1$. 
This simplified procedure works because the first element that is equal to $1$ <i>must</i> be preceded by a $-1$, or else we would find a nontrivial root of unity.

Here is a more formal definition.
An odd integer $n$ is called <i>strongly-probably-prime</i> for base $b$ if
$b^q:=Mod(1,n)$
or
$b^(q*2^i):=Mod(n-1,n)$ for some $i$ such that $0 <= i < r$,
{'fraction_non_alphanumeric': 0.10810149302439423, 'fraction_numerical': 0.014440727747409643, 'mean_word_length': 4.274526678141136, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5921982', 'n_tokens_mistral': 3930, 'n_tokens_neox': 3667, 'n_words': 2008}