Najdłuższa i największa liczba pierwsza

[KopalniaWiedzy.pl 355]

Curtis Cooper z Uniwersytetu Środkowego Missouri odkrył największą jak dotąd liczbę pierwszą, składającą się z 17.425.170 cyfr. Poprzednia, opisana w 2008 r., rekordzistka była sporo krótsza: zapisywało się ją za pomocą 12.978.189 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 2^p - 1, gdzie p jest liczbą naturalną). Podobnie jak poprzedniczka, ujrzała ona światło dzienne dzięki sieci komputerowej Great Internet Mersenne Prime Search (GIMPS), na którą składa się obecnie ok. 360 tys. procesorów.

Odkryta liczba została powtórnie sprawdzona przez kilku naukowców posługujących się innymi komputerami. Koniec końców zapewniła ona doktorowi Cooperowi nagrodę GIMPS-u w wysokości 3 tys. dol.

[Axles 0]

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.

[MrVocabulary (WhizzKid) 56]

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?

[dexx 40]

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

[MrVocabulary (WhizzKid) 56]

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

[Dyskutant 3]

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

[MrVocabulary (WhizzKid) 56]

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...

[wilk 103]

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.

[MrVocabulary (WhizzKid) 56]

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

[wilk 103]

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.

[MrVocabulary (WhizzKid) 56]

Aha, i wszystko jasne, dzięki

[wilk 103]

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.

[Shellest 0]

"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)

[kretyn 4]

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.

[wilk 103]

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