Гладкое число

Целое число, имеющее только малые простые множители

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

Определение

Положительное целое число называется B - гладким, если ни один из его простых множителей не больше B. Например, 1620 имеет разложение на простые множители 2 ² × 3 ^{4 × 5; поэтому 1620 является 5} - гладким, поскольку ни один из его простых множителей не больше 5. Это определение включает числа, у которых отсутствуют некоторые из меньших простых множителей; например, и 10, и 12 являются 5-гладкими, хотя у них отсутствуют простые множители 3 и 5 соответственно. Все 5-гладкие числа имеют вид 2 ^a × 3 ^b × 5 ^c , где a , b и c являются неотрицательными целыми числами.

3-гладкие числа также называются «гармоническими числами», хотя это название имеет и другие, более широко используемые значения. ^[4] 5-гладкие числа также называются обычными числами или числами Хэмминга; ^[5] 7-гладкие числа также называются скромными числами , ^[6] а иногда их называют высокосоставными , ^[7] хотя это противоречит другому значению высокосоставных чисел .

Здесь следует отметить, что само B не обязательно должно присутствовать среди множителей B -гладкого числа. Если наибольший простой множитель числа равен p , то число является B -гладким для любого B ≥ p . Во многих сценариях B является простым , но составные числа также разрешены. Число является B -гладким тогда и только тогда, когда оно является p -гладким, где p - наибольшее простое число, меньшее или равное B .

Приложения

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

5-гладкие или регулярные числа играют особую роль в вавилонской математике . ^[8] Они также важны в теории музыки (см. Предел (музыка) ), ^[9] и проблема эффективной генерации этих чисел использовалась в качестве тестовой задачи для функционального программирования . ^[10]

Гладкие числа имеют ряд приложений в криптографии. ^[11] В то время как большинство приложений сосредоточено вокруг криптоанализа (например, самые быстрые известные алгоритмы факторизации целых чисел , например: общий алгоритм решета числового поля ), хэш-функция VSH является еще одним примером конструктивного использования гладкости для получения доказуемо безопасной конструкции .

Распределение

Пусть обозначает число y -гладких целых чисел, меньших или равных x (функция де Брейна). ${\displaystyle \Psi (x,y)}$

Если граница гладкости B фиксирована и мала, то существует хорошая оценка для : ${\displaystyle \Psi (x,B)}$

${\displaystyle \Psi (x,B)\sim {\frac {1}{\pi (B)!}}\prod _{p\leq B}{\frac {\log x}{\log p}}.}$

где обозначает количество простых чисел, меньших или равных . ${\displaystyle \pi (B)}$ ${\displaystyle B}$

В противном случае определите параметр u как u  = log  x  / log  y : то есть, x  =  y ^u . Тогда,

${\displaystyle \Psi (x,y)=x\cdot \rho (u)+O\left({\frac {x}{\log y}}\right)}$

где — функция Дикмана . ${\displaystyle \rho (u)}$

Для любого k почти все натуральные числа не будут k -гладкими.

Если , где является -гладким и не является (или равно 1), то называется -гладкой частью . Известно, что относительный размер -гладкой части случайного целого числа, меньшего или равного , убывает гораздо медленнее, чем . ^[12] ${\displaystyle n=n_{1}n_{2}}$ ${\displaystyle n_{1}}$ ${\displaystyle B}$ ${\displaystyle n_{2}}$ ${\displaystyle n_{1}}$ ${\displaystyle B}$ ${\displaystyle n}$ ${\displaystyle x^{1/u}}$ ${\displaystyle x}$ ${\displaystyle \rho (u)}$

Числа Powersmooth

Далее, m называется n - степенногладким (или n - ультраплавным ), если все простые степени, делящие m, удовлетворяют: ${\displaystyle p^{\nu }}$

${\displaystyle p^{\nu }\leq n.\,}$

Например, 720 (2 ⁴ × 3 ² × 5 ¹ ) является 5-гладким, но не 5-степенным гладко (потому что существует несколько простых степеней, больших 5, например и ). Это 16-степенной гладко, поскольку его наибольшая степень простого множителя равна 2 ⁴  = 16. Число также является 17-степенным гладко, 18-степенным гладко и т. д. ${\displaystyle 3^{2}=9\nleq 5}$ ${\displaystyle 2^{4}=16\nleq 5}$

В отличие от n -гладких чисел, для любого положительного целого числа n существует только конечное число n -гладкостепенных чисел; на самом деле, n -гладкостепенные числа являются в точности положительными делителями « наименьшего общего кратного 1, 2, 3, …, n » (последовательность A003418 в OEIS ), например, 9-гладкостепенные числа (также 10-гладкостепенные числа) являются в точности положительными делителями 2520.

n -гладкие и n -степенногладкие числа имеют приложения в теории чисел, например, в  алгоритме Полларда p − 1 и ECM . Такие приложения часто говорят, что они работают с «гладкими числами», без указания n ; это означает, что вовлеченные числа должны быть n -степенногладкими, для некоторого неопределенного малого числа n. По мере увеличения s n производительность рассматриваемого алгоритма или метода быстро ухудшается. Например, алгоритм Полига–Хеллмана для вычисления дискретных логарифмов имеет время выполнения O ( n ^1/2 ) — для групп порядка n -гладких .

