Wie erhält man die unbekannten Werte

19

Kann mir jemand bei folgendem Problem weiterhelfen?

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

Auf jeden Fall ist es nicht möglich, jede Permutation der K 2K2 Zahlen in der Liste (völlig K 2 !K2! Mögliche Fälle) zu versuchen und dann die modularen Gleichungen mit a i , b jai,bj 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 )modN , ( b i + M )modN } K i = 1{((ai+M)modN,(bi+M)modN}Ki=1 oder ein Tausch ( { ( N - 1 - b i , N - 1 - a i ) } K i = 1 )({(N1bi,N1ai)}Ki=1) ergibt dasselbe Muster von a i - b jmodNaibjmodN ”und ist diese Aussage hilfreich?

ein Gast
quelle
7
Beachten Sie, dass es unmöglich ist, a_i, b_j wiederherzustellen , da die Unterschiede gleich bleiben a i , b jai,bj, wenn Sie allen Zahlen ein konstantes C hinzufügen CC.
Yuval Filmus
1
@Yuval: Dies ist bereits im letzten Satz der Beschreibung enthalten. Ich denke, es wird nur eine Lösung benötigt, da möglicherweise mehrere existieren.
Domotorp
2
@Yuval Entschuldigung, dass Sie nicht darauf hingewiesen haben, dass die a i , b jai,bj auch modular NN . Es gibt also keine unendlichen Lösungen.
ein Gast
@domotorp Ja, es ist in Ordnung, eine der Lösungen zu finden.
ein Gast
1
Vielleicht könnte das OP klarstellen, dass die ein iai , b jbj modulo NN früher im Beitrag genommen werden: vielleicht im Titel oder im ersten Absatz. Erwähnenswert ist auch das Problem mit der Konstanten CCBeide Dinge verwirrten mich, als ich anfing zu lesen.
Juan Bermejo Vega

Antworten:

4

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 K=6N = 251 N=251a i - b j( modN ) aibj(modN)a 1 - b 1 a1b1b 1 = 0 b1=0a 1 a1a 2 - b 1a2b1 5 / 35 = 1 / 7 5/35=1/7a 2a2

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 - aa1,a2,b1a1bjj1aibji=1(aibj)+(a2a1)=a2bji11)(aibj)+(a2a1)33/25133/251aibjaibj(aibj)+(a2a1)(aibj)+(a2a1)i=1i=1b2b2

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 .a1,a2,b1,b2a1,a2,b1,b2b2b2a3a3b3b3aibjaibj(aibj)+(a2a1)(aibj)+(a2a1)(aibj)+(a3a1)(aibj)+(a3a1)aab3,a4,b4,a5,b6,a6,b6b3,a4,b4,a5,b6,a6,b6

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.aibjaibj

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.

Yuval Filmus
quelle
Vielen Dank, und ich werde dieses Backtracking auch codieren, um es verständlicher zu machen. Vielleicht hat der Autor dieses Originalpapiers eine ähnliche Methode angewendet, weil er auch "Backtrack" erwähnte.
ein Gast
Entschuldigung, dass Sie vergessen haben, meinen Kommentar zu Ihrer Antwort zu posten! Ich habe auch die von Ihnen vorgeschlagene Methode implementiert (in C ++). Die Schlussfolgerung ist, dass Ihr Algorithmus ziemlich gut funktioniert und eine der Lösungen dann sehr schnell gefunden werden kann (in weniger als einer Sekunde auf meinem PC). Und dieses Mal kann ich die Backtrack-Prozeduren besser verstehen. Vielen Dank!
ein Gast
Warum kann ich in meinem letzten Kommentar nicht "@Yuval" ?! Entschuldigung, aber ich habe es mehrmals versucht.
ein Gast
Vielleicht können Sie den Code online freigeben, damit andere Leser der Zeitung darauf zugreifen können.
Yuval Filmus
5

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).dd

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 .

Suresh Venkat
quelle
1
Ich denke, dieses Problem ist anders. Bei der Umgehungsproblematik kennen wir alle paarweisen Abstände, hier kennen wir sie nur zwischen zwei Punkten, die sich in verschiedenen Gruppen befinden. Dies scheint zwar weniger Informationen zu sein, kann jedoch zur Lösung des Problems beitragen.
Domotorp
Ah ja. Es ist eine zweigeteilte Grafik. guter Punkt.
Suresh Venkat
Zweiteiliger Graph? So etwas wie. Vielleicht sollte ich das Problem auf diese Weise versuchen, aber ich habe jetzt keinen konkreten Gedankengang.
ein Gast
3

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:a1b1a1b1a1b2a1b2a2b1a2b1a2b2a2b2aabb

(a1b1)(a1b2)=(a2b1)(a2b2)(modN).

(a1b1)(a1b2)=(a2b1)(a2b2)(modN).

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.K2K2

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(K24)(K24)(K2)2(K2)21/N1/N((K24)(K2)2)/N((K24)(K2)2)/N(58905225)/251234(58905225)/251234andere 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.

