Proof Review: Integer Factorization is in NP 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&lt;=i&lt;=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?
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.