Najdłuższa i największa liczba pierwsza

Gdzieś kiedyś czytałem o wzorze na liczbę pierwszą 2don -1, ale nie pasuje mi to dla 2do4 gdzie wychodzi 16 - 1 = 15 a to nie jest liczba pierwsza.

Dlaczego jest taki duży rozstrzał między obecną a poprzednią rekordzistką? Oni zgadują te liczby, zamiast je sprawdzać po kolei? W ogóle zastanawia mnie, jakie są zastosowania tak dużych liczb pierwszych - ktoś się orientuje?

O zastosowaniu jest napisane w artykule "Koniec końców zapewniła ona doktorowi Cooperowi nagrodę GIMPS-u w wysokości 3 tys. dol."

Taka kwota za takie osiągnięcie to w zasadzie niewiele więcej, niżby dostał w Polsce - powiedzmy, że to zawsze coś

Gdzieś kiedyś czytałem o wzorze na liczbę pierwszą 2don -1, ale nie pasuje mi to dla 2do4 gdzie wychodzi 16 - 1 = 15 a to nie jest liczba pierwsza.

Dlaczego jest taki duży rozstrzał między obecną a poprzednią rekordzistką? Oni zgadują te liczby, zamiast je sprawdzać po kolei?

n musi być liczbą pierwszą, a i to nie gwarantuje, że otrzymamy liczbę pierwszą, np. dla n=11

n musi być liczbą pierwszą, a i to nie gwarantuje, że otrzymamy liczbę pierwszą, np. dla n=11

No tak, ale pierwsze numeri primi są dość blisko siebie, dlaczego po prostu nie brać każdej liczby po kolei i sprawdzić, przez co się dzieli? Chyba że ten rozstrzał rośnie np. liniowo czy arytmetycznie, z tym 5 milionów cyfr różnicy wydaje mi się przedziałem, w którym można by było znaleźć kilka liczb pierwszych...

dlaczego po prostu nie brać każdej liczby po kolei i sprawdzić, przez co się dzieli?

Ponieważ test pierwszości trwa że ho-ho. Co dopiero iteracyjnie każdą kolejną. W takim przypadku RSA nie miałoby racji bytu.

To w takim razie jak wybierają kandydatów do testowania?

Sprawdzają kolejne (praktycznie są to także liczby pierwsze) wykładniki i to stąd ten rozrzut. Liczby wygenerowane ze wzoru Mersenna dają znacznie większą szansę trafienia liczby pierwszej niż test kolejnych liczb.

Aha, i wszystko jasne, dzięki

Zresztą mało medialne jest znalezienie l.p. większej od poprzedniej o np. 2, skoro od razu można znaleźć dłuższą o milion cyfr.

"By uzyskać liczbę Coopera, należy podnieść dwójkę do potęgi 57.885.161. i odjąć jeden (to 48. liczba Mersenne'a, a więc liczba postaci 2p - 1", gdzie p jest liczbą naturalną)."

To chyba pomyłka, a przynajmniej skrót myślowy - omawiana liczba to 57 885 161-sza liczba Mersenne'a, nie 48. Zapewne chodziło o "jest to 48. liczba pierwsza Mersenne'a" (bo przecież nie każda liczba Mersenne'a jest liczbą pierwszą).

(edit: właściwie niby niektóre definicje, tak w każdym razie mówi wikipedia, dopuszczają zdefiniowanie liczby Mersenne'a jako "liczby pierwszej postaci 2^p - 1". Ale wtedy i tak powyższy tekst będzie niespójny)

Dlaczego jest taki duży rozstrzał między obecną a poprzednią rekordzistką? Oni zgadują te liczby, zamiast je sprawdzać po kolei? W ogóle zastanawia mnie, jakie są zastosowania tak dużych liczb pierwszych - ktoś się orientuje?

Liczby pierwsze są bardzo ważne w kryptografii, polecam wpisać w google 'kryptografia liczby pierwsze'. Od razu wyskoczy algorytm RSA - http://pl.wikipedia.org/wiki/RSA_%28kryptografia%29 .

Mnie najbardziej zastanawia jak oni zapisują te liczby w komputerze. Taka wielka precyzja wymaga opracowania całej nowej architektury i logiki liczbowej. Wszystkie operacje będą trwać zdecydowanie dłużej niż to się robi z 'naszymi' liczbami - pojedyncza lub podwójna precyzja.

Mnie najbardziej zastanawia jak oni zapisują te liczby w komputerze. Taka wielka precyzja wymaga opracowania całej nowej architektury i logiki liczbowej. Wszystkie operacje będą trwać zdecydowanie dłużej niż to się robi z 'naszymi' liczbami - pojedyncza lub podwójna precyzja.

http://en.wikipedia.org/wiki/Bignum