Quadratisches Residuum und ganzzahliges Factoring

Ich habe oft gelesen, dass die Entscheidung, ob eine Zahl ein quadratisches Restmodulo ist oder nicht, ein interessantes (und schwieriges) Problem der Zahlentheorie ist (insbesondere wenn keine Primzahl ist). $r$ $n$ $n$

Ich betrachte den folgenden Sonderfall dieses Problems: Sei und zwei verschiedene Primzahlen und . Gegeben zwischen und . Entscheide, ob es ein so dass . $p$ $q$ $n:=pq$ $r$ $1$ $n$ $x\in\mathbb{Z}/n\mathbb{Z}$ $x^2\equiv r\pmod{n}$

Meine Frage ist: Die funktionale Version dieses Problems, dh "Finde ein solches $x$ wie oben", liefert einen randomisierten Algorithmus für das Integer-Factoring. Daher ist es aus praktischen Gründen wie "RSA brechen" sehr interessant. Gibt es ein solches Ergebnis für die Entscheidungsversion dieses Problems? Wenn nicht, was sind typische Probleme, die uns glauben lassen, dass es ein schwieriges Problem ist, die quadratische Residuität zu bestimmen?

Und ist der Sonderfall, den ich betrachte, wirklich ein Sonderfall? Oder kann ich den allgemeinen Fall mit einem beliebigen $n$ mit einem Orakel für das obige Entscheidungsproblem lösen?

cryptography number-theory geboren
quelle

Siehe den Wikipedia-Artikel zum Problem der quadratischen Rückstände . Es gibt nicht viel, aber es wird als separate Annahme der Rechenhärte aufgeführt als das Faktorisierungsproblem und andere. Und obwohl nicht bekannt ist, dass wir faktorisieren, können wir sagen, ob ein Produkt von oder Primzahlen ist. (Es gibt auch Fälle , in denen es einfach Nein zu beantworten, in der Tat , dass der Fall für die Hälfte alles so ist , was hart ist , ist in der anderen Hälfte der Ja - Instanzen von den No - Instanzen zu unterscheiden.)

n

$n$

n

$n$

2

$2$

3

$3$

r

$r$

ShreevatsaR

Antworten:

Tibor Jager und Jörg Schwenk zeigen in The Generic Hardness of Subset Membership Problems unter der Factoring-Annahme, dass sich Factoring bei generischen Ringalgorithmen auf die Unterscheidung quadratischer Reste von Zahlen mit Jacobi-Symbol 1 reduziert . Dies sind Algorithmen, deren einzige "API" für ganze Zahlen Ringoperationen (Addition, Multiplikation, Subtraktion, Division), Gleichheitsvergleiche und das Erzeugen eines zufälligen Elements sind. Sie zeigen auch, dass das Jacobi-Symbol, das in Polynomzeit effizient berechnet werden kann, keinen effizienten generischen Ringalgorithmus hat. Ihr Ergebnis beantwortet Ihre Frage also nicht, außer dass die Antwort nicht bekannt ist.

Yuval Filmus
quelle