11.35

The running-time of a decision algorithm is measured against the length of its input, not against the numeric value that the input represents. Writing an integer n in binary needs only [math]\lvert x\rvert=\Theta(\log_2 n)[/math] bits. An algorithm that performs Θ(n) arithmetic steps therefore requires [math]\Theta(n)=\Theta\!\bigl(2^{\lvert x\rvert}\bigr)[/math] time in terms of the input length. Because an exponential function is not polynomial, the simple trial-division procedure for i = 2 to n−1 do
  if n mod i = 0 then return “composite”
return “prime” does not place the compositeness problem in P. The breakthrough of Agrawal, Kayal and Saxena (2002) was to devise an algorithm whose running-time is polynomial in [math]\lvert x\rvert=\log n[/math], not in n itself.

Back to Chapter 11