Is there a polynomial time algorithm for this decision problem?
-
29-09-2020 - |
Question
Is there a factor in $M$ that is $>$ $1$, but $<$ $M$ that is NOT a factor of $N$?
False Result Example
$N$ = 8
$M$ = 16
1, 2, 4, 8, 16
There is no integer that is NOT a factor of $N$ that is $>$ $1$ but < $M$
True Result Example
$N$ = 2
$M$ = 26
1, 2, 13, 26
There is an integer $13$ which is NOT a factor of $N$ that is > 1 but < $M$
Question
I have found a pseudo-polynomial solution, but is there a polynomial solution for this problem in the length of input?
Solution
This is hard as the integer factoring problem (simply take $N$ to be 2 or a random prime that has no factor in common with $M$). Whether there is a polynomial-time algorithm for factoring is a famous open problem, but it is widely believed that there likely is no such algorithm.