Pytanie o PROSTE metody określania czy b. duża liczba jest pierwsza

[Paragraf 22]

Chodzi o 2 aspekty:
żeby łatwo było zaimplementować
żeby dawały pewność, gdy "Tak - jest pierwsza", bo na "nie" to chyba zawsze jest pewność?

[Brombal]

https://pl.wikipedia.org/wiki/Test_pierwszo%C5%9Bci
Implementacje AKS są dostępne ale są niezbyt profesjonalnie zrobione. Niektóre uczelnie maja porządne ale niedostępne dla szaraczków.

[c-rasz]

link

Nie używaj zewnetrznych linków, bez "oprawienia ich w ramki" klawiszem [code] link [/code]

A co do Wiki, to w takich wypadkach nie należy korzystać ze źródeł aborygeńskich, tylko z takich, gdzie grono wikipedystów jest jak największe.
Wikipediuję co-nieco, i nasz zespół krajowy niezbyt jest doborowy, niestety...

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Primality_test

A poza tym to jakieś testy powinny być w MathWorld czyli u Wolframa

Kod: Zaznacz cały

https://www.wolframalpha.com/

Przyznam bez bicia, że wiele z tych testów, to dla mnie czysta 汉语语言 — a trochę temat znam.

Nie jestem matematykiem, typowy outsider ze mnie, więc łykam wybiórczo to, co mi wchodzi, a 汉语语言 przelatuję wzrokiem nieobecnym...

Tym niemniej jako amator, outsider, musiałem z konieczności do wielu rzeczy dochodzić sam, i to często lewą nogą, za prawe ucho, ale... Ale chyba wyszło mi to na +!

Nie głaskało mnie Życie po głowie
nie pijałem ptasiego mleka
no i dobrze, no i na zdrowie!
(tak wyrasta się na Człowieka!)
⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ [ Władysław Broniewski ]

Jeżeli temat p-liczb Cię interesuje, to witaj w klubie! Niezbyt jest liczny, no niezbyt...
A które aspekty uważasz za sexy?

Jeśli chodzi o badanie prymarności to opisałem tu dwie metody, dobre na liczby b. duże:
moje Rzeszoto, o którym na forum pisałem kilkakroć, ale potem zrobiłem implementację w Excelu, omawiam to w temacie crashowanie liczb pierwszych —

[Paragraf 22]

No cóż, dziękuję za zaproszenie do klubu, ale na tematyce liczb pierwszych znam się słabo, to jest dla mnie temat poboczny: wypłynął mi przy moim zainteresowaniu kryptologią. Bo w kryptologii i w kryptografii liczby pierwsze to narzędzie bardzo ważne. Można więc rzec, że traktuję liczby pierwsze czysto instrumentalnie.

Natomiast ty, jak widzę, siedzisz w temacie dosyć głęboko, i zajmujesz się tymi aspektami sprawy, na których nie znam się wcale. Tym niemniej zauważyłem coś, co chyba ci umknęło, co dotyczy opisanego przez ciebie "primorial sieve":
- W kryptografii znaczenie podstawowe mają iloczyny liczb pierwszych dużych, i do wykrywania podzielności tego typu liczb, twoje narzędzie wydaje się być niewystarczające. Jak sam piszesz w innym miejscu, funkcja primorial rośnie bardzo szybko, co w pewnym stopniu komplikuje obliczenia. W swoich przykładach doszedłeś do primorial liczby 11, i już na tym poprzestałeś, zapewne właśnie z powodu tego, że wykraczało to poza dokładność Excela. Ponieważ do zagadnienia psu na budę nadają się zaokrąglenia...
Oczywiście w kryptografii nikt na Excelu tego nie pisze, używa się zaawansowanych, często nawet dedykowanych języków programowania, a kiedy trzeba to i asemblera. Wtedy można operować liczbami o milionach cyfr, o ile zajdzie taka potrzeba.

BTW. Z tego co gdzieś wyczytałem, największa obecnie znana liczba pierwsza, tak zwana liczba Mersenne’a — ma prawie 25 milionów (sic!) cyfr. Toż to весь толстый book, kilkaset stron! No i tak ciekawi mnie, jakimi metodami dowiedziano tego, że jest liczbą pierwszą. No bo przecież nie poprzez wykluczenie wszystkich jej ewentualnych podzielników?

