Rzędy liczb modulo p i logarytm dyskretny — dodatek do wykładu, UJK
Analiza matematyczna · UJK⏱ 57 min
Dodatek do wykładu na UJK: skąd się bierze „prawie symetria” ciągu rzędów liczb modulo p, zaobserwowana na zajęciach dla p = 97. Kongruencje, rząd elementu, generator i logarytm dyskretny, a na koniec ogólny warunek przez największy wspólny dzielnik i waluację 2-adyczną – sprawdzony komputerowo.
W tym nagraniu
Kongruencje i potęgowanie modulo n, małe twierdzenie Fermata
Rząd liczby modulo p, generator i logarytm dyskretny
Rząd potęgi generatora a NWD(k, p − 1)
Kiedy x i −x mają ten sam rząd – warunek z waluacją 2-adyczną
Dodatek do wykładu na UJK, który wyjaśnia obserwację z zajęć: ciąg rzędów liczb modulo p = 97 okazał się „prawie symetryczny”. Żeby to zrozumieć, nagranie przypomina kongruencje, potęgowanie modulo n i małe twierdzenie Fermata.
Rząd liczby a modulo p to najmniejsze k ≥ 1, dla którego aᵏ ≡ 1 (mod p). Liczba o rzędzie p − 1 to generator (pierwiastek pierwotny): jej potęgi dają wszystkie niezerowe reszty, a wykładnik, do którego trzeba ją podnieść, żeby dostać daną resztę, to logarytm dyskretny. Kluczowy fakt: rząd potęgi gᵏ generatora wynosi (p − 1)/NWD(k, p − 1).
Na tej podstawie nagranie odpowiada, kiedy x i −x mają ten sam rząd — warunek wyraża się przez waluację 2-adyczną, czyli wykładnik najwyższej potęgi dwójki dzielącej odpowiednie liczby. Wynik jest sprawdzony komputerowo dla p = 97 i p = 37. To dobry przykład, jak eksperyment na zajęciach prowadzi do twierdzenia.
Lekcje kursu „Matematyka od nowa” na ten temat
Szkolne podstawy tego, o czym jest nagranie — interaktywnie i za darmo.
Transkrypt został wygenerowany automatycznie na podstawie napisów YouTube, więc może zawierać błędy w zapisie wzorów, nazwisk i terminów. Kliknij znacznik czasu, aby przewinąć wideo do danego fragmentu. (5077 słów)
Opowiem o tym, skąd się bierze fakt doświadczalny, który zaobserwowaliśmy ostatnio na wykładzie. To najpierw krótki recap. Pracowaliśmy z arytmetyką modularną. To znaczy takim czymś, że powiemy, że A przestaje do B modulo N, gdy zgadzają im się reszty dzielenia przez N. Jako że jestem leniwy, to napiszę to w równoważnej postaci, to znaczy, że N dzieli A minus B. Po polsku różnią się o wielokrotność n. Wcześniej mówiliśmy, że to jest dość kanoniczny przykład relacji równoważności na liczbach całkowitych.
W ogóle fakt, że do badania podzielności zatrudniamy liczby, którym wolno być ujemnymi, to jest pewien upgrade nad tym, co robiliśmy w szkole. O tym czymś można myśleć prawie jako równości. Na przykład jak mam przestawanie takie i przestawanie takie, to ja mogę dodać stronami wychodzi to, czego się należy spodziewać tak samo ja mogę pomnożyć stronami i wychodzi to, czego się należy spodziewać. I my się chcieliśmy dowiedzieć, co się dzieje, jak się robi potęgowanie. Nie takie potęgowanie, jakie wynika z tego, bo z tego oczywiście też wynika, że jak pomnożymy m sztuk takiego napisu takie coś się nazywa kongruencją. Żeby było inne słowo niż przestawanie.
Ponieważ lubimy, jak jest dużo słów, które brzmią bez sensu inaczej, na przykład pochodne i różniczkowanie. Anyway, z tej procedury potęgowanie tak działa. Natomiast już takie coś zazwyczaj nie działa. Oczywiście bywają czasem przypadki, kiedy to jest prawda, natomiast ogólnie przystawanie modułu N nie implikuje czegoś takiego. I my się szczególnie cieszyliśmy z tego, co się dzieje, jak N jest liczbą pierwszą.
Przy okazji się pobywaliśmy na coś, co się nazywa mają twierdzeniem Fermata, którego dowód pewnie jeszcze kiedyś będzie. Ono mówi tyle, że jeśli mam p nie dzieli a, matematycy będą pisać najpierw to przez co dzielimy, a potem to co chcemy dzielić. Ten napis to jest powiedzenie, że p nie jest dzielnikiem a. To wtedy a do p minus pierwszej przystaje do jedynki modułu p. Ta wiedza nam się przydawała, bo analizowaliśmy potęgi różnych liczb modulo liczby pierwszej. W szczególności ta wiedza wymusza, że potęgi dowolnej liczby modulo p się zapętlą.
Bo jak ja mam a do zerowej równe 1, potem się coś dzieje, a do pierwszej jest równe a, bla bla bla. Po drodze być może spotkam jedynkę, a być może nie. ale mam gwarancję, że jeśli a nie jest bardzo głupie, to znaczy jeśli a nie jest zerem modulo p to tu mam zapętlenie do jedynki co się dzieje dalej? a do p to przestaje do jedynki więc a do p przestaje do a więc modulo p ten ciąg się zapętla w spokojnie? anyway, wprowadziliśmy pojęcie rzędu powiedzieliśmy, że dla to jest w eksplanatury, że dla p niedzielącego a, że rząd modulo p liczby a to jest najmniejszy, nietrywialny wykładnik j w większych równych 1 takich, że a do j przystaje do 1 modulo p.
Definicja jak definicja. Z tymi rzędami bywa różnie. Jak widzieliśmy jakieś przykłady, że na przykład da się policzyć komputerem, że rząd modulo 29 z liczby 2 jest największy możliwy, to znaczy p-1, bo 2 do 29-1 musi być jedynką z mojego ćwierdzenia fermata, ale na przykład jak odpowiednio lepiej dobierzemy liczbę, na przykład weźmiemy moduł 127, to rząd dwójki jest równy 7. Więc różnie to bywa. Stwierdziliśmy też, że zawsze zachodzi podzielność.
Że to dzieli p-1 i to był taki śmieszny dowód przez dzielenie zresztą mam dwa koty na żywo na kamerze to się rzadko nie zdarza co bliski patrzysz z noslajdem za okno ty jesteś domowym kotem ty się boisz spaceru anyway no więc zauważyliśmy takie coś że jak wypisujemy ciąg to jest jakaś funkcja to jest funkcja na liczbach efektywnie od jedynki do p-1 dlaczego? bo bo dla zera to nie ma sensu, bo zero do żadnej dodatniej potęgi nie jest jedynką.
Natomiast jak się przewidzimy przez P, to wszystko funkcjonuje w modułach P. Wracamy do tych. To są jedne, które mają sens. No i zauważyliśmy przeciwną prawidłowość. Dla P równego 97 ten ciąg jest prawie symetryczny. Gdzie symetryczny, to jest planindromiczny. to znaczy jak go odwrócę akurat napisanego tak, jak go odwrócę tak, że napiszę odtał minus jedynki, to jest prawie to samo.
Gdzie to prawie, to było z dokładnością do kilku złoczyńców. Ja, znaczy my ich znaleźliśmy prawie wszystkich, ja potem jeszcze wypisałem w tych notatkach, które zostały z wykładu w powrojonej wersji i okazało się, że takie coś zachodzi dla każdego x, które nie jest które nie jest czym? które nie jest w zbiorze w zbiorze sześciu złoczyńców tu ich nie wypisanych, zlogorytmowanych tu jest napisane 35, 36 61 62 96 no i to jest dziwne spodziewalibyśmy się, że takie zjawisko będzie albo uniwersalne
Albo takie coś się w ogóle nie będzie działo. A tu wyszło prawie symetrycznie. I chcielibyśmy zrozumieć dlaczego tak się dzieje. Dobrze, czym jeszcze potrzebujemy czegoś wiedzieć? Właśnie, twierdzenie. To jest twierdzenie, którego tym bardziej dzisiaj nie udowodnimy. Twierdzenie o generatorze jest takie, że istnieje takie x, że rząd x jest największym możliwy. To się da udowodnić prosto tylko jak się zrobi technologię.
Chwilowo w to wierzymy na wiarę. I my chcieliśmy poszukiwanie takich x-ów wyrazić w terminach twierdzenia o generatorze. To znaczy ten nasz cały poligon, ja tu mówię o poligonie, na którym liczby się podnoszą do potęgi, a tam koty robią wojnę domową. W każdym razie, ten nasz cały poligon od 1 do p-1, to się nie trudno przekonać, że to są kolejne potęgi generatora. Jak to żyje modulo p, to wykładniki generatora żyją modulo p-1, bo jak go podniosę do p-1 potęgi, to dostanę z powrotem 1, czyli g do zerowej.
Co więcej, każde dwie liczby na tej liście są różne. Ja często wymiennie używam liczby i reszty dziedzinienia przez p. Tak naprawdę można po prostu myśleć o zamkniętej strukturze algebraicznej, która składa się z reszt dziedzinienia przez p. Albo można myśleć o przystawaniu, to jest dokładnie to samo. W każdym razie, tak że czasem będę mówił równać zamiast przystawianie. Whisky przejął siedzenie pandy. Anyway, żadne dwie rzeczy stąd nie mogą być równe, bo gdybym miał g do coś równe g do coś innego, to wtedy g do różnicy musiało być równe 1.
A z tego, że g to jest, nazwijmy go g od generatora, generatora, nie mylić dziewiątką, z tego, że g dopiero do potęgi p minus pierwszej jest równe 1. p minus 1 to jest najmniejszy, nietrywialny wykładnik, w którym to się dzieje. Ty dostałeś chrupki, to nie masz się o co bić. Generator to jest świetna rzecz, bo dodawanie liczb to my jakoś tam rozumiemy. Mnożenie zawsze jest dziwne.
Wielokrotności liczby modulo p To jest prosta sprawa To Świetnie Potem nie będę miał z czego wykładu prowadzić Jak wizję notatki Natomiast mnożenie To jest coś esoterycznego Tak a priori To twierdzenie pokazuje, że ja jestem w stanie Pokazać taką identyfikację tego Z tym, że mnożenie tutaj To jest to samo co dodawanie na wykładnikach No i na przykład To nasze pytanie, dla jakichś x dzieje się takie coś to można przetłumaczyć na pytanie o tym, że te x to są jakieś podańki g tak naprawdę można powiedzieć, że jeśli x jest równe g do k to z definicji jest równoważne temu, że że k to jest logarytm przy podstawie g z x w domyśle modulo p, bo już tu nie mam miejsca na napisanie pod tym logarytmem modulo p co jest znaczy modulo co jest ten logarytm Także tak, zastanawiamy się, kiedy rząd x jest równy rzędowi p-x.
P-x modulo p jest nieodróżniany od minus x. To najpierw sam rząd x. No to x do jakiejś potęgi j to jest g do k razy j. No to najmniejsze j takie, żeby to było jedynką, to żeby to było jedynką, to wykładnik musi się dzielić przez p-1, bo tak działa g. no to to jest równoważne z tym że p-1 dzieli dzieli kj a z faktu, że no to jak ja to chcę opisać?
Ja to chcę opisać tak, że ja odfaktoryzuję wspólne czynniki to znaczy podzielę p-1 przez zamiast pisać nwd to ludzie od teorii liczb zazwyczaj piszą po prostu a b w nawiasie. Ponieważ nwd jest tak ważne, że to jest ta jedna rzecz, którą można przepisać nawiasowi, któremu nie piszemy żadnej funkcji przed nią. Po angielsku się pisze gcd od greatest common divisor. Więc ja prawą i lewą stronę tej podzielności mogę podzielić przez nwd p-1 i k prawą stronę też.
No to teraz te rzeczy są względnie pierwsze. To nie ma znaczenia. To nie pomaga temu iloczynowi na dzielenie się przez to, bo te już nie mają wspólnych czynników pierwszych. To jest równoważne z tym, że P-1 z odfaktoryzowanym P-1 na igrze spódny dzielnik dzieli J. No to dostaliśmy klasyfikację takich J, które to spełniają. Pierwszym oczywiście jest 0, które jest wielokrotna świątego. następnym pierwszym nietrywialnym jest dokładnie ten iloraz. No to świetnie. Udowodniliśmy, że rząd modulo p x jest równy p minus 1 przez p minus 1 gcd z k, gdzie k to jest logarytm dyskretny przy podstawie g.
No dobro. No to rząd minus x tak samo. Tylko teraz musimy wiedzieć, co to jest logarytm z minus x. W normalnych liczbach rzeczywistych to to by nie miało sensu. Jak logarytm z x ma sens, to znaczy, że x jest dodatni, czyli minus x jest ujemny, czyli to nie ma sensu. Tu wszystko jest w tym samym garnku od 0 do p minus 1. Łatwo się przekonać, że g do potęgi k przez 2 czy łatwo się przekonać? To wynika z ogólnej teorii. O, nie, to nawet można napisać. Tu napiszę p minus 1 przez 2. Oczywiście w tej całej opowieści p jest liczbą pierwszą różną od dwójki, bo dla dwójki to wszystko się trygializuje.
Takie coś. razy g do p plus pierwszej, do p minus pierwszej przez 2 plus 1, to jest bez wątpienia równe 1, bo to jest równe różnice kwadratów, to jest równe g do p minus pierwszej minus 1, czyli to w ogóle jest 0. No dobra, to jest 0 modulo p. Jak iloczyn dwóch rzeczy jest 0 modulo p, no to przynajmniej jedna musi być. To, to jest g do potęgi mniejszej niż jego rząd. g do nic mniejszego niż p minus 1 nie ma prawa być jedynką czyli to nie dzieli się przez p w związku z tym zostaje nam, że to się musi dzielić przez p p musi dzielić g do p minus 1 przez 2 plus 1 co po polsku znaczy tyle że g do p minus 1 przez 2 jest minus jedynką czyli tu mamy p minus 1 przez p minus 1 i logarytm dyskretny z minus x no to równość tych dwóch rzeczy no to prosta sprawa.
Napiszę równość, skracamy się p-1 zostają mi te największe wspólne dzielniki. Więc pytamy dla jakich k tak naprawdę? Dla jakich k zachodzi taka równość n w d. Oznaczmy to p-1 przez n. Tu jest k plus n przez 2 tu jest n i tu jest po prostu kn. n jest równe p-1 w szczególności n jest parzyste. Żeby w ogóle miało sens n przez 2.
Dobra, i w tym momencie utknęliśmy na wykładzie, gdzie my, to było to, że ja za bardzo próbowałem to atakować w sposób, który byłby sprofilowany dla naszego konkretnego przypadku. Naszym konkretnym przypadkiem było p równe 97. I tam mieliśmy właśnie prawie symetrię. 97 było o tyle szczególne, że to jest 3 razy 32. To jest potęga dwójki razy tylko jeszcze jedna mała liczba pierwsza. i ja myślałem, że głównym powodem, dla którego jest prawie symetria, jest właśnie to coś, że tam jest potęga dwójki razy trzy.
No i to jest prawie, że racja, tylko, że prościej jest dostać ogólną klasyfikację, nie posiłkując się tym, że tam jest akurat trójka, a potem ją wyspecjalizować do 97. Dobrze, jak się takie rzeczy robi? Widać, że gdyby jakimś cudem udało nam się tutaj napisać n przez dwa, no to hulajdusza odjąłbym, bo tak działa algorytm GIDES-a. Ogólnie plan był taki, żeby tutaj trzymać rzeczy, które powinniśmy mieć w pamięci operacyjnej. To zmażę oznaczenie, bo się do niego przyzwyczailiśmy. To napiszę jakieś takie proste prawa natury. Na przykład, że A plus, na przykład, że NWDAB to jest to samo co NWDA i tu mogę zmodyfikować B o dowolną wielokrotność A.
Ta równość jest ubosta w algorytmie Euclidesa. Ponadto, jeśli C jest względnie pierwsze z A, matematycy piszą względnie pierwszość jako prostopadłość. Bo to jest dobry znaczek, który warto zrecyklować, bo wiadomo, że liczby to nieproste, które miałyby być prostopadłe. Wtedy domnażanie tego C tutaj nam w ogóle nie zmienia NWD. Jedno i drugie to jest no-brainer. to się dowodzi po prostu, albo się pamięta z wykładu. Ale będziemy z tego korzystać intensywnie co chwilę.
Więc jakby nam się cudownie udało udowodnić na przykład, że to jest nieparzyste, to ja bym stąd mógł odfaktoryzować dwójkę. Miałbym to 1 przez 2. Odjąłbym, miałbym KN i tu miałbym też KN. I byłbym zrobiony. No więc dowód, znaczy klasyfikacja takich przypadków przebiega z grubsza przez właśnie takie rozumowanie, tylko zrobione zrobione porządniej. Dobra, to powiedzmy, że ten nasz n to jest jakieś 2 do a razy m, gdzie 2 nie dzieli m. Z każdej liczby całkowitej mogę odfaktoryzować tyle dwójek, ile mogę i zostanie mi rwę nieparzysta.
K równe 0 ewidentnie nie działa. To akurat ma sens, ponieważ k równe 0 to jest wykładnik zerowy, czyli to jest x równe 1. k równego 0 jest nie. więc możemy k, jak każdą porządną liczbę większą, równą 1 napisać jako potęga dwójki razy coś nieparzystego no więc tu się robi ileś myślenie jak zrobić przypadki natomiast chciałbym to zmieścić tutaj bo potem nam się będzie mylić to jest oczywiście dla ogólnych abetu zbieżność nadzisk z tym jest przypadkowa nasze pytanie brzmi o to już zapamiętaliśmy zastanawiamy się kiedy dla n równego
Oddawać mi ten czołg długopis kiedy dla n równego 2 do a tej m i k równego 2 do b tej l kiedy zachodzi ta równość no to ja mogę napisać w terminach tych 4 literek k to jest 2 do b tej l plus n przez 2 czyli tu muszę zdjąć 1 z wykładnika to 2 do a tej m to miałoby być równe więc robimy przypadki przypadki zależą od tego kto ma więcej dwójek no i jak się najpierw nabazgroi na karteczce i jak rozwalić tam przypadki to potem wychodzi jakoś tak pierwszy przypadek a dobrze to potem i tak jeszcze zoptymalizowałem w porównaniu z tym co było w tym w tym na wirtualnej uczelni dobra to najpierw a mniejsze równe b
No bo widać, my chcemy stąd wyciągać dwójki. Chcemy ich wyciągnąć jak najwięcej, to chcemy zobaczyć, czy wyciągamy dwójki stąd, czy stąd. Teraz a jest mniejsze równe b, więc a minus 1 jest tym bardziej mniejsze równe niż b. Więc lewa strona tego mojego napisu to jest... A i oczywiście zachodzą jakieś takie no-brainery, jak to, że k a, k b. To się wyciąga przed nawias. Tu wyciągnę 2 do a minus 1. tu mi zostanie 2 do B minus A minus 1, czyli minus A plus 1 L plus M, a tu mi zostaje 2M.
No to teraz mamy taką sytuację, w której mamy jasność. B jest większy równe A. Ten wykładnik jest przynajmniej 1. To jest większy równe 1, więc ten ziomek jest parzysty, więc to wszystko jest nieparzyste. M było nieparzyste, tak samo jak L. Więc jak to jest nieparzyste, to ta dwójka tutaj, ona w ogóle nie ma znaczenia. Jak liczę NWD czegoś nieparzystego z czymś parzystym, to mogę odfaktoryzować dwójki, bo one i tak się nie liczą do NWD. No to to jest jawnym wzorem 2 do A minus pierwszej. To też możemy zrobić w pamięci.
To znaczy stwierdzić, że... To znaczy stwierdzić, że... Tu mam M, odejmę tutaj, to mi zostaje 2 do jakiejś potęgi L, NWD z M. Ale znowu, to jest to przeciwko M. Ta potęga dwójki nie gra. To mam takie coś. Prawa strona to jest, no wyciągamy mniejsze, wyciągamy 2 do A, zostaje nam M i 2 do B minus A razy L i znowu ten sam motyw co wcześniej, to jest nieparzyste, więc ta potęga dwójki nie ma znaczenia. Więc tu jest 2 do A, NWD, L, M.
No to widać, że nie ma bata. One nie są równe. Tu jest drugi przypadek. Jak a jest równe b plus 1, okazuje się, że też jest nie, ale z bardziej subtelnych powodów. No bo jak próbujemy robić to zrozumowanie za wcześnie, to nam nie wychodzi tak dobrze, że mam w tym nwd nieparzystą liczbę przeciwko parzystej. Jak podstawię a równe b plus 1, to ja mam jakiś taki napis, że tu mam 2 do b tej l plus 2 do a minus 1 to jest b plus 1, czyli tu jest 2 do b tej m o, 2 do plus pierwszej m to jest lewa strona i co się wyciąga przed nawias?
A priori się wyciąga 2 do b tej ale tu, spójrzcie, tu jest suma dwóch liczb nieparzystych stąd się zrobi gain jeszcze jednej dwójki mogę legalnie napisać liczbę l plus m przez 2 i to coś jest jak to porównamy z prawą stroną To jak to wygląda? 2 do b plus pierwszej liczba nieparzysta, 2 do b tej liczba nieparzysta. Takie rzeczy to już ujmiemy. To jest 2 do b tej razy lm. No i te rzeczy mogą być równe, to jest nieparzysta.
To jest też nieparzysta. To jest też nieparzysta. No to tak zwana waluacja 2-adyczna, czyli po prostu wykładnik, z którym dwójka dzieli jedną i drugą stronę, jest inny. Więc one nie mogą być równe. To się ogólnie nazywa new ze znaczkiem to jakaś liczba pierwsza od jakiegoś n to jest maksimum zbioru tych j że co? że q do j dzieli n więc tu możemy pompatycznie napisać, że waluacja 2 adyczna lewej strony jest równa 1 plus waluacja 2 adyczna prawej strony więc nie mogą być równe tu jest też nie trzeci przypadek kiedy, trzeci przypadek, kiedy A jest przynajmniej B plus 2. I teraz to B będzie rządziło
W byciu wyciąganym przed nawias, bo teraz nasza lewa strona to jest to jest co? Wyciągamy 2 do B. To jest najwięcej co możemy. 2 do B tej L plus 2 do A minus B minus 1 M. I tu jest 2 do A minus B M. No i teraz tak jak wcześniej. A minus B jest przynajmniej 2, więc minus 1 jest przynajmniej 1. To jest parzyste. To jest parzyste, to jest nieparzyste, więc to nie ma znaczenia, więc mamy tutaj surowego M, przy pomocy którego usuniemy to tutaj.
A prawa strona to gołym okiem widać, że to jest 2 do B razy 2 do A minus B. ML to jest parzyste, więc to jest 2 do B. Tak więc to jest jedyny przypadek, kiedy to się zgadza. Przy czym, tak na chłopski rozum, n jest większe od k, więc możemy się spodziewać, że to będzie dość często, bo b to jest ten wykładnik, z którym było k. Ale tak, to możemy napisać triumfalnie, że gcdkn jest równy gcdkn plus 2n, wtedy tylko wtedy, gdy i ten wykładnik 2 adyczny n jest większy niż wykładnik 2 adyczny k plus 2.
To jest ogólna charakteryzacja. I dla nas, jak n było równe 96, to się okazuje, że to się dzieje dla prawie każdego k. Dlaczego? No bo to jest 3 razy 2 do 5. Czyli a jest równe 5. Czyli to działa wtedy, gdy b jest mniejsze równa, a gdy b jest większe niż a-2. A-2 to jest 3, czyli ja potrzebuję, żeby b było równe 4, 5, ewentualnie 6.
I dla każdego z nich to się wypisuje zasobne. Jak mam b równe 4, to złymi liczbami są 16, bo 2 do 4 i nieparzyste wielokrotności szesnastki. Tu jest 3 razy 16 i tu jest 5 razy 16. Jak pamiętamy, że tu jest b, a to l ma być nieparzyste. Dla b równego 5 to mam 32 i 3 krotność 32, 96. tak, to w dalszym ciągu jest to w dalszym ciągu jest ja zależy kogo pytać w sumie tak, to jest tak g do 96 to jest 1 więc to jest powiedzenie, że 1 ma brak symetrii tak, to znaczy tak naprawdę mogę się tego pozbyć i powiedzieć, że co, że jest źle tylko gdy k jest równe 0 lub to wszystko k równe 0 to jest x równe 1 więc to odpowiada za to samo
Co k równe 96 i co? dla p równego 6 jest 64 czyli x dla których jest źle zauważcie, że k dla których jest źle to są 0, 16 32, 48 64, 80 to są po prostu wielokrotności 16 które się zmieściły które się zmieściły poniżej poniżej 96 no i x dla których jest źle to można sobie wypisać akurat my to kiedyś zrobiliśmy wolframem i to są te tutaj jak bym jeszcze był porządny to bym pamiętał który jest
Który z tych x jest równy 5 do którego k aż tak porządny nie jest coś tam widać prawda to znaczy 5 do zerowej to jest 1 5 do połówki to jest minus 1, a reszta wychodzi, jaka wychodzi. No więc praktycznie wszystko wiemy. To znaczy wiemy, że wiemy, jaka jest charakteryzacja. Ja po prostu muszę mieć dwójek o dwie mniej niż... Znaczy dobra, żeby było źle, to muszę mieć dwójek przynajmniej...
Znaczy muszę mieć ich więcej niż n minus 2, czyli muszę mieć przynajmniej tyle, co n dwójek minus 1. I byle jaką liczbę nieparzystą dokręcono do tego. Więc wychodzi na to, że tutaj to był szczęśliwy przypadek. To znaczy, gdyby na przykład to było tak, że a minus 2 jest równe 0, to tych wykładów możliwych by jest wielkie mnóstwo, tyle co liczby nieparzystych, które się mieszczą w zakresie.
My po prostu mieliśmy farta, że mieliśmy dużą potęgę dwójki przeciwko małemu dopełnieniu. Dla nas to m był równe 3. Uważny słuchacz zastanowi się, zaraz, zaraz, ale my wzięliśmy logarny dyskretny przy podstawie 5. Jest mnóstwo innych generatorów. Ogólnie trudno się przekonać, że 5 do dowolnej potęgi względnie pierwszej z p-1 też jest generatorem. A ciąg wykładników jest taki sam zawsze. I ciąg x jest taki sam. No więc wyjaśnienie tego fenomenu jest takie, że po pierwsze nie ciągł tylko zbiór, po drugie tak, istotnie, to jest tak dobrany zbiór, że dowolny generator o tych wykładnikach to jest jakaś permutacja tego, a dlaczego tak jest, to niech na razie pozostanie tajemnicą, dopóki się nie douczymy więcej o tym, jak działają całe skończone. Dobrze. No więc.
Coś policzyliśmy na karteczce. Problem jest taki, że nasze liczenie bywa omylne, więc możemy jeszcze zatrudnić kłopot rama, żeby nam powiedział, że się nie pomyśliliśmy. Co będzie wymagało wyklikania paru rzeczy? I teraz powinno być widać. Dobrze. No więc. To jest trochę bardziej uborządkowane w porównaniu z tym, jak to robiliśmy wcześniej. To jest funkcja, która produkuje rząd modułu P, które jest napisane w taki swęcy sposób, że za każdym razem jak o, odwiedźmy kursor za każdym razem jak x do j tej moduły p jest jedynką to wrzuć do listy j, a jak nie to p-1, który jest sztucznie duży przejść we wszystkich j nie od z, tylko od jedynki i weź z tego najmniejsze te p-1 nie zaburzą niczego bo i tak to wszystko jest mniejsze, równe niż p-1.
Mógłbym tutaj napisać infinię zamiast p-1. A, no, także tak. To złapie najwcześniejszego j, dla którego to jest 1. Będę pokazać jeszcze raz przejwagłować. I jest tabelka rzędów osiąganych przez na przykład przez gizmo do 36. No i jest taka, jakiej się można spodziewać, to znaczy są same dzielniki 36. Znaczy, dobra, modulo 37 a rzędy są dziennikami 37 minus 1. Tu jest ta sama funkcja napisana na inny sposób, na taki jak robiliśmy to wcześniej, z tym pozytywnym nawodem flatem.
No i jest sprawdzenie, że one działają tak samo. To jest najprostsza możliwa funkcja, która sprawdza, czy dla jakiegoś konkretnego x jest ta własność symetrii, której szukamy. I my to chcemy porównywać przeciwko temu naszemu, temu co nam wyszło z liczenia o. Do tego chcemy umieć napisać szybko funkcję, która patrzy z jakim wykładnikiem dwójka dzieli k. To się po prostu nazywa interior exponent.
Jak jest taki iloczyn, to on po prostu sczytuje wykładnik przy dwójce. Dobrze. Tu jest sprawdzanie warunku. Nie będąc pewny jak ta funkcja działa dla zera, dopisałem, że ma warunek z automatu niespełniony dla k równego zero. Oprócz tego to co mieliśmy napisane. To jest funkcja, która znajduje generator. Jest ta sama sztuczka, co tam wcześniej z tym p-1, który miał być sztucznie duży. To znaczy, przechodzimy przez wszystkie x. Jeśli jakiś x ma rząd p-1, czyli jest generatorem, to wpisz do listy x. A jak nie, to nieskończoność.
Więc w liście pojawią mi się nieskończoności oraz wartości tych x, które są generatorem. Więc dla ustalenia uwagi wezmę najmniejszy. Najmniejszy generator modułu 97, tak jak nam wcześniej wychodziło, jest równy 5. Więc jak teraz patrzymy? Przewijam na jednym ekranie, a nie na drugim. Screenshare'owanie przez TeamViewer jednak nie jest idealne. W każdym razie.
Tu, co się tutaj dzieje? Ja patrzę, ustalam P. Patrzę, dla których X jest spełniony ten warnek semestri, którego poszukujemy. To jest jakaś tabletka. X są indeksowane od 1. od jedynki, tutaj to jest ważne. Patrzę na których pozycjach w tej tabelce jest prawda, czyli patrzę na x, dla których zachodzi symetria, a potem jeszcze zatenuję, żeby zabrać nawiasy, które wychodzą z tej funkcji position. I z tego coś wychodzi. To jest lista tych x, które są dobre. Ja bym chciał te x, które są złe, to są dokładnie te x, które nam, które wypisaliśmy jako złoczyńców.
Tutaj, przez jakiś czas sobie wyrywałem włosy z głowy, dlaczego mi nie wychodzi dobrze. Otóż dlatego, że to, to się numeruje od zera. To jest prawie tak jak to, sprawdzając nasz śmieszny warunek, modulo, znaczy ten, z gcd z p-1, tylko, że tutaj to wszystko żyje od zera. Więc pozycje w tej tabelce, na których jest true, to k równemu 0 odpowiada pozycja pierwsza. k równemu 2 odpowiada pozycja znaczy 1 odpowiada pozycja druga k równemu 2 odpowiada pozycja trzecia więc żeby odzyskać k to od pozycji muszę odjąć jedynkę i wychodzi takie coś oczywiście te listy nie mają powodu mieć ze sobą nic wspólnego ponieważ są w innych jednostkach to jest w jednostkach x a to jest w jednostkach k to są liczby a to są ich logorytmy dyskretne w związku z tym to co robimy to bierzemy 5 do potęgi out 78 i jak to posortujemy to się okazuje, że to jest to samo
Co tutaj, czyli że 77 ma być równe 80. To sprawdźmy. Mogę jeszcze dla ustalenia uwagi sprawdzić jak to jest dla innego generatora. No patrzcie, jak ja mam ogólnie listę generatorów moduł 97. Oto. Ach! Bo ja miałem taki napis tutaj, dobrze. Tu już napisałem minimum. Dobrze, to na szczęście Tak definiujemy listę generatorów, w dalszym ciągu jest 5, a cała lista to jest taka, gdzie nieskończoność traktujemy jako, że nie ma czegoś na liście, w sensie, że dana liczba nie jest generatorem, więc równie dobrze generatorem jest 29.
No to kto Boga temu zabroni. Sprawdźmy czy tak samo jak podnosimy inny generator modulo 97, ta sama lista. Tylko, że przepermutowana. To dla ostatecznego spokoju sumienia. To właśnie mi zgubiło kursor. Do ostatecznego spokoju sumienia chciałem to sprawdzić dla dużej liczby liczb pierwszych. To robimy to tak.
Zliczamy ile razy coś poszło nie tak. Zliczamy liczby pierwsze od drugiej, bo dwójka jest nieinteresująca. Musimy to liczyć od trójki. I weźmy pierwszych, nie wiem, 100 liczb pierwszych. P to jest właśnie liczba pierwsza o numerze od 2 do 100. G to jest najmniejszy generator dla ustalenia uwagi. K jest 0, bo patrzymy na wykładniki. To teraz patrzymy w tym zakresie, w którym żyją wykładniki przy generatorze. czy ten jeden warunek to znaczy symetria k tej potęgi generatora modulo p zgadza się z tym czy jest spełniony ten warunek z występowaniem dwójki w rozkładzie odpalony na p-1c i k prosty warunek na wykładniku to jest ten śmieszny symetryczny warunek na rzędach dla potęgi i jeśli tu nam coś pójdzie nie tak to zwiększamy licznik fejli przechodzimy te pętle po wszystkich k od 0 do p-2 tu się nam kończy ta ta pętla czemu on to tak dziwnie koloruje
To jest jeden while no dobra, no i to mamy zrobione dla jednej liczby pierwszej a ta pętla po prostu przechodzi przez kolejne liczby pierwsze więc tu musi zwiększać counter liczby pierwszej więc bardzo mi się nie podoba to że to się tak długo liczy wcześniej to się liczyło dużo szybciej Niech zrobię tego mniej. Zero fail. Być może liczenie tego... Ogólnie to jest hiper nieoptymalnie napisane wszystko. To w ogóle ja powinienem dostać zakaz pisania czegokolwiek za pisanie programu w ten sposób.
Tak? Ta funkcja to się jeszcze prosto liczy. Natomiast funkcja ord choć to jest takie nieoptymalne. Niech zrobimy tego trochę więcej. To w dalszym ciągu jest zero fail. Mogę mu robić wydruki kontrolne i zobaczyć jak szybko to idzie, na czym się zacina. Bo ja mam tutaj dwie pętle, od P i po K. Więc ja zawsze tu mogę zrobić... Ciekawe czy Wolfram rozumie stringi. No patrzcie, rozumie.
Tu mogę mu dać wydruku. K równa się. Patrzcie, on koloryzuje stringi na szaro, żeby człowiek wiedział, że jak użyje jakiegoś znaku zawartości stringa, który jest zmienną, to nie zostanie potraktowany jako zmienna. To zaczyna od wydrukowania k równego 0. Ja zastanawiam się, że tu chcę wydrukować i czy modulopę. Dlaczego on tutaj drukuje 0?
Tak, i on to po prostu idzie, bo to jest bardzo mocno nieoptymalnie napisane. Tylekoron oczywiście jest nie lepszy niż kwadratowy. Natomiast on liczy rzędy bardzo brutalnie. Liczenie rzędów się daje zrobić dużo szybciej. Wystarczy na przykład wziąć tak jak my zrobiliśmy. Ale to było bardziej sprawdzenie, czy nie walnęliśmy się gdzieś tam w skład. Znaczy, czy funkcja napisana w terminach rzędów jest tym samym, co funkcja napisana w terminach wykładników. I wychodzi na to, że tak.
No więc tak. Generalnie jakbyśmy chcieli to sprawdzić do jakiejś innej liczby. Na przykład to 36 było dość obiecujące, bo 37 jest liczbą Pierwsza na 36 ma dużo czynników, ale niewiele więcej, z czym absolutnie nic nie zabroni sprawdzić dla 36. Wziąć sobie te dwie komendy, odpracować tę komórkę. Jak ja wezmę 37, tu jest tu gdzie jest dobrze, tu jest tu gdzie na wykładnikach jest dobrze.
Generatory modlo 37. Przykład 2 jest generatorem. zawsze miło mieć dwójkę jako generator to zawsze mogę podnieść 2 do potęgi output numer 104 zrobić tym moduł o 37 no i jako żywo jest to to samo co out 103 działa