Liczba gładka: Różnice pomiędzy wersjami

[wersja przejrzana]

Usunięta treść Dodana treść

Jednokolumnowy

Wersja z 17:30, 18 lut 2024

Liczba $B$ -gładka^[1] – w teorii liczb, liczba naturalna, która nie ma dzielników pierwszych większych od $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 $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^[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 $\mathbb {F} _{p}$ , gdy liczba logarytmowana jest $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 $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 $\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]$ ^[7]^[8]. 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^[4]^[8].

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$ ^[8].

Przypisy

↑ ^a ^b 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.).
↑ ^a ^b Eric W.E.W. Weisstein Eric W.E.W., Smooth Number [online], Wolfram MathWorld [dostęp 2024-02-18] (ang.).
↑ ^a ^b 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.).
↑ ^a ^b ^c ^d DavidD. Naccache DavidD., IgorI. Shparlinski IgorI., Divisibility, Smoothness and Cryptographic Applications [online], 2008 [dostęp 2024-02-18] (ang.).
↑ 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.).
↑ 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.).
↑ 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.).
↑ ^a ^b ^c 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].

[:0-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.).

[:1-2] Eric W.E.W. Weisstein Eric W.E.W., Smooth Number [online], Wolfram MathWorld [dostęp 2024-02-18] (ang.).

[:3-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-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.).

