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

1. BartoszB. Źrałek BartoszB., A GENERALIZATION OF THE POHLIG-HELLMAN ALGORITHM AND ITS APPLICATION TO FACTORING, „Studia Bezpieczeństwa Narodowego”, 6 (2), 2014, s. 177–183, DOI: 10.37055/sbn/135229, ISSN 2082-2677 [dostęp 2024-02-18]  (pol.).
2. Eric W.E.W. Weisstein Eric W.E.W., Smooth Number [online], Wolfram MathWorld [dostęp 2024-02-18]  (ang.).
3. Martin E.M.E. Hellman Martin E.M.E., Justin M.J.M. Reyneri Justin M.J.M., Advances in Cryptology: Proceedings of Crypto 82, Springer US, 1983, s. 3-13, ISBN 978-1-4757-0604-8  (ang.).
4. DavidD. Naccache DavidD., IgorI. Shparlinski IgorI., Divisibility, Smoothness and Cryptographic Applications [online], 2008 [dostęp 2024-02-18]  (ang.).
5. James W.J.W. Cooley James W.J.W., John W.J.W. Tukey John W.J.W., An algorithm for the machine calculation of complex Fourier series, „Mathematics of Computation”, 19 (90), 1965, s. 297–301, DOI: 10.1090/S0025-5718-1965-0178586-1, ISSN 0025-5718 [dostęp 2024-02-18]  (ang.).
6. ScottS. Contini ScottS., Arjen K.A.K. Lenstra Arjen K.A.K., RonR. Steinfeld RonR., VSH, an Efficient and Provable Collision-Resistant Hash Function, „Advances in Cryptology - EUROCRYPT 2006”, Springer-Verlag, 2006 (Lecture Notes in Computer Science), s. 165–182, ISBN 978-3-540-34547-3 [dostęp 2024-02-18]  (ang.).???
7. Donald ErvinD.E. Knuth Donald ErvinD.E., The art of computer programming. Volume 2: Seminumerical algorithms / Donald E. Knuth (Stanford University), Third edition, forthy-first printing, Addison-Wesley, 2021, s. 382-383, ISBN 978-0-201-89684-8 [dostęp 2024-02-18]  (ang.).
8. AndrewA. Granville AndrewA., Smooth numbers: computational number theory and beyond, „Algorithmic Number Theory. MSRI Publications”, Volume 44, Cambridge University Press, 2008, s. 267-323, ISBN 978-0-521-80854-5 [dostęp 2024-02-18]  (ang.).???

Linki zewnętrzne

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