C'è un algoritmo di tempo polinomiale per questo problema di decisione?

Question

C'è un fattore in $ M $ che è $> $ $ 1 $ , ma $ <$ $ m $ Non è un fattore di $ N $ ?

False Risultato Esempio

$ n $ = 8

$ m $ = 16

1, 2, 4, 8, 16

Non c'è numero intero che non è un fattore di $ N $ che è $> $ < Span Class="Math-Container"> $ 1 $ ma << span class="math-contenitore"> $ m $

Esempio di risultato del vero risultato

$ N $ = 2

$ m $ = 26

1, 2, 13, 26

C'è un numero intero $ 13 $ che non è un fattore di $ N $ che è> 1 ma << span class="container di matematica"> $ m $

domanda

Ho trovato una soluzione pseudo-polinomiale, ma c'è una soluzione polinomiale per questo problema nella lunghezza dell'input?

Answer 1

Questo è difficile come il problema di factoring intero (basta prendere $ N $ per essere 2 o un primo casuale che non ha fattore in comune con $ m $ ).Se c'è un algoritmo polinomiale per il factoring è un famoso problema aperto, ma è ampiamente creduto che non ci sia un algoritmo del genere.