[:2-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.).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Linia 1: / Linia 1: @@
+'''Liczba <math>B</math>-gładka'''<ref name=":0">{{Cytuj |autor = Bartosz Źrałek |tytuł = A GENERALIZATION OF THE POHLIG-HELLMAN ALGORITHM AND ITS APPLICATION TO FACTORING |czasopismo = Studia Bezpieczeństwa Narodowego |data = 2014-12-05 |data dostępu = 2024-02-18 |issn = 2082-2677 |wolumin = 6 |numer = 2 |s = 177–183 |doi = 10.37055/sbn/135229 |url = http://sbn.wat.edu.pl/ROZSZERZONY-ALGORYTM-POHLIGA-HELLMANA-I-JEGO-ZASTOSOWANIE-DO-FAKTORYZACJI,135229,0,2.html |język = pl |dostęp = o}}</ref> – w [[teoria liczb|teorii liczb]], liczba naturalna, która nie ma [[Dzielnik|dzielników]] [[Liczba pierwsza|pierwszych]] większych od <math>B</math><ref name=":1">{{Cytuj |autor = Eric W. Weisstein |tytuł = Smooth Number |data dostępu = 2024-02-18 |opublikowany = Wolfram MathWorld |url = https://mathworld.wolfram.com/SmoothNumber.html |język = en}}</ref>. Nazwa została prawdopodobnie użyta pierwszy raz przez [[Leonard Adleman|Leonarda Adlemana]] w opisie [[Algorytm|algorytmu]] teorioliczbowego<ref name=":3">{{Cytuj |autor = Martin E. Hellman; Justin M. Reyneri |tytuł = Advances in Cryptology: Proceedings of Crypto 82 |data = 1983 |isbn = 978-1-4757-0604-8 |wydawca = Springer US |s = 3-13 |url = https://link.springer.com/chapter/10.1007/978-1-4757-0602-4_1 |język = en}}</ref>. Gładkość liczb ma znaczenie w licznych problemach informatycznych, w szczególności tych związanych z [[Kryptografia|kryptografią]]<ref name=":0" /><ref name=":1" /><ref name=":4">{{Cytuj |autor = David Naccache; Igor Shparlinski |tytuł = Divisibility, Smoothness and Cryptographic Applications |data = 2008 |data dostępu = 2024-02-18 |url = https://eprint.iacr.org/2008/437.pdf |język = en |dostęp = o}}</ref>.
-{{dopracować|styl|źródła=2010-08}}
-W [[teoria liczb|teorii liczb]], liczba naturalna ''m'' jest nazywana ''B''-''gładką'', jeśli wszystkie jej dzielniki [[liczba pierwsza|pierwsze]] są nie większe niż ''B''.
+== Przykłady ==
-Przykładowo 103195607040000=2<sup>23</sup>3<sup>9</sup>5<sup>4</sup> jest 5-gładka, ponieważ jej największym dzielnikiem pierwszym jest 5.
+Liczba <math>103195607040000=2^{23}3^95^4</math> jest 5-gładka (oraz <math>B</math>-gładka dla wszystkich <math>B \ge 5</math>), ponieważ jej największym dzielnikiem pierwszym jest 5.
+Początkowe liczby 2-gładkie ([[Potęga dwójki|potęgi dwójki]]):
-Liczby gładkie przydatne są w niektórych algorytmach teorioliczbowych.
+: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768 {{OEIS|id=A000079}}.
+Początkowe liczby 3-gładkie:
-Przykładowo niektóre algorytmy [[Szybka transformacja Fouriera|FFT]], rozkładają problem rozmiaru ''n'' na problemy o wielkości jego czynników. Jeśli zaczyna się od liczb gładkich, otrzymuje się małe, szybko rozwiązywalne problemy. Innym przykładem jest [[redukcja Pohliga-Hellmana]] obliczająca [[logarytm dyskretny]]. W ogólnym przypadku jest ona [[algorytm wykładniczy|algorytmem wykładniczym]], ale dla ''B''-gładkich liczb działa w czasie O(''B''<sup>1/2</sup>).
+: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96 {{OEIS|id=A003586}}.
+Początkowe liczby 5-gładkie (liczby [[Richard Hamming|Hamminga]]):
-Liczbę ''B''-gładkich liczb mniejszych od zadanego ''x'' można oszacować przez:
+: 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 {{OEIS|id=A051037}}.
-: <math>\Psi(x,B) \sim \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log x}{\log p}.</math>
+== Zastosowania ==
+Liczby gładkie są powiązane z algorytmami [[Szybka transformacja Fouriera|szybkiej transformacji Fouriera]] (FFT), takimi jak [[algorytm Cooleya-Tukeya]]. Algorytmy te operują [[Rekurencja|rekurencyjnie]], wyrażając [[Dyskretna transformata Fouriera|dyskretną transformatę Fouriera]] (DFT) ciągu o [[Liczba złożona|złożonej]] długości <math>n = ab</math> za pomocą DFT ciągów o długościach <math>a</math> i <math>b</math>. Jeśli długość wyjściowego ciągu jest liczbą <math>B</math>-gładką dla małego <math>B</math>, przypadkami bazowymi tej rekurencji są problemy obliczenia DFT o długościach wyrażonych małymi liczbami pierwszymi, dla których istnieją [[Złożoność obliczeniowa|wydajne]] algorytmy<ref>{{Cytuj |autor = James W. Cooley, John W. Tukey |tytuł = An algorithm for the machine calculation of complex Fourier series |czasopismo = Mathematics of Computation |data = 1965 |data dostępu = 2024-02-18 |issn = 0025-5718 |wolumin = 19 |numer = 90 |s = 297–301 |doi = 10.1090/S0025-5718-1965-0178586-1 |url = https://www.ams.org/mcom/1965-19-090/S0025-5718-1965-0178586-1/ |język = en |dostęp = o}}</ref>. 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 [[Rozkład na czynniki|faktoryzacji]], takie jak algorytm Dixona, [[sito kwadratowe]] czy [[GNFS]], wykorzystują liczby gładkie. Wyznaczenie [[Logarytm dyskretny|logarytmu dyskretnego]] staje się łatwiejsze, gdy [[Rząd (teoria grup)|rząd grupy]] jest liczbą gładką ([[Redukcja Pohliga-Hellmana|algorytm Pohliga–Hellmana]])<ref name=":4" />. Co więcej, termin „liczba gładka” został prawdopodobnie użyty po raz pierwszy w kontekście znajdowania logarytmu dyskretnego w <math>\mathbb{F}_p</math>, gdy liczba logarytmowana jest <math>B</math>-gładka i znane są wartości logarytmu dyskretnego dla jej dzielników pierwszych<ref name=":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 <math>pq</math>. 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ć<ref name=":4" /><ref>{{Cytuj |autor = Scott Contini; Arjen K. Lenstra; Ron Steinfeld |tytuł = VSH, an Efficient and Provable Collision-Resistant Hash Function |czasopismo = Advances in Cryptology - EUROCRYPT 2006 |data = 2006 |data dostępu = 2024-02-18 |isbn = 978-3-540-34547-3 |wydawca = Springer-Verlag |s = 165–182 |seria = Lecture Notes in Computer Science |url = https://link.springer.com/chapter/10.1007/11761679_11 |język = en |dostęp = o}}</ref>.
+== Rozmieszczenie ==
+Niech <math>\Psi(x,B)</math> będzie liczbą liczb <math>B</math>-gładkich nie większych od <math>x</math>. W 1930 roku Dickman zaprezentował heurystyczny dowód, że
+{{Wzór|<math>\Psi(x, y) \sim x\rho\left(\frac{\log{x} }{\log{y} }\right)</math> dla <math>x\to\infty</math>,}}
+gdzie <math>\rho</math> jest funkcją Dickmana – unikalnym ciągłym rozwiązaniem równania różniczkowego <math>u\rho'(u) + \rho(u - 1) = 0</math> przy założeniu, że <math>\rho(u) = 1</math> dla <math>u \in [0, 1]</math><ref>{{Cytuj |autor = Donald Ervin Knuth |tytuł = The art of computer programming. Volume 2: Seminumerical algorithms / Donald E. Knuth (Stanford University) |data = 2021 |data dostępu = 2024-02-18 |isbn = 978-0-201-89684-8 |wydanie = Third edition, forthy-first printing |wydawca = Addison-Wesley |s = 382-383 |język = en}}</ref><ref name=":2">{{Cytuj |autor = Andrew Granville |tytuł = Smooth numbers: computational number theory and beyond |czasopismo = Algorithmic Number Theory. MSRI Publications |data = 2008 |data dostępu = 2024-02-18 |isbn = 978-0-521-80854-5 |wolumin = Volume 44 |wydawca = Cambridge University Press |s = 267-323 |url = https://dms.umontreal.ca/~andrew/PDF/msrire.pdf |język = en |dostęp = o}}</ref>. Na podstawie późniejszych wyników de Bruijina i Hildebranda wiadomo, że dla <math>u = \textstyle \frac{\log{x}}{\log{y}}</math> równość
+{{Wzór|<math>\Psi(x, y) = x\rho(u)\left(1 + O\left(\frac{\log{(u + 1)} }{\log{y} }\right)\right)</math>}}
+zachodzi, gdy
+{{Wzór|<math>1 \le u \le \exp\left((\log{y})^{3/5 - \varepsilon}\right)</math>.}}
+Ponadto wspomniane ograniczenie jest prawdziwe dla wszystkich
+{{Wzór|<math> 1 \le u \le y^{1/2 - \varepsilon} </math>}}
+wtedy i tylko wtedy, gdy prawdziwa jest [[hipoteza Riemanna]]<ref name=":4" /><ref name=":2" />.
+Dla małych wartości <math>B</math> możemy wyprowadzić inne ograniczenia. Gdy spełniona jest nierówność <math>B \le \sqrt{\log{x}\log\log{x}}</math>, mamy
+{{Wzór|<math>\Psi(x,B) = \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log x}{\log p}\left(1 + O\left(\frac{B^2}{\log{x}\log{B} }\right)\right)</math>,}}
+gdzie <math>\pi(n)</math> jest [[Funkcja licząca liczby pierwsze|liczbą liczb pierwszych nie większych od]] <math>n</math><ref name=":2" />.
+== Przypisy ==
+{{Przypisy}}
 == Linki zewnętrzne ==