Liczba gładka

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

W teorii liczb, liczba naturalna m jest nazywana B-gładką, jeśli wszystkie jej dzielniki pierwsze są nie większe niż B.

Przykładowo 103195607040000=2233954 jest 5-gładka, ponieważ jej największym dzielnikiem pierwszym jest 5.

Liczby gładkie przydatne są w niektórych algorytmach teorioliczbowych. Przykładowo niektóre algorytmy 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 algorytmem wykładniczym, ale dla B-gładkich liczb działa w czasie O(B1/2).

Liczbę B-gładkich liczb mniejszych od zadanego x można oszacować przez:

 \Psi(x,B) \sim  \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log x}{\log p} .