No i tu wracamy do mojego pytania, czy są metody dające stuprocentową pewność, że liczby zbliżonego rzędu wielkości, milionocyfrowe - są liczbami pierwszymi? Decydujące znaczenie ma też to, aby w przeciwnym wypadku, gdy liczba jest złożona - metoda umożliwiała znajdywanie bardzo dużych (dwóch co najwyżej!) podzielników, o ilości cyfr do siebie zbliżonej. Czyli mające mniej więcej połowę długości liczby testowanej. Bo tym w tej chwili najbardziej się zajmuję, a literatura jest dość skąpa, i nie dziwota, bo zdaje się, że wszystko na ten temat jest po prostu utajniane, nawet jeżeli napisze to cywil:
Wielki Brat bez trudu potrafi zniknąć ze wszystkich serwerów dowolny tekst, który ma duże znaczenie militarne. No, przynajmniej bardzo się stara: internet pełen jest tak wielu różnych zakamarków, a nawet istnieje takie pojęcie jak darknet - że nikt z zewnątrz nie jest w stanie się dowiedzieć niczego, co tam się dzieje. Natomiast, co dziwne, nigdzie nie natknąłem się na słowo darknety (chodzi o liczbę mnogą), a przecież na pewno nie powinno się mówić o jednej takiej sieci, na bank jest ich mnóstwo.

No i tu dotykamy kwestii szyfrowania, która ma znaczenie w owym kontekście wielce istotne: aby uniknąć wścibstwa osób niepowołanych, szyfrowanie to sprawa fundamentalna. A z tym szyfrowaniem to bywa dosyć dziwnie, a nawet bardzo dziwnie. Wyobraźcie sobie, że w Stanach Zjednoczonych wprowadzono ustawowo, ustawowo wprowadzono zakaz używania przez obywateli USA programów do szyfrowania wyprodukowanych poza granicami kraju.

Może nie każdy załapał, to wyłożą tą łopatologicznie: skąd ten zakaz płynie, i jak należy jego znaczenie odczytać? Według mnie istnieje tylko jedno wytłumaczenie, które jest wytłumaczeniem logicznym, które jest wytłumaczeniem wyjaśniającym przyczyny, oraz cel. Otóż istnieje takie określenie jak back-door, czyli drzwi kuchenne (w odróżnieniu od wejścia drzwiami frontowymi), niektórzy mówią wejść od zakrystii. Co określenie oznacza? Otóż autorzy dowolnego programu szyfrującego, mogą całkiem bezkarnie umieścić w nim właśnie taki back-door, tylne drzwi, dzięki którym są w stanie odczytać zaszyfrowany tym programem tekst, nawet nie mając do niego klucza! Po prostu wchodzą przez drzwi kuchenne, i zaraz za nimi klucz jest schowany pod wycieraczką.

Czaicie bazę? Każdy komercyjny program szyfrujący ma drzwi kuchenne, każdy! Dlatego jeżeli chce się być bezpiecznym, to nie należy szyfrować oryginalnego tekstu, tylko wstępnie go zaszyfrować metodami chałupniczymi, i to nie jedną, tylko zastosować kolejno trzy metody szyfrujące, różniące się od siebie, i oczywiście wyposażone w różne klucze. Nie muszą to być metody bardzo wyrafinowane, przy zastosowaniu piramidy trzech metod szyfrowania, oraz trzech kluczy, prawdopodobieństwo złamania takiego szyfru wynikowego - jest jak jeden do biliona bilionów...


Detale na priv!

[Brombal]

Metody deterministyczne dają pewność. Np. test AKS. Być może do złamania szyfrowania RSA ktoś wymyślił metodę faktoryzacji dla liczb gładkich (bo takie są stosowane). Albo komputer kwantowy. Gdybyś miał dobry program do testu AKS to poproszę. Poszukuję od lat ale wszystko siermiężne.

[c-rasz]

(...) ktoś wymyślił metodę faktoryzacji dla liczb gładkich

B-gładkich... Jak raz to wydaje mi się stosunkowo łatwe: gdy znamy wartość B — to i wiemy, jak spowodować, że komputer będzie liczył w określonej ilości iteracji, a to ważna wiedza...

Albo komputer kwantowy.

