Ich habe Probleme, mich mit den Problemen PRIME, COMPOSITE, FACTOR und deren Beziehung zur Komplexität auseinanderzusetzen. Ich verstehe, dass PRIME durch den AKS-Primalitätstest als wurde, und ich glaube, dass dies auch für COMPOSITE funktioniert.
Wie für FACTOR,
Nach dem, was ich gelesen habe, scheint es in . Ich sehe, dass es in da ein Zertifikat aus einem Hauptteiler von weniger als . Aber welche Art von Zertifikat kann nachweisen, dass es keinen solchen Primteiler gibt (in der Polynomzeit)?
complexity-theory
factoring
Fequish
quelle
quelle
Antworten:
Ein Zertifikat dafür, dass kein nicht-trivialer Teiler von kleiner als r ist, ist die Faktorisierung von m . Wir können in der Polynomzeit überprüfen, ob alle Faktoren tatsächlich Primzahlen sind (da die Primalität nach dem AKS-Primalitätstest in P angegeben ist ), ob ihr Produkt m ist und ob alle mindestens r sind .m r m m r
quelle
Um Yuvals Antwort zu ergänzen: Der AKS-Primalitätstest wurde im Jahr 2002 entdeckt. Zuvor hatten wir keinen polynomiellen Zeitalgorithmus, um zu überprüfen, ob eine Zahl eine Primzahl ist. Pratt entdeckte jedoch 1975 das, was heute als Pratt-Urkunden bekannt ist, und bewies, dass Primes in NP ist. Wir können diese Primalitätszertifikate von Pratt für die Faktoren in unser Zertifikat aufnehmen, um zu zeigen, dass FACTOR in coNP ist, anstatt den AKS-Algorithmus zu verwenden, um zu überprüfen, ob die Faktoren direkt prim sind.
quelle