Powersmooth Numbers
Further, m is called B-powersmooth if all prime powers dividing m satisfy:
For example, 243251 is 5-smooth, but is not 5-powersmooth. It is 16-powersmooth since its greatest prime factor power is 24 = 16. The number is also 17-powersmooth, 18-powersmooth, etc.
B-smooth and B-powersmooth numbers have applications in number theory, such as in Pollard's p − 1 algorithm. Such applications are often said to work with "smooth numbers," with no B specified; this means the numbers involved must be B-smooth for some unspecified small number B; as B increases, the performance of the algorithm or method in question degrades rapidly. For example, the Pohlig–Hellman algorithm for computing discrete logarithms has a running time of O(B1/2) for groups of B-smooth order.
Read more about this topic: Smooth Number
Famous quotes containing the word numbers:
“I had a feeling that out there, there were very poor people who didn’t have enough to eat. But they wore wonderfully colored rags and did musical numbers up and down the streets together.”
—Jill Robinson (b. 1936)