Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Your title doesn't match your question. –  Chris Eagle Oct 8 '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 8 '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 8 '12 at 20:24
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
    
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 8 '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 8 '12 at 21:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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