Сгладить по наборуА

Более того, m называется гладким над множеством A , если существует факторизация m , где множители являются степенями элементов из A. Например, поскольку 12 = 4 × 3, 12 является гладким над множествами A ₁ = {4, 3}, A ₂ = {2, 3} и , однако он не будет гладким над множеством A ₃ = {3, 5}, так как 12 содержит множитель 4 = 2 ² , а ни 4, ни 2 не входят в A ₃ . ${\displaystyle \mathbb {Z} }$

Обратите внимание, что множество A не обязательно должно быть множеством простых множителей, но обычно оно является собственным подмножеством простых чисел, как это видно в факторной базе метода факторизации Диксона и квадратичного решета . Аналогично, это то, что общее числовое поле решета использует для построения своего понятия гладкости, при гомоморфизме . ^[13] ${\displaystyle \phi :\mathbb {Z} [\theta ]\to \mathbb {Z} /n\mathbb {Z} }$

Смотрите также

• Очень составное число
• Грубое число
• Круглое число
• Теорема Штёрмера
• Необычное число

Примечания и ссылки

1. "P-гладкие числа или P-рыхлые числа". GeeksforGeeks . 2018-02-12 . Получено 2019-12-12 .
2. Weisstein, Eric W. "Smooth Number". mathworld.wolfram.com . Получено 12.12.2019 .
3. Хеллман, ME ; Рейнери, JM (1983). "Быстрое вычисление дискретных логарифмов в GF ( q )". Достижения в криптологии – Труды Crypto 82. стр. 3–13. doi :10.1007/978-1-4757-0602-4_1. ISBN 978-1-4757-0604-8.
4. Слоан, Н. Дж. А. (ред.). "Последовательность A003586 (3-гладкие числа)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
5. "Python: Получить числа Хэмминга вплоть до заданного числа, а также проверить, является ли заданное число числом Хэмминга". w3resource . Получено 12.12.2019 .
6. "Problem H: Humble Numbers". www.eecs.qmul.ac.uk . Получено 2019-12-12 .
7. Слоан, Н. Дж. А. (ред.). "Последовательность A002473 (7-гладкие числа)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
8. Aaboe, Asger (1965), «Некоторые математические таблицы Селевкидов (расширенные обратные величины и квадраты обычных чисел)», Journal of Cuneiform Studies , 19 (3): 79–86, doi :10.2307/1359089, JSTOR  1359089, MR  0191779, S2CID  164195082.
9. Лонге-Хиггинс, ХК (1962), «Письмо другу-музыканту», Music Review (август): 244–248.
10. Дейкстра, Эдсгер В. (1981), Упражнение Хэмминга в SASL (PDF) , Отчет EWD792. Первоначально частная рукописная заметка.
11. Наккаш, Дэвид; Шпарлинский, Игорь (17 октября 2008 г.). «Divisibility, Smoothness and Cryptographic Applications» (PDF) . eprint.iacr.org . arXiv : 0810.2067 . Получено 26 июля 2017 г. .ф
12. Ким, Тэчан; Тибоучи, Мехди (2015). «Атаки с использованием недействительных кривых в условиях GLS». В Tanaka, Keisuke; Suga, Yuji (ред.). Достижения в области информационной и компьютерной безопасности – 10-й международный семинар по безопасности, IWSEC 2015, Нара, Япония, 26–28 августа 2015 г., Труды . Конспект лекций по информатике. Том 9241. Springer. стр. 41–55. doi :10.1007/978-3-319-22425-1_3.
13. Бриггс, Мэтью Э. (17 апреля 1998 г.). «Введение в общее решето числового поля» (PDF) . math.vt.edu . Блэксбург, Вирджиния: Политехнический институт и государственный университет Вирджинии . Получено 26 июля 2017 г. .

Библиография

• Г. Тененбаум, Введение в аналитическую и вероятностную теорию чисел , (AMS, 2015) ISBN 978-0821898543 
• А. Грэнвилл , Гладкие числа: вычислительная теория чисел и не только, Труды семинара MSRI, 2008 г.

Внешние ссылки

• Вайсштейн, Эрик В. «Гладкое число». MathWorld .

В энциклопедии целочисленных последовательностей (OEIS) перечислены B -гладкие числа для малых B :

• 2-гладкие числа: A000079 (2 ⁱ )
• 3-гладкие числа: A003586 (2 ⁱ 3 ^j )
• 5-гладкие числа: A051037 (2 ⁱ 3 ^j 5 ^k )
• 7-гладкие числа: A002473 (2 ⁱ 3 ^j 5 ^k 7 ^l )
• 11-гладкие числа: A051038 (и т.д.)
• 13-гладкие числа: A080197
• 17-гладкие числа: A080681
• 19-гладкие числа: A080682
• 23-гладкие числа: A080683