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:

.