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:
“Out of the darkness where Philomela sat,
Her fairy numbers issued. What then ailed me?
My ears are called capacious but they failed me,
Her classics registered a little flat!
I rose, and venomously spat.”
—John Crowe Ransom (1888–1974)