2
$\begingroup$

I want to prove that integer factorization is in NP I have a general idea of how to prove this, and was wondering if I could get a sanity check: I'll show it's in NP by using a non-deterministic TM whose longest computational branch runs in polynomial time. The TM will do the following: Given an input (binary) word w of length n on the tape: Non deterministically guess i factors, 1<=i<=n, such that each of the factors is a binary string no longer than n. Multiply all of the factors together (I think this should take O(n^3)) and accept if the final number on the tape is equal to w. Otherwise, reject.

Am I missing anything?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Commented Apr 7, 2017 at 19:27

1 Answer 1

Reset to default
3
$\begingroup$

You are missing something.

If you are given what is supposed to be a factorisation of a number x, it's not enough to show that the product of those numbers is x. You also have to prove that all the numbers in the purported factorisation are primes.

Fortunately there is theorem that for every prime number, there is a polynomial time proof that it is a prime.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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