Сглаженное число

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

• 1 Определение
• 2 Приложения
• 3 Распространение
• 4 Числа Powersmooth
• 5 Сглаживание по набору A
• 6 См. Также
• 7 Примечания и ссылки
• 8 Библиография
• 9 Внешние ссылки

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 хэш-функция - еще один пример конструктивного использования гладкости для получения доказуемо безопасного дизайна.

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

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

$\Psi \; (x,\; B)\; \sim \; 1\; \pi \; (B)!\; \prod \; p\; \le \; B\; журнал\; \; x\; журнал\; \; p.\; \{\backslash \; displaystyle\; \backslash \; Psi\; (x,\; B)\; \backslash \; sim\; \{\backslash \; frac\; \{1\}\; \{\backslash \; pi\; (B)!\}\}\; \backslash \; prod\; \_\; \{p\; \backslash \; leq\; B\}\; \{\backslash \; frac\; \{\backslash \; log\; x\}\; \{\backslash \; log\; p\}\}.\}$

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

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

$\Psi \; (Икс,\; Y)\; знак\; равно\; Икс\; \cdot \; \rho \; (U)\; +\; О\; (Икс\; журнал\; \; Y)\; \{\backslash \; Displaystyle\; \backslash \; Psi\; (x,\; y)\; =\; х\; \backslash \; cdot\; \backslash \; rho\; (u)\; +\; O\; \backslash \; left\; (\; \{\backslash \; frac\; \{x\}\; \{\backslash \; log\; y\}\}\; \backslash \; right)\}$

где $\rho \; (u)\; \{\backslash \; displaystyle\; \backslash \; rho\; (u)\}$- это функция Дикмана.

Средний размер гладкой части числа заданного размера известен как $\zeta \; (u)\; \{\backslash \; displaystyle\; \backslash \; zeta\; (u)\}$, и известно, что он распадается намного медленнее. чем $\rho \; (u)\; \{\backslash \; displaystyle\; \backslash \; rho\; (u)\}$.

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

Далее, m называется B- powersmooth (или B- сверхрыхлым ), если все простые степени $p\; \nu \; \{\; \backslash \; displaystyle\; \backslash \; scriptstyle\; p\; ^\; \{\backslash \; nu\}\}$деление m удовлетворяет:

$p\; \nu \; \le \; B.\; \{\backslash \; displaystyle\; p\; ^\; \{\backslash \; nu\}\; \backslash \; leq\; B.\; \backslash ,\}$

Например, 720 (2 × 3 × 5) является 5-гладким, но не 5-степенным (поскольку есть несколько степеней простых чисел больше 5, например, $3\; 2\; =\; 9\; \nleqq \; 5\; \{\backslash \; displaystyle\; 3\; ^\; \{2\}\; =\; 9\; \backslash \; nleq\; 5\}$и $2\; 4\; =\; 16\; \nleqq \; 5\; \{\backslash \; displaystyle\; 2\; ^\; \{4\}\; =\; 16\; \backslash \; nleq\; 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}, и $Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\}$, однако он не будет сглаженным по набору A 3 = {3, 5}, поскольку 12 содержит фактор 4 = 2, которого нет в A 3.

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

• Сильно составное число
• Приблизительное число
• Круглое число
• Теорема Стёрмера
• Необычное число

1. ^«Окончательный глоссарий высшего математического жаргона - гладкий». Математическое хранилище. 2019-08-01. Проверено 12 декабря 2019 г.
2. ^«P-Smooth Numbers или P-friable Number». GeeksforGeeks. 2018-02-12. Проверено 12 декабря 2019 г.
3. ^Вайсштейн, Эрик У. "Smooth Number". mathworld.wolfram.com. Проверено 12 декабря 2019 г.
4. ^Хеллман, М. Э. ; Рейнери, Дж. М. (1983). Быстрое вычисление дискретных логарифмов в GF (q). Достижения в криптологии: материалы CRYPTO '82 (ред. Д. Чаум, Р. Ривест, А. Шерман). С. 3–13. DOI : 10.1007 / 978-1-4757-0602-4_1. ISBN 978-1-4757-0604-8.
5. ^«Python: Получите числа Хэмминга до заданных чисел, также проверьте, является ли данное число числом Хэмминга». w3resource. Проверено 12 декабря 2019 г.
6. ^«Проблема H: скромные числа». www.eecs.qmul.ac.uk. Проверено 12 декабря 2019 г.
7. ^Sloane, N.J.A. (ed.). «Последовательность A002473 (7-гладкие числа)». Он-лайн энциклопедия целочисленных последовательностей. OEIS Foundation.
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 г.). «Делимость, гладкость и криптографические приложения» (PDF). eprint.iacr.org. Проверено 26 июля 2017 г. f
12. ^Танака, Кейсуке; Шуга, Юдзи (20 августа 2015). Достижения в области информационной и компьютерной безопасности: 10-й международный семинар по безопасности, IWSEC 2015, Нара, Япония, 26-28 августа 2015 г., Материалы. Springer. С. 49–51. ISBN 9783319224251.
13. ^Бриггс, Мэтью Э. (17 апреля 1998 г.). «Введение в сито общего числового поля» (PDF). math.vt.edu. Блэксбург, Вирджиния: Политехнический институт и университет штата Вирджиния. Проверено 26 июля 2017 г.

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

• Вайсштейн, Эрик У. «Smooth Number». MathWorld.

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

• 2-гладкие числа: A000079 (2)
• 3-гладкие числа: A003586 (23)
• 5-гладкие числа: A051037 (235)
• 7 -гладкие числа: A002473 (2357)
• 11-гладкие числа: A051038 (etc...)
• 13-гладкие числа: A080197
• 17-гладкие числа: A080681
• 19-гладкие числа: A080682
• 23-гладкие числа: A080683