2

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?

Takkun
  • 433
  • 1
    Your title doesn't match your question. – Chris Eagle Oct 08 '12 at 20:19
  • Am I mistaken that in order to prove a problem is in NP the following must be true? "Given some information C, you can create an algorithm V that will verify for every input whether X is in your domain or not. V must run in polynomial time." – Takkun Oct 08 '12 at 20:22
  • 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). – Steven Stadnicki Oct 08 '12 at 20:24

1 Answers1

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?)

Steven Stadnicki
  • 51,746
  • Is it true that every non-prime number has a prime factor? (Addressing your question of why you don't have to check for primality of k) – Takkun Oct 08 '12 at 20:54
  • 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!) – Steven Stadnicki Oct 08 '12 at 21:01