Eeeh, marzenie! Wg. mnie, zamiast na ITER, Very-LHC czy kolejny HST (teleskop kosmiczny) — całą kasę należałoby włożyć w badania nad takim komputerem, i rozwój 𝑎𝑟𝑡𝑖𝑓𝑖𝑐𝑖𝑎𝑙 𝑖𝑛𝑡𝑒𝑙𝑙𝑖𝑔𝑒𝑛𝑐𝑒, przecież zmiast robić eksperymenty w realu — łatwiej, taniej, i milion razy szybciej — da się to wyczaić w symulacjach!. Teleskop Webba miał kosztować miliard $, a skosztowano go za sumę (bagatela!) DZIESIĘĆ razy większą, skandal!

Gdybyś miał dobry program do testu AKS to poproszę. Poszukuję od lat ale wszystko siermiężne.

Jeżeli "wszystko siermiężne" to jest interes do zrobienia, wystarczy się nad problemem "pochylić" — Luuudzie, pieniądze na ulicy leżą! Czyli: napisz dobry program, naprawdę dobry, a potem zbieraj lajki na Facebooku, a na sprzedaży zbieraj na własną wysepkę na lewantyńskich wodach, hę?

Dodano po 27 minutach 58 sekundach:
Paragrafie — Twoje spostrzeżenie zmartwiło mnie, przyznam, poczułem nagle wielki zawód, bo myślałem, że znalazłem narzędzie uniwersalne, a wygląda na to, a raczej wyglądało (o tym za chwilę), że selekcja, jaką się prowadzi, przy niezbyt wysokim primoriale podstawowym, wprawdzie faktycznie eliminuje liczby złożone — ale wyłącznie z pewnego zakresu modulo, to znaczy liczby podzielne przez niezbyt duże liczby pierwsze.

Skoro to zauważyłeś (zostawiając mojemu domysłowi detale, ale załapałem!), to nie będę sprawy tłumaczył Tobie, ale na użytek kogoś, kto nie dostrzega rzeczy, o której mówisz. Otóż:

1. W sposób oczywisty eliminowane są liczby podzielne przez dowolną z liczb pierwszych primorial tworzących, czyli dla liczby ⁣ ⁣11# ⁣ ⁣⁣ ⁣będą to liczby \(\displaystyle{ 2;⁣ ⁣ 3; ⁣ ⁣5; ⁣ ⁣7; ⁣ ⁣11}\)

Ponadto będą eliminowane również i liczby złożone, podzielne przez wyższe liczby pierwsze, mianowicie z zakresu 11 — \(\displaystyle{ 11}\)#, i chociaż ta ostatnia wartość jest już dosyć spora, to jedynie dla zwykłych zjadaczy chleba, a nie dla badaczy liczb pierwszych, dla których zabawa zaczyna się dopiero wtedy, gdy liczba ma znacznie ponad \(\displaystyle{ 10k}\) cyfr

A tymczasem liczby Double Precision oznaczają ich zapis w systemie dwójkowym na czterech bajtach, czyli na 64 bitach. 2 do potęgi 64 daje nam 19 cyfr dziesiętnych — co wytrawni łowcy naprawdę dużych liczb pierwszych — skwitują krótkim: phi...

Niektóre implementacje Fortranu dopuszczały format liczb \(\displaystyle{ REAL*16}\) czyli 128 bitów, co w systemie decymalnym daje 38 cyfr: Phi!

(No cóż, wychowałem się w epoce DOS-a łupanego... Zarzucę więc ten temat, bo się po prostu na tym nie znam)

Konsekwentnie omijając to, na czym się nie znam, powiem, że znalazłem pewne umiarkowane lekarstwo, na wskazaną przez ciebie wadę. Przypomnę, że w tym pierwotnym tekście stwierdzałem z buta, że należy konsekwentnie stosować coraz wyższe primoriale, tak, jak rośnie apetyt w miarę jedzenia. Ale przecież można je po-sekwencjonować:

Wpierw jako podstawę algorytmu bierzemy primorial liczby p, i dokonujemy za jego pomocą wiadomych operacji. Jest pewna nadzieja na jakiś tam odsiew, ale nadzieja ta duża nie jest.

W następnym kroku, zamiast podnosić poprzeczkę primorialu, bierzemy liczbę wyższą od p, (oznaczmy ją q) — i stosujemy wzór następujący:

#\(\displaystyle{ qp}\) = \(\displaystyle{ \frac{Q-hash}{P-hash} }\) dzieląc dwa primoriale (gdzie \(\displaystyle{ q > p}\))

