# Is this a Fruitful Primality Testing scheme?

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:

1. Given any number $n$, pick $k: k \ge \sqrt n$ (the closer $k$ is to $\sqrt n$, the better).
2. Generate an optimum $S_k^j$.
3. for $x_i$ in $S_k^j$
4. if $g^*(n, x_i) != 1$
return false
end for
5. 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$).

• It's really hard to understand your algorithm. It is likely that if you implement it then it will be very slow and/or won't work correctly, but it's difficult to tell at this stage. – Yuval Filmus Jul 23 '17 at 17:36
• Efficient algorithm run in time which is polylogarithmic in $n$, that is, $O(\log^C n)$ for some constant $C$. It seems that your algorithm will run in time polynomial in $n$, that is, $O(n^c)$ for some constant $c$. – Yuval Filmus Jul 23 '17 at 19:36
• I have edited the question to be as clear as possible. My question is: "Is the below primality testing scheme a fruitful one". Is it worth pursuing. E.g if I came up with a cubic time algorithm for sorting, then it wouldn't be worth pursuing. If the algorithm was superlinear ($n(\log(n))$), then it would be worth pursuing. (I think any polynomial time algorithm $n^c, c: c < 2$ is still an algorithm worth pursuing. That's my question. – Tobi Alafin Jul 23 '17 at 19:46
• "To test if a number n is prime, we only need to check if any of the prime numbers from 2 to $\sqrt{n}$ are prime." -- This sentence doesn't make any sense, and does not invite to read further. – Raphael Jul 23 '17 at 21:05
• We only need to check if any of the (prime) numbers from $2$ to $\sqrt{n}$ are a factor of $n$. – Tobi Alafin Jul 23 '17 at 21:11

No, this won't work -- it's too slow. Let $B$ be the product of all the prime numbers up to $\sqrt{n}$. Then $B$ is roughly $\sqrt{n}^{\sqrt{n}/\log n}$, i.e., exponential in $n$. Consequently, no matter how you form the set $S$, you're going to be working with a set of exponential size. As a result the algorithm will have exponential running time, which is no good.
• What if I precompute $S$? If I precompute $S$, and use $S$ to test for primality, then will it work? I may precompute S up to a list of known primes that gets updated periodically. For any new number $n$ that we suspect is Prime, we first run a probabilistic algorithm. If the probabilistic algorithm supplies reasonable confidence, then we run the deterministic algorithm and test if $n$ is prime. – Tobi Alafin Jul 24 '17 at 5:12
• I'm trying to sacrifice time complexity for space complexity? We may have our $S$ formed from current list of known primes, and for every number $n$ that is suspected to be Prime. (Perform a look up in list of primes if $n \lt$ largest number in list (the look up can be achieved in logarithmic time, using a binary search and the prime counting function to generate an upper bound in which to look for $n$. Else, execute a probabilistic algorithm to test for primality. If the probabilistic algorithm supplies favourable results, perform the deterministic test I described above. – Tobi Alafin Jul 24 '17 at 5:21