DW
quelle
@DW: Danke, aber ich frage mich jetzt den nächsten Schritt, nachdem alle möglichen Quartette (insgesamt 225 + 234 = 459) gefunden wurden. Sollte sie nach 3 nicht überlappenden Quartetten suchen und prüfen, ob sie eine mögliche Lösung darstellen können? Wie kann dies effizient erreicht werden? Vielleicht nicht so schwierig, weil es nicht viele Überlappungen geben wird.
ein Gast
@ Gast, gute Frage! Ich kann mich nicht erinnern, was ich damals gedacht habe. Ich erinnere mich, dass ich dachte, ein Ansatz könnte darin bestehen, mit einem Quartett zu beginnen und dann nach allen anderen zu suchen, die es in zwei Unterschieden überlappen (z. B. aus wo ), aber ich nicht wissen, wohin von dort aus zu gehen ist (wie man falsche Positive herausfiltert). a1,aj,b1,b2a1,aj,b1,b2j2j2
DW
3

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{a1,,a6}{a1,,a6}AAaa{a1,,a6}A{a1,,a6}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).BBbb{b1,,b6}B{b1,,b6}BAABB

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äherungAAaaBBbbAA 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.aaAAAAAAAAaa

Aus Symmetriegründen lässt uns im Wesentlichen der gleiche Trick unsere Überapproximation für die verfeinern : eine Überapproximation vorausgesetztbbAA für die und einer Überapproximation für die wird eine neue Überapproximation erzeugt -Näherung für die 's.aaBBbbBBbb

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 .DDD={aibj:1i,j6}D={aibj:1i,j6}AAA,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 mussdDd+B={d+y:yB}Bbd+B{a1,,a6} . 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+BAdDd

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 Differenza1a1b1Da1b1B(a1b1)+Ba1a1b2 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 undDa1a1a2a3, 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.Aaa

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.Ad(d+B)AAAAA

Zusammengefasst lautet der Algorithmus zur Verfeinerung von zu wie folgt:A,BA

  1. Lassen . Dies ist die Vielzahl von Vorschlägen.S=dD(d+B)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 SieSASasa[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 undA,BB . Grundsätzlich kehrt man die obigen Dinge um und dreht ein paar Zeichen um: Beispielsweise sieht man anstelle von .d+Bd+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 werdenb1=0aiDDa . 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 dasab1=0A=Daaa1B=a1Db . 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,Ba1

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.a1,,a6,b1,,b6AB

  1. Errate: Errate für jedes , dass . Mach Folgendes:zDa1=z

    1. Anfängliche : Definieren Sie und .A=DB=zD

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

      • Verfeinern Sie , um eine neue Überapproximation der zu erhalten.A,BBb
      • Verfeinern eine neue über Annäherung zu bekommen der ‚s.A,BAa
      • Sei und .A:=AB:=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,Bz

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={a1,,a6}B={b1,,b6}

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|AA,Bd|B||B|1xaAa(|B|1)×36/251 (im Durchschnitt mit einer Standardabweichung um die Quadratwurzel davon). Wenn , ist die Wahrscheinlichkeit, dass ein falsches|B|36xü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 alsp=0.4|B||B|=30p0.25Ap(|A|6)+6|A|. Zum Beispiel, wenn , dann erwarte ich basierend auf diesen Heuristiken|A|=|B|=36|A|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

DW
quelle
@DW: Vielen Dank für deine lange Antwort und die Mühe, die du gemacht hast, um so viele Wörter zu tippen !!! Entsprechend Ihrer Beschreibung ist Ihr Algorithmus hier ziemlich korrekt. Und ich werde es jetzt codieren, um die Effizienz zu testen.
ein Gast
@DW: Hallo, ich habe deine Beschreibung in C ++ implementiert. Der Algorithmus läuft schnell und der Verfeinerungsschritt macht die Größe der ursprünglichen Sätze reduzieren und . Die Konvergenz scheint jedoch nicht so perfekt zu sein. Tatsächlich sind die endgültigen Größen von und für jede Schätzung von immer noch mehr als 10, wie aus meinem vom Programm ausgegebenen Datensatz hervorgeht. Die häufigste Anzahl vorhandener Elemente, bei denen (und ) durch weitere Wiederholungen der Verfeinerung nicht verbessert werden können, ist 11, aber ich kann kaum eine Zahl unter 10 sehen. Dies hat jedoch das Problem durch Versuchen von jedem lösbar gemacht 6 Elemente ausgewählt ausABzDABAB
einem Gast
@DW: (Fortsetzung) final und für jede Vermutung (obwohl ich den letzten Schritt nicht auf meinem PC implementiert habe). Die Berechnung des Gesamtbetrags wird nach meiner Schätzung etwa betragen . Vielen Dank! ABz220
ein Gast
Entschuldigung, aber mein letzter Kommentar ist zu lang und ich muss ihn in zwei Teile teilen.
ein Gast