Wyzwanie
Znajdź najmniejszą osłonę zasad (np. Moduły), których zestawy kwadratowych reszt można przetestować poprzez przeglądanie tabeli, aby ostatecznie ustalić, czy dana nieujemna liczba całkowita n jest idealnym kwadratem. Wszystkie zasady muszą być mniejsze lub równe pierwiastkowi kwadratowemu z maksymalnej wartości n .
Odpowiedź z najmniejszym zestawem podstaw dla danej kategorii n wygrywa wyzwanie. (Oznacza to, że potencjalnie może być więcej niż jeden zwycięzca.) Kategorie n to:
Category Maximum allowed n Maximum allowed modulus/base
------------- -------------------- ----------------------------
8-bit values 255 15
16-bit values 65535 255
32-bit values 4294967295 65535
64-bit values 18446744073709551615 4294967295
W przypadku remisu z dwoma zestawami mającymi jednakową liczność, remis trafi do zestawu mającego większą zdolność wykrywania wcześniejszych kwadratów w sekwencji.
W przypadku, gdy nie zostaną znalezione pełne okładki (co jest całkowicie prawdopodobne w przypadku kategorii 32-bitowych i 64-bitowych), zwycięzcą zostanie zestaw baz, który statystycznie lub możliwy do udowodnienia wyklucza najwyższy odsetek kwadratów (bez niepoprawnych błędów) zgłaszanie kwadratów jako niekwadratowych). Poniżej znajduje się omówienie niepełnych okładek.
tło
W wielu zastosowaniach teorii liczb pojawia się pytanie, czy jakaś liczba n jest kwadratem idealnym (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 itd.). Jednym ze sposobów sprawdzenia, czy n jest kwadratem, jest sprawdzenie, czy floor (√n) ² = n, to znaczy, czy zaokrąglony w dół pierwiastek kwadratowy n , gdy jest kwadratem, zwraca n . Na przykład podłoga (√123) ² = 11² = 121, która nie jest 123, więc 123 nie jest kwadratowe; ale podłoga (√121) ² = 11² = 121, więc 121 jest kwadratowe. Ta metoda działa dobrze w przypadku małych liczb, zwłaszcza gdy dostępna jest sprzętowa operacja pierwiastka kwadratowego. Ale w przypadku dużych liczb (setek lub tysięcy bitów) może być bardzo wolny.
Innym sposobem sprawdzenia kwadratowości jest wykluczenie kwadratów za pomocą kwadratowych tabel reszt. Na przykład wszystkie kwadraty w podstawie 10 muszą mieć ostatnią cyfrę (jedno miejsce), która wynosi 0, 1, 4, 5, 6 lub 9. Te wartości tworzą zbiór kwadratowej reszty dla zasady 10. Więc jeśli zasada -10 liczba kończy się na 0, 1, 4, 5, 6 lub 9, wiesz, że może być kwadratowa i konieczne będzie dalsze sprawdzenie. Ale jeśli base-10 końce numer w 2, 3, 7 lub 8, wówczas można mieć pewność, że to nie kwadrat.
Spójrzmy więc na inną bazę. Wszystkie kwadraty w bazie 8 muszą kończyć się na 0, 1 lub 4, co dogodnie stanowi tylko 3 z 8 możliwości, co oznacza 37,5% szansy, że liczba losowa będzie prawdopodobnie kwadratowa, lub 62,5% szansy, że liczba losowa zdecydowanie nie będzie kwadratowa. Są to znacznie lepsze kursy niż daje podstawa 10. (I zauważ, że operacja modułu podstawy 8 jest po prostu logiczną operacją, w przeciwieństwie do modułu podstawy 10, który jest dzieleniem przez 10 z resztą.)
Czy są jeszcze lepsze bazy? Właściwie to tak. Baza 120 ma 18 możliwości (0, 1, 4, 9, 16, 24, 25, 36, 40, 49, 60, 64, 76, 81, 84, 96, 100 i 105), co stanowi tylko 15% szansa bycia kwadratem. A baza 240 jest jeszcze lepsza, z jedynie 24 możliwościami, co stanowi jedynie 10% szansy na bycie kwadratem.
Ale żadna pojedyncza zasada sama w sobie nie może definitywnie określić kwadratowości (chyba że jest większa niż maksymalna testowana liczba, co jest wyjątkowo niepraktyczne). Sama pojedyncza podstawa może jedynie wykluczyć kwadratowość; nie może jednoznacznie zweryfikować kwadratowości. Tylko starannie dobrany zestaw zasad, współpracujących ze sobą, może jednoznacznie zweryfikować kwadratowość w zakresie liczb całkowitych.
Powstaje zatem pytanie: jaki zestaw zasad tworzy minimalną osłonę, która łącznie pozwala na ostateczne odjęcie kwadratowości lub niekwadratowości?
Przykład poprawnej, ale nie minimalnej ochrony
Pokrywa 16-podstawowa pokrywa {3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 29, 31, 37} jest wystarczająca do ostatecznego określenia kwadratowości lub niekwadratności wszystkie 16-bitowe wartości od 0 do 65535. Ale nie jest to minimalna ochrona, ponieważ istnieje co najmniej jedna 15-bazowa ochrona, którą można łatwo wykryć. W rzeczywistości jest prawdopodobne, że istnieją znacznie mniejsze osłony - być może z zaledwie 6 lub 7 bazami.
Ale dla ilustracji przyjrzyjmy się testowaniu wartości próbki n przy użyciu tego 16-podstawowego zestawu okładek. Oto zestawy reszt kwadratowych dla powyższego zestawu zasad:
Base m Quadratic residue table specific to base m
------ ----------------------------------------------------
3 {0,1}
4 {0,1}
5 {0,1,4}
7 {0,1,2,4}
8 {0,1,4}
9 {0,1,4,7}
11 {0,1,3,4,5,9}
13 {0,1,3,4,9,10,12}
16 {0,1,4,9}
17 {0,1,2,4,8,9,13,15,16}
19 {0,1,4,5,6,7,9,11,16,17}
23 {0,1,2,3,4,6,8,9,12,13,16,18}
25 {0,1,4,6,9,11,14,16,19,21,24}
29 {0,1,4,5,6,7,9,13,16,20,22,23,24,25,28}
31 {0,1,2,4,5,7,8,9,10,14,16,18,19,20,25,28}
37 {0,1,3,4,7,9,10,11,12,16,21,25,26,27,28,30,33,34,36}
Teraz przetestujmy liczbę n = 50401 przy użyciu tego zestawu zasad, przekształcając je w każdą bazę. (To nie jest najskuteczniejszy sposób badania pozostałości, ale jest wystarczający do celów wyjaśniających.) Interesuje nas miejsce 1 (zaznaczone poniżej w nawiasach):
Base "Digits" in base m
m m^9 m^8 m^7 m^6 m^5 m^4 m^3 m^2 m^1 ( m^0 )
---- -----------------------------------------------------------------
3 2 1 2 0 0 1 0 2 0 ( 1 ) ✓
4 3 0 1 0 3 2 0 ( 1 ) ✓
5 3 1 0 3 1 0 ( 1 ) ✓
7 2 6 6 6 4 ( 1 ) ✓
8 1 4 2 3 4 ( 1 ) ✓
9 7 6 1 2 ( 1 ) ✓
11 3 4 9 5 ( 10 )
13 1 9 12 3 ( 0 ) ✓
16 12 4 14 ( 1 ) ✓
17 10 4 6 ( 13 ) ✓
19 7 6 11 ( 13 )
23 4 3 6 ( 8 ) ✓
25 3 5 16 ( 1 ) ✓
29 2 1 26 ( 28 ) ✓
31 1 21 13 ( 26 )
37 36 30 ( 7 ) ✓
Widzimy więc, że w 13 z tych zasad reszta pasuje do znanej reszty kwadratowej (nazwij to „trafieniem” w tabeli), a w 3 z tych zasad reszta nie pasuje do znanej reszty kwadratowej (nazwij to "chybienie"). Wystarczy jedna chybić, aby wiedzieć, że liczba nie jest kwadratowa, więc moglibyśmy zatrzymać się na 11, ale dla celów ilustracyjnych zbadaliśmy tutaj wszystkie 16 baz.
Przykład niepełnej ochrony
Z technicznego punktu widzenia niepełna ochrona nie jest ochroną, ale to nie ma znaczenia. Zbiór zasad {7, 8, 11, 15} prawie obejmuje wszystkie 8-bitowe wartości n od 0 do 255 poprawnie, ale nie do końca. W szczególności niepoprawnie identyfikuje 60 i 240 jako kwadratowe (są to wyniki fałszywie dodatnie) - ale poprawnie identyfikuje wszystkie rzeczywiste kwadraty (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196 i 225) i nie czyni innych fałszywych trafień. Jest to więc zestaw 4, który prawie odnosi sukces jako rozwiązanie, ale ostatecznie zawodzi, ponieważ niepełna ochrona nie jest prawidłowym rozwiązaniem.
Dla 8-bitów n zbiór zasad {7, 8, 11, 15} jest jednym z dwóch zestawów 4 zasad, które powodują dwa błędy, i jest siedem zestawów 4 zasad, które powodują tylko jeden błąd. W rzeczywistości nie istnieją zestawy 4 zasad, które stanowią pełne i dokładne pokrycie wartości 8-bitowych. Czy potrafisz znaleźć zestaw 5 zasad, które nie powodują błędów, poprawnie pokrywając wszystkie 8-bitowe wartości? A może potrzebujesz 6 lub więcej? (Znam odpowiedź na 8-bitowe n , ale nie zamierzam jej zdradzić. Nie znam odpowiedzi na 16-bitowe, 32-bitowe lub 64-bitowe i uważam, że nawet 16- przypadku bitów nie da się rozwiązać za pomocą przeszukiwania metodą brute-force. Rozwiązanie 32-bitowych i 64-bitowych przypadków z pewnością będzie wymagać genetycznych, heurystycznych lub innych technik wyszukiwania.)
Komentarz do kryptograficznie dużych liczb
Poza liczbami 64-bitowymi - w setkach lub tysiącach cyfr binarnych - w tym przypadku bardzo przydatna jest szybka kontrola kwadratowości, nawet jeśli okładka jest niepełna (co z pewnością będzie w przypadku naprawdę dużych liczb). Jak taki test może być nadal przydatny, nawet jeśli nie jest wystarczająco decydujący? Cóż, wyobraź sobie, że miałeś wyjątkowo szybki test prostopadłości, który działał poprawnie przez 99,9% czasu i dawał fałszywe negatywy przez pozostałe 0,1% czasu i nigdy nie dawał fałszywych wyników pozytywnych. Dzięki takiemu testowi byłbyś w stanie niemal natychmiast określić niekwadratowość liczby, a następnie w wyjątkowych przypadkach niezdecydowania można zastosować wolniejszą metodę rozwiązania nieznanego w inny sposób. Zaoszczędziłoby to sporo czasu.
Na przykład zestaw {8, 11, 13, 15} jest poprawny 99,61% czasu dla 8-bitowych wartości n od 0 do 255, jest poprawny 95,98% czasu dla 16-bitowych wartości n od 0 do 65535, i jest poprawny 95,62% czasu dla 24-bitowych wartości n od 0 do 16777215. Gdy n idzie w nieskończoność, procent poprawności dla tego zestawu zasad spada, ale asymptotycznie się zbliża i nigdy nie spada poniżej 95,5944% poprawność.
Tak więc nawet ten bardzo mały zestaw 4 małych baz jest przydatny do niemal natychmiastowego zidentyfikowania około 22 spośród 23 dowolnie dużych liczb jako niekwadratowych - eliminując potrzebę dalszej kontroli tych liczb wolniejszymi metodami. Wolniejsze metody należy wówczas zastosować tylko w niewielkim odsetku przypadków, których nie można wykluczyć za pomocą tego szybkiego testu.
Warto zauważyć, że niektóre 16-bitowe bazy same osiągają lepsze niż 95%. W rzeczywistości każda z poniższych baz jest w stanie wyeliminować lepiej niż 97% wszystkich liczb do nieskończoności, ponieważ nie są kwadratowe. Kwadratowy zestaw reszt dla każdej z tych zasad może być reprezentowany jako tablica upakowanych bitów z wykorzystaniem tylko 8192 bajtów.
Oto 10 najpotężniejszych pojedynczych baz mniejszych niż 2 ^ 16:
Rank Base Prime factorization Weeds out
---- ------------------------------ ---------
1. 65520 = 2^4 x 3^2 x 5 x 7 x 13 97.95%
2. 55440 = 2^4 x 3^2 x 5 x 7 x 11 97.92%
3. 50400 = 2^5 x 3^2 x 5^2 x 7 97.56%
4. 52416 = 2^6 x 3^2 x 7 x 13 97.44%
5. 61200 = 2^4 x 3^2 x 5^2 x 17 97.41%
6. 44352 = 2^6 x 3^2 x 7 x 11 97.40%
7. 63360 = 2^7 x 3^2 x 5 x 11 97.39%
8. 60480 = 2^6 x 3^3 x 5 x 7 97.38%
9. 63840 = 2^5 x 3 x 5 x 7 x 19 97.37%
10. 54720 = 2^6 x 3^2 x 5 x 19 97.37%
Widzisz coś interesującego, co łączy wszystkie te bazy? Nie ma powodu, aby sądzić, że mogą być przydatne w połączeniu razem (może są, może nie są), ale jest tu kilka dobrych wskazówek, które podstawy mogą mieć największy wpływ na większe kategorie liczb.
Wyzwaniem boczny: Jedna z najbardziej znaczących zasad (jeśli nie najbardziej) do 2 ^ 28 wynosi 245044800, który sam może prawidłowo wyeliminować 99,67% niż kwadratów, lub od około 306 do 307 liczb losowych rzucane na niego. Można znaleźć na najbardziej wpływowych pojedynczą bazę mniej niż 2 ^ 32?
Związane z
Istnieje kilka bardzo fajnych pomysłów w poniższych pytaniach, które są ze sobą ściśle powiązane, a także kilka sztuczek mikrooptymalizacyjnych, które przyspieszają niektóre operacje. Chociaż powiązane pytania nie mają na celu znalezienia najsilniejszego zestawu zasad, idea silnych zasad jest w sposób dorozumiany kluczowa dla niektórych stosowanych tam technik optymalizacji.
źródło
Odpowiedzi:
Matematyka
Tak naprawdę niewiele wiem o teorii liczb (niestety), więc jest to dość naiwne podejście. Używam chciwego algorytmu, który zawsze dodaje bazę, która ma najwięcej błędów dla pozostałych liczb.
Rozwiązuje 8 bitów w krótkim czasie dzięki następującym 6 zasadom:
16 bitów zajmuje 6 sekund i daje następującą 6-bazową osłonę:
W większych przypadkach w podejściu tym oczywiście brakuje pamięci.
Aby przekroczyć 16 bitów, muszę wymyślić sposób sprawdzenia kompletności okładki bez faktycznego utrzymywania listy wszystkich liczb do Nmax (lub przejdź i poznaj teorię liczb).
Edycja: Skrócono czas działania 16 bitów z 66 do 8 sekund, wypełniając listę liczb tylko tymi, które nie są wykluczone przez najbardziej efektywną bazę. Powinno to również znacznie poprawić zużycie pamięci.
Edycja: Dodałem dwie niewielkie optymalizacje w celu zmniejszenia przestrzeni wyszukiwania. To nie jest jedna z oficjalnych kategorii, ale dzięki temu znalazłem 8-bazową osłonę na 24 bity w 9,3 godziny:
Jeśli chodzi o optymalizacje, pomijam teraz wszystkie bazy, które dzielą LCM baz już znajdujących się w pokrywie, a kiedy testuję wydajność bazy, testuję ją tylko na liczbach do LCM tej nowej bazy i wszystkich baz już mieć.
źródło