patternModerate
Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test?
Viewed 0 times
whynumberprimalityeveryinefficientsqrtbetweentestingtestdividing
Problem
In the paper "PRIMES is in P" the following is said (page 1):
Let PRIMES denote the set of all prime numbers. The definition of prime numbers already gives a way of determining if a number $n$ is in PRIMES: try dividing $n$ by every number $m \leq \sqrt{n}$ — if any m divides $n$ then it is composite, otherwise it is prime. This test was known since the time of the ancient Greeks — it is a specialization of the Sieve of Eratosthenes (ca. 240 BC) that generates all primes less then $n$. The test, however, is inefficient: it takes $\Omega (\sqrt{n})$ steps to determine if $n$ is prime. An efficient test should need only a polynomial (in the size of the input = $\lceil \log n \rceil$) number of steps.
Firstly, isn't complexity $\sqrt{n}$ already polynomial?
Secondly, why would complexity $\lceil \log n \rceil$ represent an efficient algorithm? This seems somewhat arbitrary to me.
Let PRIMES denote the set of all prime numbers. The definition of prime numbers already gives a way of determining if a number $n$ is in PRIMES: try dividing $n$ by every number $m \leq \sqrt{n}$ — if any m divides $n$ then it is composite, otherwise it is prime. This test was known since the time of the ancient Greeks — it is a specialization of the Sieve of Eratosthenes (ca. 240 BC) that generates all primes less then $n$. The test, however, is inefficient: it takes $\Omega (\sqrt{n})$ steps to determine if $n$ is prime. An efficient test should need only a polynomial (in the size of the input = $\lceil \log n \rceil$) number of steps.
Firstly, isn't complexity $\sqrt{n}$ already polynomial?
Secondly, why would complexity $\lceil \log n \rceil$ represent an efficient algorithm? This seems somewhat arbitrary to me.
Solution
The complexity is measured as a function of the size of the input.
You don't have here an array of $n$ numbers but a number $n$.
The size of the input is $O(\log n)$ (to store a number $n$ you need $\lfloor log_2(n) + 1 )\rfloor$ bits).
Hence, $O(\sqrt n)$ is not polynomial in the size of the input.
The answer to the second question is a direct consequence. Since the size of the input is logarithmic in $n$, an algorithm with logarithmic time complexity with respect to $n$ (and therefore, polynomial wrt the size of the input) would be efficient.
As an example, consider a number $M$ of size $n$, an algorithm with time complexity $O(log^k M)$ for a constant $k$, corresponds to a polynomial time algorithm (in the size of the input) of time complexity $O(n^k)$.
You don't have here an array of $n$ numbers but a number $n$.
The size of the input is $O(\log n)$ (to store a number $n$ you need $\lfloor log_2(n) + 1 )\rfloor$ bits).
Hence, $O(\sqrt n)$ is not polynomial in the size of the input.
The answer to the second question is a direct consequence. Since the size of the input is logarithmic in $n$, an algorithm with logarithmic time complexity with respect to $n$ (and therefore, polynomial wrt the size of the input) would be efficient.
As an example, consider a number $M$ of size $n$, an algorithm with time complexity $O(log^k M)$ for a constant $k$, corresponds to a polynomial time algorithm (in the size of the input) of time complexity $O(n^k)$.
Context
StackExchange Computer Science Q#88398, answer score: 12
Revisions (0)
No revisions yet.