Jak uzyskać nieznane wartości

Czy ktoś może mi pomóc z następującym problemem?

Chcę znaleźć niektóre wartości $a_i,b_j$ (mod $N$ ) gdzie $i=1,2,…,K, j=1,2,…,K$ (na przykład $K=6$ ), biorąc pod uwagę listę wartości $K^2$ , które odpowiadają różnicom $a_i-b_j\pmod N$ (na przykład $N=251$ ), nie znając konkretnej odpowiedniej relacji. Ponieważ wartości $a_i,b_j\pmod N$ nie są jednoznacznie zdefiniowane, biorąc pod uwagę różnice $a_i-b_j\pmod N$ , szukamy jakiegokolwiek prawidłowego przypisania wartości.

Zdecydowanie wypróbowanie każdej permutacji liczb $K^2$ na liście (całkowicie możliwe przypadki $K^2!$ ), A następnie rozwiązywanie równań modułowych za pomocą $a_i,b_j$ ponieważ zmienne są niemożliwe.

W rzeczywistości problem ten pojawia się w artykule na temat kryptoanalizy we wczesnej wersji schematu podpisu NTRU ( http://eprint.iacr.org/2001/005 ). Jednak autor napisał tylko jedno zdanie „Prosty algorytm cofania się znajduje jedno rozwiązanie…” (w rozdziale 3.3), a zatem czy ktoś może podać więcej wyjaśnień? Co więcej, autor wspomniał również, że „każde przesunięcie kołowe $\{((a_i+M)\mod N,(b_i+M)\mod N\}_{i=1}^K$ lub zamiana $(\{(N-1-b_i,N-1-a_i)\}_{i=1}^K)$ daje taki sam wzorzec jak $a_i-b_j\mod N$ ”i czy to stwierdzenie jest pomocne?

Oto sugestia dla i . Otrzymujemy listę . Zacznij od wzięcia jednego z nich, bez utraty ogólności . Bez utraty ogólności , a otrzymujemy wartość . Teraz weź inny i miej nadzieję, że ma on postać (dzieje się to z prawdopodobieństwem ), i wywnioskuj .$K = 6$$N = 251$a i - b j( modN ) 1 - b 1 b 1 = 0 1 2 - b 1 5 / 35 = 1 / 7 $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$

Na tym etapie wiemy . Naszym kolejnym celem jest poszukiwanie dla . Dla każdego kandydata , jeśli to również powinno być na liście. Jeśli , to prawdopodobieństwo, że jest również na liście, wynosi około . Jeśli więc znajdziemy kandydata dla którego również znajduje się na liście, to prawdopodobnie . W ten sposób możemy odzyskać z pewną pewnością.$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$

Na tym etapie wiemy . W ten sam sposób, w jaki odzyskaliśmy , możemy odzyskać z rozsądną pewnością. Następnie możemy odzyskać , szukając kandydata dla którego i znajdują się na liście. Ponieważ mamy więcej s, nasza prawdopodobieństwo awarii idzie znacznie w dół. Kontynuujemy i znajdujemy .$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$

W dowolnym momencie tego algorytmu moglibyśmy zgadnąć coś złego, co ostatecznie doprowadzi do sprzeczności (powiedzmy, że w pewnym momencie nie ma dobrego kandydata ). Następnie cofamy się i próbujemy innej możliwości; jeśli wyczerpiemy wszystkie możliwości, cofniemy się ponownie i spróbujemy innej możliwości (dla innego etapu algorytmu); i tak dalej.$a_i-b_j$

Dobrym ćwiczeniem jest zaprogramowanie tego algorytmu - to prawdopodobnie jedyny sposób, aby zrozumieć, jak poprawnie zaimplementować cofanie. To także jedyny sposób, aby stwierdzić, czy ten algorytm działa w praktyce.

Aktualizacja : Poniższy opis dotyczy innego problemu (w którym wszystkie pary są parami w zestawie, a nie parami odległości między dwoma odrębnymi zestawami). Zrezygnuję z tego, ponieważ jest to ściśle powiązane.

Problem ten nazywa się problemem obwodnicy i jest szczególnym przypadkiem ogólnego problemu osadzania się -torus. Jest to również ściśle związane z problemem rogatki, w którym różnice odległości są absolutne (nie modulo pewnej liczby).$d$

Nie wiadomo, czy problem z obwodnicą dopuszcza algorytm wieloczasowy. Istnieją różne algorytmy pseudo-poli-czasowe dla powiązanych pytań. Najlepszym odniesieniem (niestety starym) jest artykuł Lemke, Skieny i Smitha .

Oto spostrzeżenie, które moim zdaniem stanowi przyczółek, być może wystarczający do rozwiązania problemu.

Załóżmy, że mamy cztery różnice , , , które powstają jako pary różnic między dwoma a i . Nazwij to kwartetem różnic. Zauważ, że mamy nietrywialny związek:$a_1-b_1$$a_1-b_2$$a_2-b_1$$a_2-b_2$$a$$b$

Możesz spróbować wykorzystać ten związek do zidentyfikowania potencjalnych kwartetów z listy . Na przykład wybierz cztery różnice z listy; jeśli nie spełniają powyższego związku, to na pewno nie powstają ze struktury kwartetu; jeśli spełnią relację, mogą powstać z kwartetu.$K^2$

Istnieje wiele sposobów na zabranie rzeczy stąd, ale podejrzewam, że to wystarczy.

Podejrzewam szczególnie, że dla przykładowych ustawień parametrów problem będzie dość łatwy, ponieważ powyższy test rozpoznawania kwartetu prawdopodobnie nie będzie miał zbyt wielu fałszywych trafień. Nasz ze wszystkich sposobów wyboru 4 różnic z listy, będą kwartety (które wszystkie spełnią relację), a reszta to kwartety niekompetentne (które spełniają związek z prawdopodobieństwem , heurystycznie). Dlatego spodziewamy się zobaczyć o fałszywych trafień, tj. 4-krotkach, które przejdą test, nawet jeśli nie są kwartetami. Dla twoich parametrów oznacza to, że mamy 225 kwartetów i${K^2 \choose 4}$${K \choose 2}^2$$1/N$$({K^2 \choose 4}-{K \choose 2}^2)/N$$(58905-225)/251 \approx 234$inne fałszywe alarmy; więc około połowa 4-krotek, które przejdą test, to tak naprawdę kwartety. Oznacza to, że powyższy test jest całkiem dobrym sposobem na rozpoznanie kwartetów. Kiedy już rozpoznasz kwartety, naprawdę możesz udać się do miasta po odzyskaniu struktury listy różnic.

Oto inne podejście, oparte na iteracyjnym wyszukiwaniu liczb, które nie mogą pojawić się w . Nazywamy zbiorem nadmierne przybliżenie „s, jeśli wiemy, że . Podobnie, jest overapproximation z „s, jeśli wiemy, że . Oczywiście mniejszy$\{a_1,\dots,a_6\}$$A$$a$$\{a_1,\dots,a_6\} \subseteq A$$B$$b$$\{b_1,\dots,b_6\} \subseteq B$$A$ , tym bardziej użyteczne to nadmierne przybliżenie jest i to samo dotyczy . Moje podejście opiera się na iteracyjnym udoskonalaniu tych nadmiernych przybliżeń, tj. Iteracyjnym zmniejszaniu rozmiaru tych zbiorów (ponieważ wykluczamy coraz więcej wartości jako niemożliwych).$B$

Zasadniczą cechą tego rozwiązania jest sposób udoskonalenia : podany nadmierne przybliżenie dla „S nadmierne przybliżenie do ” s, znalezienie nowego nadmiernej aproksymacji do jest taki, że . W szczególności normalnie będzie mniejsza niż , więc to pozwala nam udoskonalić nadmiernej Przybliżony „s.$A$$a$$B$$b$$A^*$$a$$A^* \subsetneq A$$A^*$$A$$a$

Przez symetrii zasadniczo taka sama sztuczka pozwoli nam udoskonalić nasze nadmiernej Przybliżony „s: podany nadmierne zbliżanie dla ” ów i nadmierne zbliżanie do „s, będzie produkować nowy ponad - przybliżenie dla .$b$$A$$a$$B$$b$$B^*$$b$

Więc pozwól, że powiem ci, jak udoskonalić, a następnie połączę wszystko, aby uzyskać pełny algorytm dla tego problemu. W poniższym przykładzie niech oznacza zbiór różnic, tzn. ; skupimy się na znalezieniu wyrafinowanego nadmiernego przybliżenia$D$$D=\{a_i-b_j:1 \le i,j \le 6\}$$A^*$ , zważywszy .$A,B$

Jak obliczyć udoskonalenie. Rozważmy jeden różnicy . Rozważmy zestaw . W oparciu o naszą wiedzę, że jest nadmiernym przybliżeniem , wiemy, że co najmniej jeden element musi być elementem . W związku z tym można traktować każdy z elementów jako „sugestii” po numer może zawierać w . Prześledźmy więc wszystkie różnice i, dla każdej, określ, które liczby są „sugerowane” przez .$d \in D$$d+B=\{d+y : y \in B\}$$B$$b$$d+B$$\{a_1,\dots,a_6\}$$d+B$$A$$d \in D$$d$

Teraz zauważę, że liczba pewnością zostanie zasugerowana co najmniej 6 razy podczas tego procesu. Dlaczego? Ponieważ różnica występuje w , a kiedy ją przetworzymy, będzie jedną z sugerowanych przez nią liczb (ponieważ mamy gwarancję, że , z pewnością będzie zawierać ). Podobnie różnica pojawia się gdzieś w i spowoduje ponowne zasugerowanie . W ten sposób widzimy, że poprawna wartość$a_1$$a_1-b_1$$D$$a_1$$b_1 \in B$$(a_1-b_1)+B$$a_1$$a_1-b_2$$D$$a_1$$a_1$ zostanie zasugerowana co najmniej 6 razy. To samo dotyczy i$a_2$$a_3$, i tak dalej.

Niech będzie zbiorem liczb$A^*$$a^*$ , które zostały zasugerowane co najmniej 6 razy. To z pewnością będzie nadmierne przybliżenie „s, w powyższych komentarzach.$a$

Jako optymalizacji, możemy odfiltrować wszystkie propozycje, które nie są obecne w natychmiast: innymi słowy, możemy traktować różnicę jak sugeruje wszystkie wartości . Gwarantuje to, że będziemy musieli . Mamy nadzieję, że jest ściśle mniejsze niż$A$$d$$(d+B)\cap A$$A^* \subseteq A$$A^*$$A$ ; żadnych gwarancji, ale jeśli wszystko pójdzie dobrze, może tak będzie.

Podsumowując, algorytm udoskonalenia daje$A,B$$A^*$ jest następujący:

1. Niech . To jest zestaw sugestii.$S = \cup_{d \in D} (d+B)\cap A$

2. Policz, ile razy pojawia się każda wartość w . Niech oznacza zbiór wartości, które są w co najmniej 6 razy w . (Może to być realizowane skutecznie budując tablicę z 251 na początku, początkowo wszystkie zera, i za każdym razem liczba jest sugerowane, to przyrost ; na koniec zamiatać przez szuka elementów, których wartość wynosi 6 lub większy)$S$$A^*$$S$$a$$s$$a[s]$$a$

Podobną metodę można zbudować w celu udoskonalenia celu uzyskania . W zasadzie odwrotnej rzeczy powyżej odwrócić pewne oznaki: np zamiast , obejrzysz .$A,B$$B^*$$d+B$$-d+A$

Jak obliczyć początkowe przekroczenie przybliżenia. Aby uzyskać nasze wstępne przybliżenie, jednym z pomysłów jest założenie (wlog), że . Wynika stąd, że każda wartość musi pojawić się gdzieś między , stąd listę różnic mogą być stosowane jako naszego początkowego nadmiernego zbliżenia dla tych. Niestety, nie daje to nam bardzo przydatnego przesadnego przybliżenia wartości .$b_1=0$$a_i$$D$$D$$a$$b$

Lepszym podejściem jest dodatkowe odgadnięcie wartości jednego z „a”. Innymi słowy, zakładamy (wlog), które i używać jako naszego początkowego nadmiernego zbliżenia „s. Następnie możemy odgadnąć, która z tych wartości jest 36 rzeczywiście jeden z „s, powiedzmy . To daje nam w przybliżeniu dla . Używamy tego wstępnego przeszacowania , a następnie iteracyjnie dopracowujemy go do zbieżności i sprawdzamy, czy wynik jest poprawny. Powtarzamy do 36 razy, z 36 różnymi przypuszczeniami na (średnio powinno wystarczyć 6 domysłów), aż znajdziemy taki, który działa.$a$$b_1=0$$A=D$$a$$a$$a_1$$B=a_1-D$$b$$A,B$$a_1$

Pełny algorytm. Teraz możemy mieć pełny algorytm do obliczania . Zasadniczo wyprowadzamy wstępne przybliżenie dla i , a następnie iteracyjnie udoskonalamy.$a_1,\dots,a_6,b_1,\dots,b_6$$A$$B$

1. Zgadnij: Dla każdego zgadnij, że . Wykonaj następujące czynności:$z \in D$$a_1=z$

   1. Początkowe : zdefiniuj i .$A=D$$B=z-D$

   2. Udoskonalenie iteracyjne: Powtarzaj kolejno następujące czynności aż do zbieżności:

      • Popraw aby uzyskać nowe przybliżenie z .$A,B$$B^*$$b$
      • Popraw aby uzyskać nowe przybliżenie dla$A,B^*$$A^*$$a$ „s.
      • Niech i .$A:= A^*$$B:= B^*$

   3. Sprawdź sukces: jeśli każdy z wynikowych zestawów ma rozmiar 6, sprawdź , czy są one poprawnym rozwiązaniem problemu. Jeśli tak, przestań. Jeśli nie, przejdź do pętli nad wartościami kandydującymi .$A,B$$z$

Analiza. Czy to zadziała? Czy ostatecznie zbiegnie się w i$A=\{a_1,\dots,a_6\}$$B=\{b_1,\dots,b_6\}$ , czy utknie bez całkowitego rozwiązania problemu? Najlepszym sposobem na sprawdzenie tego jest prawdopodobnie przetestowanie go. Jednak dla twoich parametrów, tak, spodziewam się, że będzie skuteczny.

Jeśli użyjemy metody nr 1, o ilenie są zbyt duże, heurystycznie spodziewam się, że rozmiary zestawów zmniejszą się monotonicznie. Rozważmy wyprowadzania z . Każda różnica sugerujewartości; jeden z nich jest poprawny, a drugi można traktować (heurystycznie) jako liczby losowe. Jeśli jest liczbą, która nie pojawia się wśród „s, jakie jest prawdopodobieństwo, że przeżyje filtrowanie i dodano do ? Spodziewamy sugestii dotyczącej$|A|,|B|$$A^*$$A,B$$d$$|B|$$|B|-1$$x$$a$$A^*$$a$$(|B|-1) \times 36/251$razy ogółem (średnio przy standardowym odchyleniu o pierwiastek kwadratowy z tego). Jeśli , prawdopodobieństwo, że niepoprawne. Na przykład, jeśli , to na podstawie tych heurystyk oczekuję$|B|\le 36$$x$ przetrwa filtrowanie powinno wynosić około lub więcej (przy użyciu normalnego przybliżenia dla dwumianu, z korektą ciągłości). (Prawdopodobieństwo jest mniejsze, jeśli jest mniejsze; np. Dla , spodziewam się .) Spodziewam się, że rozmiar będzie około , co zdecydowanie poprawi nadmierne zbliżenie, ponieważ jest ono ściśle mniejsze niż$p=0.4$$|B|$$|B|=30$$p\approx 0.25$$A^*$$p (|A|-6) + 6$$|A|$$|A|=|B|=36$$|A^*|\approx 18$ , co stanowi dużą poprawę w stosunku do.$|A|$

Dlatego przewiduję, że czas działania będzie bardzo szybki. Spodziewam się, że około 3-5 iteracji udoskonalenia będzie wystarczających do konwergencji, a zwykle około 6 domysłów w punkcie powinno prawdopodobnie wystarczyć. Każda operacja udoskonalania obejmuje może kilka tysięcy odczytów / zapisów w pamięci, a robimy to może 20-30 razy. Oczekuję więc, że będzie to bardzo szybkie, jak na określone parametry. Jednak jedynym sposobem, aby się przekonać, jest wypróbowanie go i sprawdzenie, czy działa dobrze, czy nie.$z$