Gibt es einen Polynomzeitalgorithmus für dieses Entscheidungsproblem?

Question

Gibt es einen Faktor in $ M $ das ist $> $ $ 1 $ , aber $ <$ $ M $ Das ist nicht ein Faktor von $ n $ ?

falsches Ergebnisbeispiel

$ n $ = 8

$ M $ = 16

1, 2, 4, 8, 16

Es gibt keine Ganzzahl, die nicht ein Faktor von $ N $ ist, der $> $ $ 1 $ aber << span class="Math-Container"> $ M $

True-Ergebnisbeispiel

$ N $ = 2

$ M $ = 26

1, 2, 13, 26

Es gibt eine Ganzzahl $ 13 $ , die nicht ein Faktor von $ N $ das ist> 1 aber << span class="Math-Container"> $ M $

Frage

Ich habe eine Pseudo-Polynom-Lösung gefunden, gibt es jedoch eine Polynomlösung für dieses Problem in der Länge der Eingabe?

Answer 1

Dies ist schwerwiegend wie das Integer-Factoring-Problem (einfach $ N $ auf 2 oder eine zufällige Prime, die keinen Faktor mit $ M $ ).Ob es einen Polynom-Zeit-Algorithmus zum Factoring gibt, ist ein berühmtes offenes Problem, aber es wird weit verbreitet, dass es wahrscheinlich keinen solchen Algorithmus gibt.