(zwracam uwagę, że znak # poprzedza DWIE liczby, na których on operuje. Nie jest to więc funkcja primorial, lecz funkcja nowa, nazwę ją prowizorycznie "awangarda", ze względu właśnie na owo "poprzedzanie")

Równanie to, tłumacząc na język potoczny oznacza, że nie wymnażamy liczb pierwszych od dwójki, aż do podstawy primorialu, lecz wymnażamy wyłącznie liczby pierwsze zaczynając od \(\displaystyle{ p}\), zaś na \(\displaystyle{ q}\) kończąc...

Oczywiście otrzymamy w wyniku liczbę dużą, ale jej wielkość możemy kontrolować, odpowiednio dobierając \(\displaystyle{ Δpq }\) — czyli jak odległe, o ile większe od \(\displaystyle{ p}\) ma być \(\displaystyle{ q}\), a więc ile kolejnych liczb pierwszych, dosyć już dużych, będziemy przez siebie wymnażać, odrzucając balast jakim była liczba równa \(\displaystyle{ p}\)#

Następnie stosujemy znaną już procedurę dzielenia, oraz odrzucania tych liczb, które zostaną wskazane jako złożone.

W kolejnym kroku podnosimy sobie poprzeczkę, ale (i tu posłużę się pewnego rodzaju przenośnią) podnosimy też i podłogę, z której będziemy poprzeczkę atakować, czyli bierzemy takie \(\displaystyle{ r,}\) żeby nie było za duże, i wyliczamy sobie według znanego już wzoru:

#rq = r#/q#

Gdzie tym razem \(\displaystyle{ Δ qr}\) dobierzemy mniejszą, ponieważ mamy do czynienia z większymi liczbami.

No i tak implementując to w odpowiedniej pętli, możemy spowodować, że program nie będzie musiał wykonywać zbyt dużych dzieleń, dzięki czemu będzie działał szybciej.


Program będzie musiał mieć dostęp do bazy danych, zawierającej pełne zestawienie dużych liczb pierwszych z interesującego nas przedziału. Jak dużych? Ano zawierających się w przedziale od \(\displaystyle{ q}\)# aż do \(\displaystyle{ r}\)#

Zaś by to miało sens, abyśmy nie powielali błędów popełnionych przez innych — zestawienie tych p-liczb musi być kompletne, to znaczy muszą tam być WSZYSTKIE kolejne liczby pierwsze. Jakiekolwiek "dziury" są niedopuszczalne, ponieważ spowodują, że i nasze obliczenia nie będą prawidłowe.

⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣No, i to by było na tyle...

Dodano po 1 dniu 13 godzinach 12 minutach 5 sekundach:

[1. ] żeby łatwo było zaimplementować

Nie wiem, czy mój pomysł, z użyciem funkcji 𝐕𝐚𝐧 — spełnia ten warunek, być może są sposoby prostsze, zerknij:
dyskusje-o-matematyce-f76/nowa-funkcja- ... 56965.html

[2. ] żeby dawały pewność, gdy "Tak - jest pierwsza"

— Primorial sieve wraz z funkcją 𝐕𝐚𝐧 — jak najbardziej dają pewność całkowitą...

Ale powinno być i proste, posuwamy się bowiem odmierzonym, zadanym krokiem, w butach dokładnie \(\displaystyle{ 7}\)-milowych, od \(\displaystyle{ p₀,}\) do \(\displaystyle{ p₁}\), potem do \(\displaystyle{ p₂}\), aż dotuptamy do \(\displaystyle{ p_{n} }\), większego od liczby badanej, i to jest moment STOP-u programu, jak wujcio Turing zalecał...

[Paragraf 22]

No, looks good, ale jakość wyjdzie w praniu. Lecz choć napaliłem się jak łysy na grzebień, to póki co muszę temat odłożyć, bo zasiedziałem przed kompem za długo, a życie ma swe oczekiwania również i w realu...

Zresztą i kolega, z którym temat rozgryzamy - też musiał się wymiksować, bo mu parę rzeczy już w kolejce do ogarnięcia stoi, a to on jest głównym magikiem od programowania, bo ja to tylko trochę koduję, raczej teoretyzuję...

Przewidujesz napisać to w formie użytkowej? Fajnie by było, zamienić teorię w działający soft! Może nawet kasa jaka by za to popłynęła, kto wie...