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$
10
  • 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$ Jul 23, 2017 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$ Jul 23, 2017 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$ Jul 23, 2017 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, 2017 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$ Jul 23, 2017 at 21:11

1 Answer 1

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$
5
  • $\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$ Jul 24, 2017 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$ Jul 24, 2017 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, 2017 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, 2017 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, 2017 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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