Existe um algoritmo de tempo polinomial para este problema de decisão?

Question

Existe um fator $M$ aquilo é $>$ $1$, mas $<$ $M$ isso NÃO é um fator de $N$?

Exemplo de resultado falso

$N$ = 8

$M$ = 16

1, 2, 4, 8, 16

Não existe número inteiro que NÃO seja fator de $N$ aquilo é $>$ $1$ mas < $M$

Exemplo de resultado verdadeiro

$N$ = 2

$M$ = 26

1, 2, 13, 26

Existe um número inteiro $13$ o que NÃO é um fator de $N$ isso é> 1, mas < $M$

Pergunta

Encontrei uma solução pseudopolinomial, mas existe uma solução polinomial para este problema no comprimento da entrada?

Answer 1

Isso é tão difícil quanto o problema de fatoração de números inteiros (basta pegar $N$ ser 2 ou um primo aleatório que não tem nenhum fator em comum com $M$).A existência de um algoritmo de tempo polinomial para fatoração é um famoso problema em aberto, mas acredita-se amplamente que provavelmente não existe tal algoritmo.