Введение

Целое число, имеющее только малые простые множители. В теории чисел, n-гладкое (или n-фриабельное) число — это целое число, все простые множители которого не превосходят n. Например, 7-гладкое число — это число, каждый простой множитель которого не больше 7, таким образом, 49 = 7² и 15750 = 2 × 3² × 5³ × 7 являются 7-гладкими, в то время как 11 и 702 = 2 × 3³ × 13 не являются 7-гладкими. Термин, по-видимому, был введен Леонардом Адлеманом. Гладкие числа особенно важны в криптографии, которая опирается на разложение целых чисел на множители. 2-гладкие числа — это просто степени 2, а 5-гладкие числа известны как регулярные числа.

Определение

Положительное целое число называется B-гладким, если ни один из его простых множителей не превышает B. Например, 1620 имеет разложение на простые множители 2² × 3⁴ × 5; следовательно, 1620 является 5-гладким, поскольку ни один из его простых множителей не превышает 5. Это определение включает числа, которым не хватает некоторых из меньших простых множителей; например, и 10, и 12 являются 5-гладкими, даже если им не хватает простых множителей 3 и 5 соответственно. Все 5-гладкие числа имеют вид 2ᵃ × 3ᵇ × 5ᶜ, где a, b и c – неотрицательные целые числа. 3-гладкие числа также называют "гармоническими числами", хотя это название имеет и другие, более широко используемые значения. 5-гладкие числа также называют регулярными числами или числами Хамминга; 7-гладкие числа также называют скромными числами, и иногда высокосоставными, хотя это противоречит другому значению высокосоставных чисел. Следует отметить, что само B не обязательно должно присутствовать среди множителей B-гладкого числа. Если наибольший простой множитель числа равен p, то число является B-гладким для любого B ≥ p. Во многих случаях B является простым числом, но допускаются и составные числа. Число является B-гладким тогда и только тогда, когда оно является p-гладким, где p – наибольшее простое число, меньшее или равное B.

Приложения

Важным практическим применением гладких чисел является быстрое преобразование Фурье (FFT) – алгоритмы (такие как алгоритм Кули — Тьюки FFT), который работает путем рекурсивного разбиения задачи заданного размера n на подзадачи размером, равным размерам его факторов. Используя B-гладкие числа, можно обеспечить, чтобы базовые случаи этой рекурсии представляли собой малые простые числа, для которых существуют эффективные алгоритмы. (Для больших простых чисел требуются менее эффективные алгоритмы, такие как алгоритм FFT Блюстайна.) 5-гладкие или регулярные числа играют особую роль в вавилонской математике. Они также важны в теории музыки (см. Лимит (музыка)), а задача эффективной генерации этих чисел использовалась в качестве тестовой задачи для функционального программирования. Гладкие числа имеют ряд применений в криптографии. Хотя большинство применений сосредоточено вокруг криптоанализа (например, самые быстрые известные алгоритмы факторизации целых чисел, такие как алгоритм общего решета числового поля), хеш-функция VSH является еще одним примером конструктивного использования гладкости для получения принципиально безопасной конструкции.

Гладкая над множеством А

Более того, число m называется гладким относительно множества A, если существует разложение m на множители, где каждый множитель является степенью элемента из A. Например, поскольку 12 = 4 × 3, число 12 гладко относительно множеств A1 = {4, 3}, A2 = {2, 3}, однако оно не будет гладким относительно множества A3 = {3, 5}, так как 12 содержит множитель 4 = 2², и ни 4, ни 2 не входят в A3. Следует отметить, что множество A не обязательно должно состоять из простых множителей, но обычно является собственным подмножеством простых чисел, как это видно из фактор-базы метода факторизации Диксона и квадратического решета. Аналогично, это используется в общем методе решета числового поля для построения понятия гладкости, посредством гомоморфизма.