9 miesięcy temu

Udało się odkryć kolejną liczbę pierwszą!

liczby-pierwsze

Odkryta w ubiegłym miesiącu liczba, jest największą znaną dotąd liczbą pierwszą – jej zapis składa się z 22 milionów cyfr! Jej wartość można zapisać jako:

najwieksza-liczba-pierwsza

Odkrycia dokonał profesor matematyki z Uni­ver­sity of Cen­tral Mis­souri Curtis Co­oper, mnożąc ze sobą 74,207,281 dwójek i odejmując na końcu od wyniku jedynkę. Następnie otrzymaną liczbę przetestował, czy nie jest podzielna przez inną liczbę poza samą sobą oraz jedynką – zgodnie z definicją liczb pierwszych. Sprawdzenie tego zajęło mu aż 39 dni obliczeń!

Naukowca można nazywać prawdziwym pogromcą liczb pierwszych – odkrył ich już cztery, w tym również przedostatnią odkrytą 3 lata wcześniej, ale krótszą o 5 milionów liczb…

Jest to zaledwie piętnasta liczba pierwsza odkryta w przeciągu 20 lat trwania projektu GIMPS, który łączy 360 tysięcy procesorów na całym świecie w ich poszukiwaniu. Mimo iż zgodnie z twierdzeniem Euklidesa, liczb pierwszych jest nieskończenie wiele, ich poszukiwania są niezwykle trudne – im większe wartości liczbowe tym rzadziej zaczynają się one pojawiać.

Dodatkowo, im większa wartość liczby tym dłuższy czas weryfikacji wszystkich potencjalnych dzielników.

liczby-pierwsze-1

Dlaczego liczby pierwsze są tak istotne?

Po co w ogóle bawić się w żmudne poszukiwania liczb pierwszych? Ponieważ mają one istotne zastosowanie w tworzeniu algorytmów kryptograficznych, czyli w kodowaniu. Bezpieczne kodowanie przekłada się m. in. na możliwość dokonywania transferów pieniężnych, czy użycia numerów PIN w kartach płatniczych.

Słabą stroną procesu kodowania jest konieczność przekazania klucza deszyfrującego – niesie to za sobą ryzyko, że może on zostać przechwycony. Pod koniec lat 70-tych udało się opracować metodę, która eliminowała ten problem nazywaną w skrócie RSA. Polega ona na tym, że wybiera się trzy liczby: A, B i C nazywane „liczbami magicznymi”. Dwie z nich (A i B) służą do zaszyfrowania informacji, natomiast rozszyfrowanie możliwe jest tylko przy pomocy kombinacji liczb A i C. To powoduje, że konieczne staje się zabezpieczenie przed ujawnieniem tylko jednej z trzech liczb.

Każdy szyfr jest jednak możliwy do złamania. Aby temu zapobiec, do tworzenia liczb magicznych, używa się liczb pierwszych, które po pomnożeniu dają wynik ponad stucyfrowy. Rozłożenie takiego wyniku na czynniki pierwsze i odkrycie liczb magicznych, trwałoby miesiące, jeśli nie lata.

Do poszukiwania kolejnych liczb pierwszych zachęcić ma nagroda wysokości 150 tysięcy dolarów, ufundowana przez organizację pozarządową Elec­tronic Fron­tier Fo­un­da­tion, za odkrycie liczby pierwszej składającej się z ponad 100 milionów cyfr.

Poszukiwania liczb pierwszych mogą zostać przyspieszone, dzięki komputerom kwantowym, które nieporównywalnie szybciej dokonują obliczeń. Tradycyjny procesor rozróżnia jedynie dwie wartość „0” lub „1”, komputery kwantowe posługują się natomiast kubitem, jednostką która opisuje różne superpozycje stanów kwantowych, a więc wiele różnych możliwości na raz. Aby określić wynik, komputer kwantowy dokonuje za jednym zamachem całej serii różnych pomiarów.

Komputery kwantowe przyśpieszają obliczenia, których dokonać mógłby tradycyjny pecet. Jednak jeśli chodzi o poszukiwania liczb pierwszych czas odgrywa istotną rolę. W 2013 roku powstał pierwszy algorytm napisany na komputer kwantowy do poszukiwań liczb pierwszych (tzw. algorytm Latorre). Aby go wykorzystać, wymagane byłoby jednak zastosowanie 80-cio kubitowego komputera – większego niż jakikolwiek działający do tej pory sprzęt tego rodzaju.