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:
“The principle of majority rule is the mildest form in which the force of numbers can be exercised. It is a pacific substitute for civil war in which the opposing armies are counted and the victory is awarded to the larger before any blood is shed. Except in the sacred tests of democracy and in the incantations of the orators, we hardly take the trouble to pretend that the rule of the majority is not at bottom a rule of force.”
—Walter Lippmann (1889–1974)