Liczba -gładka – w teorii liczb, liczba naturalna, która nie ma dzielników pierwszych większych od . Nazwa została prawdopodobnie użyta pierwszy raz przez Leonarda Adlemana w opisie algorytmu teorioliczbowego. Gładkość liczb ma znaczenie w licznych problemach informatycznych, w szczególności tych związanych z kryptografią.

Przykłady Liczba jest 5-gładka (oraz -gładka dla wszystkich ), ponieważ jej największym dzielnikiem pierwszym jest 5.

Początkowe liczby 2-gładkie (potęgi dwójki): 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768 .

Początkowe liczby 3-gładkie: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96 .

Początkowe liczby 5-gładkie (liczby Hamminga): 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80 .

Zastosowania Liczby gładkie są powiązane z algorytmami szybkiej transformacji Fouriera (FFT), takimi jak algorytm Cooleya-Tukeya. Algorytmy te operują rekurencyjnie, wyrażając dyskretną transformatę Fouriera (DFT) ciągu o złożonej długości za pomocą DFT ciągów o długościach i . Jeśli długość wyjściowego ciągu jest liczbą -gładką dla małego , przypadkami bazowymi tej rekurencji są problemy obliczenia DFT o długościach wyrażonych małymi liczbami pierwszymi, dla których istnieją wydajne algorytmy. Dla dużych liczb pierwszych konieczne jest użycie mniej efektywnych algorytmów, takich jak algorytm Bluesteina.

Liczby gładkie odgrywają istotną rolę w problemach informatycznych z dziedziny teorii liczb, które związane są ściśle z kryptografią. Najlepsze znane algorytmy faktoryzacji, takie jak algorytm Dixona, sito kwadratowe czy GNFS, wykorzystują liczby gładkie. Wyznaczenie logarytmu dyskretnego staje się łatwiejsze, gdy rząd grupy jest liczbą gładką (algorytm Pohliga–Hellmana). Co więcej, termin „liczba gładka” został prawdopodobnie użyty po raz pierwszy w kontekście znajdowania logarytmu dyskretnego w , gdy liczba logarytmowana jest -gładka i znane są wartości logarytmu dyskretnego dla jej dzielników pierwszych.

Na wiedzy o liczbach gładkich oparta jest funkcja skrótu Very Smooth Hash (VSH), której odporność na kolizje (trudność wygenerowania dwóch wiadomości o takim samym skrócie) wynika z trudności znalezienia pierwiastka kwadratowego z liczby gładkiej modulo . Metoda ta jest wydajniejsza i bardziej praktyczna w porównaniu do wielu funkcji skrótu, których odporność na kolizje można ściśle wykazać.

Rozmieszczenie Niech będzie liczbą liczb -gładkich nie większych od . W 1930 roku Dickman zaprezentował heurystyczny dowód, że

gdzie jest funkcją Dickmana – unikalnym ciągłym rozwiązaniem równania różniczkowego przy założeniu, że dla . Na podstawie późniejszych wyników de Bruijina i Hildebranda wiadomo, że dla równość

zachodzi, gdy

Ponadto wspomniane ograniczenie jest prawdziwe dla wszystkich

wtedy i tylko wtedy, gdy prawdziwa jest hipoteza Riemanna.

Dla małych wartości możemy wyprowadzić inne ograniczenia. Gdy spełniona jest nierówność , mamy

gdzie jest liczbą liczb pierwszych nie większych od .

Przypisy

Linki zewnętrzne [dostęp 2022-07-02].

G