Jak zbudować dużą liczbę pierwszą | Magazyn Quanta

Liczby pierwsze to skomplikowana sprawa. W szkole uczymy się, że są to liczby, które nie mają czynników innych niż 1 i siebie, a matematycy od tysięcy lat wiedzą, że istnieje ich nieskończona liczba. Wyprodukowanie jednego na zamówienie nie wydaje się trudne.

Ale to jest. Konstruowanie dowolnie dużych liczb pierwszych jest niezwykle skomplikowane. Zasadniczo masz dwie opcje obliczeniowe, obie z wadami. Możesz użyć losowości i znaleźć jedną, zgadując, ale metoda jest niespójna — ryzykujesz wygenerowanie innej liczby pierwszej za każdym razem. Lub możesz użyć bardziej niezawodnego, deterministycznego algorytmu, ale przy dużych kosztach obliczeniowych.

W maju zespół informatyków pokazał że pewien rodzaj podejścia hybrydowego również mógłby się sprawdzić. Opublikowali algorytm, który skutecznie łączy podejście losowe i deterministyczne, aby wyprowadzić liczbę pierwszą o określonej długości, z dużym prawdopodobieństwem dostarczenia tej samej liczby, nawet jeśli algorytm jest uruchamiany wiele razy. Algorytm łączy losowość i złożoność w interesujący sposób i może być również przydatny w kryptografii, gdzie niektóre schematy kodowania opierają się na konstrukcji dużych liczb pierwszych.

„Ułożyli sekwencję prób, z których każda próbowała skonstruować liczbę pierwszą o różnej długości, i pokazali, że jedna z prób działa” – powiedział Roei Tell, informatyk teoretyczny w Institute for Advanced Study, który nie był zaangażowany w pracę. „Jest to konstrukcja, która generuje deterministycznie wybraną liczbę pierwszą, ale pozwala ci rzucać monetami i dokonywać losowych wyborów w tym procesie”.

Wyzwanie polegające na stworzeniu skutecznej receptury na liczby pierwsze ma głębokie korzenie. „Naprawdę nie wiemy zbyt wiele o rozkładzie liczb pierwszych ani o lukach w liczbach pierwszych” — powiedział Ofer Grossman, który bada algorytmy pseudolosowe. A jeśli nie wiemy, gdzie je znaleźć, nie ma łatwego sposobu na wygenerowanie liczby pierwszej od podstaw.

Z biegiem czasu badacze rozwinęli wyżej wymienione podejścia. Najprościej jest po prostu zgadywać. Jeśli na przykład chcesz liczbę pierwszą z 1,000 cyfr, możesz wybrać losowo liczbę 1,000 cyfr, a następnie ją sprawdzić. „Jeśli to nie jest liczba pierwsza, po prostu wypróbuj kolejną i kolejną i tak dalej, aż ją znajdziesz” – powiedział Rahula Santhanama, informatyk z Uniwersytetu Oksfordzkiego i współautor nowego artykułu. „Ponieważ istnieje wiele liczb pierwszych, ten algorytm da ci pewną liczbę pierwszą z dużym prawdopodobieństwem, po stosunkowo niewielkiej liczbie iteracji”. Ale użycie losowości oznacza, że ​​prawdopodobnie za każdym razem otrzymasz inną liczbę, powiedział. Może to stanowić problem, jeśli potrzebujesz spójności — jeśli, powiedzmy, stosujesz kryptograficzną metodę bezpieczeństwa, która zależy od dostępności dużych liczb pierwszych.

Drugim podejściem jest zastosowanie algorytmu deterministycznego. Możesz wybrać punkt początkowy i rozpocząć sekwencyjne testowanie liczb pod kątem pierwszości. W końcu twoim przeznaczeniem jest znalezienie jednego, a twój algorytm będzie konsekwentnie wyświetlał pierwszy znaleziony. Ale może to trochę potrwać: jeśli szukasz liczby pierwszej z 1,000 cyfr, nawet obliczenia z 2⁵⁰⁰ kroków — co zajęłoby znacznie więcej czasu niż wiek wszechświata — nie wystarczy, aby zagwarantować sukces.

W 2009 roku matematyk i medalista Fieldsa Terence Tao chciał wypaść lepiej. Rzucił wyzwanie matematykom, aby wymyślili deterministyczny algorytm znajdowania liczby pierwszej o danym rozmiarze w obliczeniowym limicie czasu.

