1
$\begingroup$

Let Fact be the following decision problem. Given two natural numbers $k \le n$ the machine accepts if and only if $n$ has a non-trivial divisor that is less than or equal to $k$. Prove that if Fact $\in$ P then there is an algorithm that given $n$, it produces its decomposition into prime factors in polynomial time in the length of $n$.


I have tried to create this algorithm as follows: Given $n\in\mathbb{N}$, if $\mathrm{Fact}(2,n)=1$ then $2\mid n$, in which case we take $n_1=\frac{n}{2}$, if $\mathrm{Fact}(2,n)=0$ then we see what happens with $\mathrm{Fact}(3,n)$ and we continue like this, my problem is that this algorithm is done in a time $O(2^n)$ which is not polynomial and all the algorithms that occur to me end in this problem is it possible to do this in polynomial time?

$\endgroup$
1
$\begingroup$

Use binary search to find the smallest factor, divide and repeat.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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