2
$\begingroup$

INPUT: an integer $n$ and a integer $d$
QUESTION: does $n$ have a prime factor less than $d$?

Does a polynomial time algorithm exist that can tell whether or not $n$ has a prime factor $< d$?

Would iterating through all possible primes $< d$ take too long?

  • 2
    Takkun: you are mistaken. The most straightforward characterization of NP is as polynomially _checkable_ problems, roughly: 'if we are given a purported solution for this problem, can we in fact verify that it is a solution in polynomial time?' Note that this then allows you to _guess_ a potential solution (the 'N', Nondeterministic) and then _check_ it in polynomial time (the 'P', Polynomial).2012-10-08

1 Answers 1

4

Iterating through all possible primes $\lt d$ would in fact take too long; assuming that $n$ and $d$ are both given in binary and that $d$ is comparable to $n$, then it would take time exponential in the size of your input. But you don't have to iterate through all possible primes; instead, you can guess a number $k$ less than $d$ and then check whether or not $k$ is a factor of $n$. (Can you see why you don't need to check whether $k$ is prime or not?)

  • 1
    @Takkun Exactly; and moreso, that factor must be less than the number itself - so even if $k$ isn't prime, you've established that $n$ has some prime factor $p\leq k\lt d$. (Note that this means you don't necessarily know what the prime factor _is_ - you're answering a yes-no question, not finding a value!)2012-10-08