Liczba gładka

Liczba $B$-gładka – w teorii liczb, liczba naturalna, która nie ma dzielników pierwszych większych od $B$. 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 $103195607040000=2^{23}3^{9}5^{4}$ jest 5-gładka (oraz $B$-gładka dla wszystkich $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 $n=ab$ za pomocą DFT ciągów o długościach $a$ i $b$. Jeśli długość wyjściowego ciągu jest liczbą $B$-gładką dla małego $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. 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 $\mathbb {F} _{p}$, gdy liczba logarytmowana jest $B$-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 $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ć.

Rozmieszczenie

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

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

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

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

zachodzi, gdy

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

Ponadto wspomniane ograniczenie jest prawdziwe dla wszystkich

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

wtedy i tylko wtedy, gdy prawdziwa jest hipoteza Riemanna.

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

$\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 $\pi (n)$ jest liczbą liczb pierwszych nie większych od $n$.

Linki zewnętrzne

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