Wie erhält man die unbekannten Werte

Kann mir jemand bei folgendem Problem weiterhelfen?

Ich möchte einige Werte $a_i,b_j$ (mod $N$ ) finden, wobei $i=1,2,…,K, j=1,2,…,K$ (zum Beispiel $K=6$ ), wenn eine Liste von $K^2$ Werten gegeben ist, die entsprechen den Differenzen $a_i-b_j\pmod N$ (zum Beispiel $N=251$ ), ohne die konkrete entsprechende Beziehung zu kennen. Da die Werte $a_i,b_j\pmod N$ angesichts der Differenzen a_i-b_j \ pmod N nicht eindeutig definiert sind $a_i-b_j\pmod N$, suchen wir nach einer gültigen Zuordnung von Werten.

Auf jeden Fall ist es nicht möglich, jede Permutation der $K^2$ Zahlen in der Liste (völlig $K^2!$ Mögliche Fälle) zu versuchen und dann die modularen Gleichungen mit $a_i,b_j$ als Variablen zu lösen.

Tatsächlich tritt dieses Problem in einem Artikel über die Kryptoanalyse zu einer frühen Version des NTRU-Signaturschemas auf ( http://eprint.iacr.org/2001/005 ). Der Autor schrieb jedoch nur einen Satz „Ein einfacher Backtrack-Algorithmus findet eine Lösung…“ (in Abschnitt 3.3). Kann jemand weitere Erklärungen geben? Darüber hinaus erwähnte der Autor, dass „jede kreisförmige Verschiebung $\{((a_i+M)\mod N,(b_i+M)\mod N\}_{i=1}^K$ oder ein Tausch $(\{(N-1-b_i,N-1-a_i)\}_{i=1}^K)$ ergibt dasselbe Muster von $a_i-b_j\mod N$ ”und ist diese Aussage hilfreich?

Hier ist ein Vorschlag für und . Wir erhalten eine Liste . Beginnen Sie, indem Sie einen von ihnen ohne Verlust der Allgemeinheit . Ohne Verlust der Allgemeinheit ist und wir erhalten den Wert von . Nehmen Sie nun eine andere und hoffen Sie, dass sie die Form (dies geschieht mit einer Wahrscheinlichkeit von ), und leiten Sie .$K = 6$$N = 251$$a_i - b_j \pmod{N}$$a_1-b_1$$b_1=0$$a_1$$a_2-b_1$$5/35 = 1/7$$a_2$

Zu diesem Zeitpunkt kennen wir . Unser nächstes Ziel ist es, nach für zu suchen . Für jeden Kandidaten sollte auch auf der Liste stehen , wenn ist . Wenn , dann ist die Wahrscheinlichkeit, dass ebenfalls auf der Liste ist, ungefähr . Wenn wir also einen Kandidaten für den ebenfalls auf der Liste steht, dann ist wahrscheinlich . Auf diese Weise können wir mit einiger Sicherheit wiederherstellen .a 1 , a 2 , b 1 a 1 - b j j ≠ 1 a i - b j i = 1 ( a i - b j ) + ( a 2 - a 1 ) = ein 2 - b j i ≠ 1 ( a i - b j ) + ( a 2 - $a_1,a_2,b_1$$a_1-b_j$$j \neq 1$$a_i-b_j$$i=1$$(a_i-b_j)+(a_2-a_1)=a_2-b_j$$i \neq 1$$(a_i-b_j)+(a_2-a_1)$$33/251$$a_i-b_j$$(a_i-b_j)+(a_2-a_1)$$i=1$$b_2$

Zu diesem Zeitpunkt kennen wir . Genauso wie wir wiederhergestellt haben , können wir mit hinreichender Sicherheit wiederherstellen . Wir können dann indem nach einem Kandidaten suchen, für den und beide auf der Liste stehen. Da wir mehr s haben, sinkt unsere Ausfallwahrscheinlichkeit merklich. Wir fahren fort und finden .$a_1,a_2,b_1,b_2$$b_2$$a_3$$b_3$$a_i-b_j$$(a_i-b_j)+(a_2-a_1)$$(a_i-b_j)+(a_3-a_1)$$a$$b_3,a_4,b_4,a_5,b_6,a_6,b_6$

Zu irgendeinem Zeitpunkt in diesem Algorithmus haben wir möglicherweise etwas Falsches erraten, und dies wird schließlich zu einem Widerspruch führen (sagen wir, irgendwann gibt es keinen guten Kandidaten ). Wir ziehen uns dann zurück und versuchen eine andere Möglichkeit; Wenn wir alle Möglichkeiten ausschöpfen, kehren wir zurück und versuchen eine andere Möglichkeit (für eine andere Stufe des Algorithmus). und so weiter.$a_i-b_j$

Es ist eine gute Übung, diesen Algorithmus tatsächlich zu programmieren - wahrscheinlich ist dies der einzige Weg, um zu verstehen, wie das Backtracking korrekt implementiert wird. Nur so lässt sich auch feststellen, ob dieser Algorithmus in der Praxis funktioniert.

Update : Die folgende Beschreibung bezieht sich auf ein anderes Problem (bei dem alle paarweisen Abstände in einem Satz vorhanden sind und nicht paarweise Abstände zwischen zwei unterschiedlichen Sätzen). Ich lasse es trotzdem, da es eng verwandt ist.

Dieses Problem wird als Beltway-Problem bezeichnet und ist ein Spezialfall des allgemeinen Torus-Einbettungsproblems. Es hängt auch eng mit dem Turnpike-Problem zusammen, bei dem die Entfernungsunterschiede absolut sind (nicht modulo irgendeine Zahl).$d$

Es ist nicht bekannt, ob das Beltway-Problem einen Poly-Time-Algorithmus zulässt. Es gibt verschiedene Pseudo-Poly-Time-Algorithmen für verwandte Fragen. Die beste Referenz (leider eine alte) ist das Papier von Lemke, Skiena und Smith .

Hier ist eine Beobachtung, von der ich denke, dass sie Ihnen Halt gibt, möglicherweise genug, um das Problem zu lösen.

Angenommen, wir haben vier Differenzen , , , , die sich als paarweise Differenzen zwischen zwei und zwei . Nennen Sie das ein Quartett der Unterschiede. Beachten Sie, dass wir eine nicht triviale Beziehung haben:$a_1-b_1$$a_1-b_2$$a_2-b_1$$a_2-b_2$$a$$b$

Sie können versuchen, diese Beziehung zu verwenden, um potenzielle Quartette aus der Liste von zu identifizieren . Wählen Sie beispielsweise vier Unterschiede aus der Liste aus. wenn sie die obige Beziehung nicht erfüllen, dann entstehen sie definitiv nicht aus einer Quartettstruktur; Wenn sie die Beziehung erfüllen, können sie aus einem Quartett stammen.$K^2$

Es gibt viele Möglichkeiten, wie Sie die Dinge von hier aus angehen können, aber ich vermute, dass dies ausreichen wird.

Ich vermute besonders, dass das Problem für Ihre Beispielparametereinstellungen ziemlich einfach sein wird, da der obige Test zum Erkennen eines Quartetts wahrscheinlich nicht zu viele Fehlalarme hat. Unsere aller Möglichkeiten zur Auswahl von 4 Unterschieden aus der Liste sind Quartette (die alle die Beziehung erfüllen) und der Rest sind Nicht-Quartette (die erfüllen) die Beziehung mit Wahrscheinlichkeit , heuristisch). Daher erwarten wir ungefähr falsch positive Ergebnisse, dh 4-Tupel, die den Test bestehen, obwohl sie keine Quartette sind. Für Ihre Parameter bedeutet dies, dass wir 225 Quartette und${K^2 \choose 4}$${K \choose 2}^2$$1/N$$({K^2 \choose 4}-{K \choose 2}^2)/N$$(58905-225)/251 \approx 234$andere falsch positive Ergebnisse; So ist etwa die Hälfte der 4-Tupel, die den Test bestehen, tatsächlich ein Quartett. Dies bedeutet, dass der obige Test eine ziemlich gute Möglichkeit ist, Quartette zu erkennen. Sobald Sie Quartette erkennen können, können Sie wirklich in die Stadt gehen, um die Struktur der Liste der Unterschiede wiederherzustellen.

Hier ist ein anderer Ansatz, der darauf basiert, iterativ Zahlen zu finden, die nicht unter . Nennen Sie eine Menge eine Über-Approximation der 's, wenn wir das wissen$\{a_1,\dots,a_6\}$$A$$a$$\{a_1,\dots,a_6\} \subseteq A$ . In ähnlicher Weise ist ein overapproximation der ‚s , wenn wir wissen , dass . Offensichtlich ist , desto kleiner ist, desto nützlicher diese Über Annäherung ist, und das gleiche gilt für . Mein Ansatz basiert auf der iterativen Verfeinerung dieser Überapproximationen, dh der iterativen Verkleinerung dieser Mengen (da wir immer mehr Werte als unmöglich ausschließen).$B$$b$$\{b_1,\dots,b_6\} \subseteq B$$A$$B$

Der Kern dieses Ansatzes ist ein Verfahren zur Verfeinerung : Da eine über Annäherung für die ‚s und eine über Annäherung für die ‘ s, findet eine neue über Annäherung$A$$a$$B$$b$$A^*$ für die ‚s , so dass . Insbesondere normalerweise wird kleiner sein als , so dass dies läßt uns die über Näherung für die Verfeinerung ‚s.$a$$A^* \subsetneq A$$A^*$$A$$a$

Aus Symmetriegründen lässt uns im Wesentlichen der gleiche Trick unsere Überapproximation für die verfeinern : eine Überapproximation vorausgesetzt$b$$A$ für die und einer Überapproximation für die wird eine neue Überapproximation erzeugt -Näherung für die 's.$a$$B$$b$$B^*$$b$

Lassen Sie mich also sagen, wie Verfeinerungen vorgenommen werden, und dann werde ich alles zusammensetzen, um einen vollständigen Algorithmus für dieses Problem zu erhalten. Im Folgenden sei die Mehrfachmenge von Differenzen, dh ; wir konzentrieren sich auf eine raffinierte Über Annäherung zu finden , gegeben .$D$$D=\{a_i-b_j:1 \le i,j \le 6\}$$A^*$$A,B$

Berechnen einer Verfeinerung Betrachten wir einen einzigen Unterschied . Betrachten Sie die Menge . Basierend auf unserem Wissen, dass eine Über-Approximation der , wissen wir, dass mindestens ein Element von ein Element von sein muss$d \in D$$d+B=\{d+y : y \in B\}$$B$$b$$d+B$$\{a_1,\dots,a_6\}$ . Daher können wir jedes der Elemente in als "Vorschlag" für eine Zahl behandeln, die möglicherweise in . Lassen Sie uns also alle Differenzen und für jede identifizieren, welche Zahlen von "vorgeschlagen" werden .$d+B$$A$$d \in D$$d$

Jetzt werde ich feststellen, dass die Zahl während dieses Vorgangs mit Sicherheit mindestens sechsmal vorgeschlagen wird. Warum? Da die Differenz in ist , und wenn wir sie verarbeiten, wird eine der Zahlen, es schlägt vor (da wir , dass garantiert sind , wird sicherlich umfassen ). Ebenso die Differenz$a_1$$a_1-b_1$$D$$a_1$$b_1 \in B$$(a_1-b_1)+B$$a_1$$a_1-b_2$ irgendwo in und es wird veranlasst, dass erneut vorgeschlagen wird. Auf diese Weise sehen wir, dass der korrekte Wert von mindestens sechsmal vorgeschlagen wird. Gleiches gilt für und$D$$a_1$$a_1$$a_2$$a_3$, und so weiter.

Also sei die Menge von Zahlen , die mindestens sechsmal vorgeschlagen wurden. Dies ist sicher eine Überbewertung der 's, wie aus den obigen Kommentaren hervorgeht.$A^*$$a^*$$a$

Als Optimierung können wir alle Vorschläge herausfiltern, die in sofort vorhanden sind. Mit anderen Worten, wir können die Differenz so behandeln, als würden alle Werte . Dies stellt sicher, dass wir . Wir hoffen, dass genau kleiner ist als ; Keine Garantie, aber wenn alles gut geht, wird es vielleicht sein.$A$$d$$(d+B)\cap A$$A^* \subseteq A$$A^*$$A$

Zusammengefasst lautet der Algorithmus zur Verfeinerung von zu wie folgt:$A,B$$A^*$

1. Lassen . Dies ist die Vielzahl von Vorschlägen.$S = \cup_{d \in D} (d+B)\cap A$

2. Zählen Sie, wie oft jeder Wert in erscheint . Sei die Menge von Werten, die in mindestens sechsmal vorkommen . (Dies kann effizient implementiert werden, indem zunächst ein Array von 251 erstellt wird, anfangs alle null, und jedes Mal, wenn die Zahl vorgeschlagen wird, erhöhen Sie$S$$A^*$$S$$a$$s$$a[s]$ , am Ende Sie fegen durch Suche nach Elementen , deren Wert 6 oder größer)$a$

Eine ähnliche Methode kann erstellt werden, um zu verfeinern und$A,B$$B^*$ . Grundsätzlich kehrt man die obigen Dinge um und dreht ein paar Zeichen um: Beispielsweise sieht man anstelle von .$d+B$$-d+A$

Wie man eine anfängliche Über-Approximation berechnet. Um unsere anfängliche Über-Approximation zu erhalten, besteht eine Idee darin, (wlog) anzunehmen, dass . Daraus folgt, dass jeder Wert irgendwo zwischen , daher kann die Liste der Differenzen als unsere anfängliche Über-Approximation für das verwendet werden$b_1=0$$a_i$$D$$D$$a$ . Leider gibt uns dies keine sehr nützliche Überapproximation für die .$b$

Ein besserer Ansatz ist es, zusätzlich den Wert eines der zu erraten . Mit anderen Worten, wir nehmen (wlog) an, dass , und verwenden als unsere anfängliche Über-Approximation der . Dann raten wir, welcher dieser 36 Werte tatsächlich einer der , sagen wir . Das ergibt dann eine Überapproximation für das$a$$b_1=0$$A=D$$a$$a$$a_1$$B=a_1-D$$b$ . Wir verwenden diese anfängliche Über-Approximation , verfeinern sie dann iterativ bis zur Konvergenz und testen, ob das Ergebnis korrekt ist. Wir wiederholen bis zu 36 Mal mit 36 ​​verschiedenen Annahmen bei (im Durchschnitt sollten 6 Annahmen ausreichen), bis wir eine finden, die funktioniert.$A,B$$a_1$

Ein vollständiger Algorithmus. Jetzt können wir einen vollständigen Algorithmus haben, um . Grundsätzlich leiten wir eine anfängliche Über-Approximation für und und verfeinern sie dann iterativ.$a_1,\dots,a_6,b_1,\dots,b_6$$A$$B$

1. Errate: Errate für jedes , dass . Mach Folgendes:$z \in D$$a_1=z$

   1. Anfängliche : Definieren Sie und .$A=D$$B=z-D$

   2. Iterative Verfeinerung: Wenden Sie wiederholt Folgendes bis zur Konvergenz an:

      • Verfeinern Sie , um eine neue Überapproximation der zu erhalten.$A,B$$B^*$$b$
      • Verfeinern eine neue über Annäherung zu bekommen der ‚s.$A,B^*$$A^*$$a$
      • Sei und .$A:= A^*$$B:= B^*$

   3. Auf Erfolg prüfen : Wenn die resultierenden Mengen jeweils die Größe 6 haben, prüfen Sie, ob sie eine gültige Lösung für das Problem darstellen. Wenn ja, hör auf. Wenn nicht, fahren Sie mit der Schleife über Kandidatenwerte von .$A,B$$z$

Analyse. Ob das funktioniert? Konvergiert es irgendwann auf und , oder bleibt es , ohne das Problem vollständig zu lösen? Der beste Weg, dies herauszufinden, ist wahrscheinlich, es zu testen. Aber für Ihre Parameter, ja, ich gehe davon aus, dass es effektiv sein wird.$A=\{a_1,\dots,a_6\}$$B=\{b_1,\dots,b_6\}$

Wenn wir Methode # 1 verwenden, solangesind nicht zu groß, heuristisch erwarte ich, dass die größen der sets monoton schrumpfen. Ziehen Sie in Betracht, von abzuleiten . Jeder Unterschied legtWerte; einer von ihnen ist korrekt, und der andere kann (heuristisch) als Zufallszahl behandelt werden. Wenn eine Zahl ist, die nicht unter den , wie groß ist die Wahrscheinlichkeit, dass sie die Filterung überlebt und zu hinzugefügt wird ? Nun ja, wir erwarten vorgeschlagen werden über$|A|,|B|$$A^*$$A,B$$d$$|B|$$|B|-1$$x$$a$$A^*$$a$$(|B|-1) \times 36/251$ (im Durchschnitt mit einer Standardabweichung um die Quadratwurzel davon). Wenn , ist die Wahrscheinlichkeit, dass ein falsches$|B|\le 36$$x$überlebt, sollte die Filterung bei etwa (unter Verwendung der normalen Approximation für das Binomial mit Kontinuitätskorrektur). (Die Wahrscheinlichkeit ist kleiner, wenn kleiner ist; z. B. für erwarte ich .) Ich erwarte, dass die Größe von ungefähr , was die Überapproximation streng verbessern wird, da sie streng kleiner als$p=0.4$$|B|$$|B|=30$$p\approx 0.25$$A^*$$p (|A|-6) + 6$$|A|$. Zum Beispiel, wenn , dann erwarte ich basierend auf diesen Heuristiken$|A|=|B|=36$$|A^*|\approx 18$ , was eine große Verbesserung gegenüber.$|A|$

Daher gehe ich davon aus, dass die Laufzeit sehr schnell sein wird. Ich erwarte, dass ungefähr 3-5 Iterationen der Verfeinerung für die Konvergenz ausreichen, und ungefähr 6 Vermutungen bei sollten wahrscheinlich ausreichen. Jede Verfeinerungsoperation umfasst möglicherweise einige tausend Speicherlesevorgänge / -schreibvorgänge, und wir tun dies möglicherweise 20 bis 30 Mal. Daher erwarte ich, dass dies für die von Ihnen angegebenen Parameter sehr schnell geht. Die einzige Möglichkeit, dies herauszufinden, besteht darin, es zu versuchen und zu prüfen, ob es gut funktioniert oder nicht.$z$