Existe un polinomio tiempo algoritmo para esta decisión el problema?

Question

Hay un factor en $M$ que es $>$ $1$, pero $<$ $M$ que NO es un factor de $N$?

Resultado Falso Ejemplo

$N$ = 8

$M$ = 16

1, 2, 4, 8, 16

No hay ningún número entero que NO es un factor de $N$ que es $>$ $1$ pero < $M$

Resultado Verdadero Ejemplo

$N$ = 2

$M$ = 26

1, 2, 13, 26

Hay un número entero $13$ que NO es un factor de $N$ que es > 1, pero < $M$

Pregunta

He encontrado un pseudo-polinomial solución, pero existe un polinomio solución para este problema en la longitud de la entrada?

Answer 1

Esto es difícil como el problema del factoraje entero (simplemente toma $ n $ para ser 2 o un primo aleatorio que no tiene factor en común con $ m $ ).Si hay un algoritmo de tiempo polinomial para factorizar es un problema abierto famoso, pero se cree ampliamente que probablemente no haya tal algoritmo.