Today I had an insight into an alternative deterministic algorithm for testing the primality of a number. I want to know if this algorithm is useful, and worth pursuing. I'll describe the idea behind the algorithm below:
Let the fastest gcd algorithm we know be $g^*(a, b)$. $g^*$ takes in two numbers and finds their greatest common divisor. To find out if any number $n$ is prime it is sufficient to test if any of the prime numbers from $2$ to $\sqrt{n}$ inclusive is a factor of $n$.
Consider a set of numbers $S$. Let $V_c$ be any subset of $S$ such that $g^*(V_c) = 1$, that is, all $x_i$ in $S$ are mutually prime. Let the set of prime numbers be $P$. Let $h_i$ be the set of all factors of $x_i$.
$$P = \bigcup_{i = 1}^{{\#}S} h_i.$$
So $S$ is a partitioning of $P$ such that all the elements of $S$ are formed from the product of unique elements in $P$, and no element in $P$ is used to form more than one element in $S$. There are several possible configurations of $S$. Let's denote them $S^j$.
Let $P_k$ be the set of all prime numbers from $2$ to $k$. Let $S_k^j$ be an $S$ partitioning of $P$.
Now, my primality test is this:
- Given any number $n$, pick $k: k \ge \sqrt n$ (the closer $k$ is to $\sqrt n$, the better).
- Generate an optimum $S_k^j$.
- for $x_i$ in $S_k^j$
- if $g^*(n, x_i) != 1$
return false
end for- return check
For implementation purposes, I'm thinking of creating a set of $S^j$ with consecutive $x_i$ (consecutive in the sense that the largest prime number used to make $x_i$ is consecutive with the smallest prime number used to make $x_{i+1}$, such that we can easily cut off a portion of $S^j$ to get our $S_k^j$. Depending on circumstances though, we may generate the optimum $S_k^j$ on the spot, though this should only be pursued if the cost of generating it is negligible or guarantees a significant speed up over the alternative of the consecutive table. I think creating a pre-generated $S_k^j$ is useful for this purpose, though I'm not sure if it would slow down the overall algorithm. Alternative tables apart from the consecutive table may also be considered.
An English Explanation
My idea in English is basically this:
To test if a number $n$ is prime, we only need to check if any of the prime numbers from $2$ to $\sqrt{n}$ is a factor of $n$. Using this foundation, I tried to devise a method that is faster at testing primality, than computing $n \mod i$ for all primes between $2$ and $\sqrt{n}$.
If two numbers are mutually prime, then their gcd is $1$. A prime number is mutually prime with every other prime number that is not itself. Imagine I had a number $y_n$. $y_n$ is a product of all the prime numbers from $2$ to $\sqrt{n}$. I can test if $y_n$ is prime, by running $g^*(n, y_n)$, where $g^*()$ is our fastest gcd algorithm.
However, what if instead of just $1$ number, I had a set $S$ of numbers which satisfied the following properties:
1. All the elements of the set are mutually prime with every other element.
1. Each element of the set is a product of some primes between $2 and \sqrt{n}$ (both inclusive). 2. The product of the elements of the set is equal to the product of all the prime numbers from $2$ to $\sqrt{n}$.
It becomes apparent, that I can test if $n$ is prime, by computing $g^*(n, x_i)$ until I get a value that is not equal to $1$ (if all values are equal to $1$, then the number is prime). where $x_i$ is some element in $S$.
It is possible, that my $S$ contains only $y_n$. The idea is to choose $S$ such that we minimise the runtime of the algorithm, and the runtime of generating $S$. (I suggest a table storing $S$, such that a desired subset of $S$ can easily be cut out from it to use to test any prime number. If we keep a lookup table for $S$ (as opposed to generating it), then we can minimise the cost the algorithm incurs when generating $S$. There are other ideas that can be pursued to minimise the cost of generating $S$).
