1
$\begingroup$

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$).

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 23 '17 at 17:36
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Jul 23 '17 at 19:36
  • $\begingroup$ 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. $\endgroup$ – Tobi Alafin Jul 23 '17 at 19:46
  • 1
    $\begingroup$ "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. $\endgroup$ – Raphael Jul 23 '17 at 21:05
  • $\begingroup$ We only need to check if any of the (prime) numbers from $2$ to $\sqrt{n}$ are a factor of $n$. $\endgroup$ – Tobi Alafin Jul 23 '17 at 21:11
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tobi Alafin Jul 24 '17 at 5:12
  • $\begingroup$ 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. $\endgroup$ – Tobi Alafin Jul 24 '17 at 5:21
  • $\begingroup$ @TobiAlafin, nope, that doesn't help. You still have to do all those gcd's. The way to work it out is to write down a specific algorithm, then analyze its running time. $\endgroup$ – D.W. Jul 24 '17 at 6:04
  • 1
    $\begingroup$ The OP idea in general is exercise 3.44 in Crandall and Pomerance. Using precomputed results gives a practical speedup over standard trial division when using GMP, but it's still trial division. You need to amortize the primorial generation time to achieve real speedup. It reaches limits quickly, so is only useful for use to find small factors (which are common in arbitrary inputs), e.g. the first 10k primes, though you can go larger if you can amortize the primorial. Also see remainder trees which are a similar idea but even faster. $\endgroup$ – DanaJ Jul 24 '17 at 18:20
  • 1
    $\begingroup$ It's a nice pre-test idea to quickly find composites with small factors, but it's not useful as a complete primality test for anything other than tiny inputs. For example, BPSW is deterministic for 64-bit inputs and runs massively faster than doing the gcds, especially as there is no bignum library involved. Once you're past 64-bit, trial division is horrendously slow, even using gcds. Use BLS75 (n-1, n+1, or hybrid), APR-CL, or ECPP. $\endgroup$ – DanaJ Jul 24 '17 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.