Liczby gładkie

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

Przykłady

Liczba ${\displaystyle 103195607040000=2^{23}3^{9}5^{4}}$ jest 5-gładka (oraz ${\displaystyle B}$-gładka dla wszystkich ${\displaystyle B\geq 5}$), 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 (ciąg A000079 w OEIS).

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 (ciąg A003586 w OEIS).

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 (ciąg A051037 w OEIS).

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 ${\displaystyle n=ab}$ za pomocą DFT ciągów o długościach ${\displaystyle a}$ i ${\displaystyle b}$. Jeśli długość wyjściowego ciągu jest liczbą ${\displaystyle B}$-gładką dla małego ${\displaystyle B}$, przypadkami bazowymi tej rekurencji są problemy obliczenia DFT o długościach wyrażonych małymi liczbami pierwszymi, dla których istnieją wydajne algorytmy^[5]. 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)^[4]. Co więcej, termin „liczba gładka” został prawdopodobnie użyty po raz pierwszy w kontekście znajdowania logarytmu dyskretnego w ${\displaystyle \mathbb {F} _{p}}$, gdy liczba logarytmowana jest ${\displaystyle B}$-gładka i znane są wartości logarytmu dyskretnego dla jej dzielników pierwszych^[3].

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 ${\displaystyle pq}$. 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ć^[4][6].

Rozmieszczenie

Niech ${\displaystyle \Psi (x,B)}$ będzie liczbą liczb ${\displaystyle B}$-gładkich nie większych od ${\displaystyle x}$. W 1930 roku Dickman zaprezentował heurystyczny dowód, że

${\displaystyle \Psi (x,y)\sim x\rho \left({\frac {\log {x}}{\log {y}}}\right)}$ dla ${\displaystyle x\to \infty }$,

gdzie ${\displaystyle \rho }$ jest funkcją Dickmana – unikalnym ciągłym rozwiązaniem równania różniczkowego ${\displaystyle u\rho '(u)+\rho (u-1)=0}$ przy założeniu, że ${\displaystyle \rho (u)=1}$ dla ${\displaystyle u\in [0,1]}$^[7][8]. Na podstawie późniejszych wyników de Bruijina i Hildebranda wiadomo, że dla ${\displaystyle u=\textstyle {\frac {\log {x}}{\log {y}}}}$ równość

${\displaystyle \Psi (x,y)=x\rho (u)\left(1+O\left({\frac {\log {(u+1)}}{\log {y}}}\right)\right)}$

zachodzi, gdy

${\displaystyle 1\leq u\leq \exp \left((\log {y})^{3/5-\varepsilon }\right)}$.

Ponadto wspomniane ograniczenie jest prawdziwe dla wszystkich

${\displaystyle 1\leq u\leq y^{1/2-\varepsilon }}$

wtedy i tylko wtedy, gdy prawdziwa jest hipoteza Riemanna^[4][8].

Dla małych wartości ${\displaystyle B}$ możemy wyprowadzić inne ograniczenia. Gdy spełniona jest nierówność ${\displaystyle B\leq {\sqrt {\log {x}\log \log {x}}}}$, mamy

${\displaystyle \Psi (x,B)={\frac {1}{\pi (B)!}}\prod _{p\leq B}{\frac {\log x}{\log p}}\left(1+O\left({\frac {B^{2}}{\log {x}\log {B}}}\right)\right)}$,

gdzie ${\displaystyle \pi (n)}$ jest liczbą liczb pierwszych nie większych od ${\displaystyle n}$^[8].

Przypisy

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Smooth Number, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2022-07-02].