Ten limit czasu jest znany jako czas wielomianowy. Algorytm rozwiązuje problem w czasie wielomianowym, jeśli liczba kroków, które wykonuje, jest nie większa niż funkcja wielomianu n, rozmiar wejścia. (Funkcja wielomianowa obejmuje terminy, które mają zmienne podniesione do dodatnich potęg całkowitych, np n² lub 4n³.) W kontekście konstrukcji liczb pierwszych, n odnosi się do liczby cyfr liczby pierwszej, którą chcesz. Mówiąc obliczeniowo, nie kosztuje to dużo: informatycy opisują problemy, które można rozwiązać za pomocą algorytmów w czasie wielomianowym, jako łatwe. Trudny problem natomiast zajmuje czas wykładniczy, co oznacza, że ​​wymaga pewnej liczby kroków przybliżonych przez funkcję wykładniczą (która obejmuje terminy takie jak 2ⁿ).

Przez dziesięciolecia naukowcy badali związek między losowością a twardością. Problem konstruowania liczb pierwszych uznano za łatwy, jeśli dopuszcza się losowość — i zadowala się otrzymaniem za każdym razem innej liczby — i za trudny, jeśli obstaje się przy determinizmie.

Nikomu jeszcze nie udało się sprostać wyzwaniu Tao, ale nowa praca jest bliska. W dużym stopniu opiera się na podejściu wprowadzonym w 2011 roku przez Shafiego Goldwassera i Erana Gata, informatyków z Massachusetts Institute of Technology. Opisali „pseudodeterministyczne” algorytmy — matematyczne przepisy na problemy wyszukiwania, takie jak znajdowanie dużych liczb pierwszych, które mogłyby wykorzystać zalety losowości i z dużym prawdopodobieństwem nadal dawać tę samą odpowiedź za każdym razem. Wykorzystaliby wydajność losowych bitów w przepisie, które w wyniku zostałyby pozbawione losowości, wyglądając na deterministyczne.

Od tego czasu naukowcy badają algorytmy pseudodeterministyczne. W 2017 roku Santhanam i Igor Oliveira z University of Warwick (który również przyczynił się do powstania nowej pracy) opisane pseudodeterministyczne podejście do konstruowania liczb pierwszych, które wykorzystywało losowość i wyglądało przekonująco deterministycznie, ale działało w czasie „podwykładniczym” — szybszym niż wykładniczy, ale wolniejszym niż czas wielomianowy. Następnie w 2021 roku Powiedz i Liji Chen, informatyk z Uniwersytetu Kalifornijskiego w Berkeley, zbadane jak wykorzystać trudny problem do zbudowania generatora liczb pseudolosowych (algorytmu, który generuje ciąg liczb nie do odróżnienia od losowego wyniku). „[Odkryliśmy] nowy związek między twardością a pseudolosowością” – powiedział Chen.

Kawałki ostatecznie połączyły się wiosną 2023 roku, podczas bootcamp dotyczący złożoności obliczeniowej w Simons Institute for the Theory of Computing w Berkeley, kiedy naukowcy zaczęli wspólnie pracować nad problemem, łącząc ze sobą wcześniejsze wyniki. Chen powiedział, że w przypadku nowej pracy Hanlin Ren – informatyk z Oksfordu i współautor – miał wstępne pomysły na połączenie wyniku Chen-Tell z podejściem Santhanam-Oliveira w nowatorski sposób. Następnie cały zespół rozwinął pomysły pełniej, aby stworzyć nowy artykuł.

Powstały pseudodeterministyczny algorytm, powiedział Santhanam, wykorzystał nowe sposoby patrzenia na przeszłe prace do tworzenia liczb pierwszych w czasie wielomianowym. Udowodniono, że wykorzystało losowość do wygenerowania liczby pierwszej o określonej długości, a narzędzie jest dokładniejsze niż losowe zgadywanie i bardziej wydajne obliczeniowo niż deterministyczne chrupanie.

Santhanam powiedział, że nowy algorytm jest również niezwykle prosty i można go zastosować do szerokiego zakresu problemów wyszukiwania - tak naprawdę do dowolnego gęstego podzbioru liczb, takich jak liczby pierwsze, dla których przynależność można określić w czasie wielomianowym. Ale to nie jest idealne. Algorytm działa dla nieskończenie wielu długości danych wejściowych, ale nie obejmuje wszystkich długości cyfr. Nadal mogą istnieć pewne wartości n tam, dla których algorytm nie tworzy deterministycznie liczby pierwszej.

„Fajnie byłoby pozbyć się tego małego zastrzeżenia” – powiedział Grossman.

Ostatecznym celem, powiedział Santhanam, jest znalezienie algorytmu, który w ogóle nie wymaga losowości. Ale to zadanie pozostaje otwarte. „Chcielibyśmy użyć determinizmu” — powiedział.

Zwrócił jednak również uwagę, że procesy pseudolosowe są potężnymi narzędziami, a projekty takie jak konstruowanie liczb pierwszych to tylko jeden ze sposobów ich wykorzystania do łączenia pomysłów z matematyki, informatyki, teorii informacji i innych dziedzin.

„Ekscytujące jest zastanawianie się, dokąd jeszcze zaprowadzą te genialne obserwacje” – powiedział Tell.