В теории чисел, n- гладкое (или n-рыхлое ) число - это целое, простое факто rs меньше или равны n. Например, 7-гладкое число - это число, все простые множители которого не более 7, поэтому 49 = 7 и 15750 = 2 × 3 × 5 × 7 оба являются 7-гладкими, а 11 и 702 = 2 × 3 × 13. не 7-гладкие. Этот термин, кажется, был придуман Леонардом Адлеманом. Гладкие числа особенно важны в криптографии, которая основана на факторизации целых чисел. 2-гладкие числа - это просто степени 2, а 5-гладкие числа известны как обычные числа.
A положительное целое число называется B-сглаженным, если ни один из его простых множителей не превышает B. Например, 1,620 имеет разложение на простые множители 2 × 3 × 5; следовательно, 1,620 является 5-гладким, потому что ни один из его простых делителей не больше 5. Это определение включает числа, у которых отсутствуют некоторые из меньших простых множителей; например, и 10, и 12 являются 5-гладкими, даже если они пропускают простые множители 3 и 5 соответственно. Все 5-гладкие числа имеют форму 2 × 3 × 5, где a, b и c - неотрицательные целые числа.
5-гладкие числа также называются регулярными числами или числами Хэмминга; 7-гладкие числа также называются простыми числами и иногда называются сильно составными, хотя это противоречит другому значению очень составных чисел.
. Здесь обратите внимание, что само Bне требуется, чтобы он входил в число факторов гладкого числа B. Если наибольший простой множитель числа равен p, тогда число B-гладкое для любого B≥ p. Во многих сценариях Bявляется простым, но также разрешены составные числа. Число является B-гладким тогда и только тогда, когда это p-smooth, где p- наибольшее простое число, меньшее или равное в B.
Важным практическим применением гладких чисел являются алгоритмы быстрого преобразования Фурье (БПФ) (такие как алгоритм БПФ Кули – Тьюки ), который действует путем рекурсивного разбиения проблемы заданного размера n на задачи, размер которых зависит от ее факторов. Используя B-гладкие числа, можно гарантировать, что базовыми случаями этой рекурсии являются маленькие простые числа, для которых существуют эффективные алгоритмы. (Для больших простых чисел требуются менее эффективные алгоритмы, такие как алгоритм БПФ Блустейна.)
5-гладкие или регулярные числа играют особую роль в вавилонской математике. Они также важны в теории музыки (см. Предел (музыка) ), и проблема эффективного генерирования этих чисел использовалась в качестве тестовой задачи для функционального программирования.
Гладкие числа имеют ряд применений в криптографии. В то время как большинство приложений сосредоточено вокруг криптоанализа (например, самых быстрых из известных алгоритмов целочисленной факторизации, например: алгоритм сита общего числового поля ), VSH хэш-функция - еще один пример конструктивного использования гладкости для получения доказуемо безопасного дизайна.
Пусть обозначают количество y-гладких целых чисел, меньших или равных x (функция де Брейна).
Если граница гладкости B фиксированная и мала, существует хорошая оценка для :
где обозначает количество простых чисел, меньшее или равное <184.>B {\ displaystyle \ scriptstyle B}
.
В противном случае определите параметр u как u = log x / log y: то есть x = y. Тогда
где - это функция Дикмана.
Средний размер гладкой части числа заданного размера известен как , и известно, что он распадается намного медленнее. чем
.
Для любого k, почти все натуральные числа не будут k-гладкими.
Далее, m называется B- powersmooth (или B- сверхрыхлым ), если все простые степени деление m удовлетворяет:
Например, 720 (2 × 3 × 5) является 5-гладким, но не 5-степенным (поскольку есть несколько степеней простых чисел больше 5, например, и
). Это 16-степенное плавное число, так как его наибольшая степень простого коэффициента равна 2 = 16. Число также является 17-степенным, 18-степенным и т. Д.
B-гладкие и B-степенные числа имеют приложения в теории чисел, например, в алгоритме p - 1 Полларда и ECM. Часто говорят, что такие приложения работают с «гладкими числами» без указания B; это означает, что задействованные числа должны быть B-степенной гладкостью для некоторого неопределенного малого числа B. По мере увеличения B производительность рассматриваемого алгоритма или метода быстро ухудшается. Например, алгоритм Полига – Хеллмана для вычисления дискретных логарифмов имеет время выполнения O (B) - для групп из B -smooth order.
Более того, m называется гладким по набору A, если существует факторизация m, где множители являются степенями элементов в A. Например, поскольку 12 = 4 × 3, 12 является гладким по множествам A 1 = {4, 3}, A 2 = {2, 3}, и , однако он не будет сглаженным по набору A 3 = {3, 5}, поскольку 12 содержит фактор 4 = 2, которого нет в A 3.
. Обратите внимание, что набор A не обязательно должен быть набором простых множителей, но обычно это собственное подмножество простых чисел, как показано в факторная база из метода факторизации Диксона и квадратного сита. Аналогичным образом, это то, что сито общего числового поля использует для построения своего понятия гладкости в рамках гомоморфизма .
В Он-лайн энциклопедии целочисленных последовательностей (OEIS) перечислены B-гладкие числа для маленьких B: