Гладкий номер

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

В теории чисел 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 ⁴ × 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 количество целых 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)}$

Средний размер гладкой части числа заданного размера известен как , и известно, что он затухает гораздо медленнее, чем . ^[12] ${\displaystyle \zeta (u)}$ ${\displaystyle \rho (u)}$

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

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

Далее, 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 - гладкого порядка .

Сглаживание набора A

Более того, 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-рыхлые числа» . Гики для гиков . 12 февраля 2018 г. Проверено 12 декабря 2019 г.
2. Вайсштейн, Эрик В. «Гладкое число». mathworld.wolfram.com . Проверено 12 декабря 2019 г.
3. Хеллман, Мэн ; Рейнери, Дж. М. (1983). «Быстрое вычисление дискретных логарифмов в GF ( q )». Достижения в криптологии – Труды Крипто 82 . стр. 3–13. дои : 10.1007/978-1-4757-0602-4_1. ISBN 978-1-4757-0604-8.
4. Слоан, Нью-Джерси (ред.). «Последовательность A003586 (3-гладкие числа)». Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
5. «Python: получить числа Хэмминга до заданных чисел, а также проверить, является ли данное число числом Хэмминга» . w3ресурс . Проверено 12 декабря 2019 г.
6. «Проблема H: скромные числа». www.eecs.qmul.ac.uk. _ Проверено 12 декабря 2019 г.
7. Слоан, Нью-Джерси (ред.). «Последовательность A002473 (7-гладкие числа)». Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
8. Аабо, Асгер (1965), «Некоторые математические таблицы Селевкидов (расширенные обратные числа и квадраты обычных чисел)», Журнал клинописных исследований , 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 . arXiv : 0810.2067 . Проверено 26 июля 2017 г.ж
12. Танака, Кейсуке; Шуга, Юджи (20 августа 2015 г.). Достижения в области информационной и компьютерной безопасности: 10-й международный семинар по безопасности, IWSEC 2015, Нара, Япония, 26-28 августа 2015 г., Материалы. Спрингер. стр. 49–51. ISBN 9783319224251.
13. Бриггс, Мэтью Э. (17 апреля 1998 г.). «Введение в решето общего числового поля» (PDF) . math.vt.edu . Блэксбург, Вирджиния: Политехнический институт и Государственный университет Вирджинии . Проверено 26 июля 2017 г.

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

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

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

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

В Интернет-энциклопедии целочисленных последовательностей (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-гладкие цифры: А051038 (и т.д...)
• 13-гладкие цифры: A080197
• 17-гладкие цифры: А080681
• 19-гладкие цифры: A080682
• 23-гладкие цифры: A080683