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

В теории чисел число 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 ^а × 3 ^б × 5 ^с, где 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 является еще одним примером конструктивного использования гладкости для получения доказуемо безопасной конструкции .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В отличие от 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} и $\mathbb {Z}$ , однако оно не будет гладким на множестве A ₃ = {3, 5}, поскольку 12 содержит множитель 4 = 2 ², и ни 4, ни 2 не находятся в A ₃ .

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

См. также

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

^ «П-гладкие числа или П-рыхлое число» . Гики для Гиков . 12 февраля 2018 г. Проверено 12 декабря 2019 г.
^ Вайсштейн, Эрик В. «Гладкое число» . mathworld.wolfram.com . Проверено 12 декабря 2019 г.
^ Хеллман, Мэн ; Рейнери, Дж. М. (1983). «Быстрое вычисление дискретных логарифмов в GF ( q )». Достижения в криптологии – Труды Крипто 82 . стр. 3–13. дои : 10.1007/978-1-4757-0602-4_1 . ISBN 978-1-4757-0604-8 .
^ Слоан, Нью-Джерси (ред.). «Последовательность A003586 (3-гладкие числа)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
^ «Python: получить числа Хэмминга до заданных чисел, а также проверить, является ли данное число числом Хэмминга» . w3ресурс . Проверено 12 декабря 2019 г.
^ «Проблема H: скромные числа» . www.eecs.qmul.ac.uk. Проверено 12 декабря 2019 г.
^ Слоан, Нью-Джерси (ред.). «Последовательность A002473 (7-гладкие числа)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
^ Аабо, Асгер (1965), «Некоторые математические таблицы Селевкидов (расширенные обратные числа и квадраты обычных чисел)», Journal of Cuneiform Studies , 19 (3): 79–86, doi : 10.2307/1359089 , JSTOR 1359089 , MR 0191779 , S2CID 164195082 .
^ Лонге-Хиггинс, ХК (1962), «Письмо музыкальному другу», Music Review (август): 244–248 .
^ Дейкстра, Эдсгер В. (1981), Упражнение Хэмминга в SASL (PDF) , отчет EWD792. Первоначально это была рукописная записка, распространявшаяся в частном порядке .
^ Наккеш, Дэвид; Шпарлинский, Игорь (17 октября 2008 г.). «Делимость, гладкость и криптографические приложения» (PDF) . eprint.iacr.org . arXiv : 0810.2067 . Проверено 26 июля 2017 г. ж
^ Ким, Тэчан; Тибучи, Мехди (2015). «Недопустимые атаки по кривой в настройках GLS». МВСЕК 2015 .
^ Бриггс, Мэтью Э. (17 апреля 1998 г.). «Введение в решето общего числового поля» (PDF) . math.vt.edu . Блэксбург, Вирджиния: Политехнический институт и Государственный университет Вирджинии . Проверено 26 июля 2017 г.

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

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

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

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

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

2-гладкие числа: А000079 (2 ^я)
3-гладкие цифры: А003586 (2 ^я3 ^дж)
5-гладкие цифры: A051037 (2 ^я3 ^дж5 ^к)
7-гладкие цифры: А002473 (2 ^я3 ^дж5 ^к7 ^л)
11-гладкие цифры: А051038 (и т.д...)
13-гладкие цифры: A080197
17-гладкие цифры: А080681
19-гладкие цифры: A080682
23-гладкие цифры: A080683

[1] «П-гладкие числа или П-рыхлое число» . Гики для Гиков . 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), «Некоторые математические таблицы Селевкидов (расширенные обратные числа и квадраты обычных чисел)», 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 . arXiv : 0810.2067 . Проверено 26 июля 2017 г. ж

[12] Ким, Тэчан; Тибучи, Мехди (2015). «Недопустимые атаки по кривой в настройках GLS». МВСЕК 2015 .

[13] Бриггс, Мэтью Э. (17 апреля 1998 г.). «Введение в решето общего числового поля» (PDF) . math.vt.edu . Блэксбург, Вирджиния: Политехнический институт и Государственный университет Вирджинии . Проверено 26 июля 2017 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

v т и Наборы целых чисел на основе делимости
Overview	Integer factorization Divisor Unitary divisor Divisor function Prime factor Fundamental theorem of arithmetic
Factorization forms	Prime Composite Semiprime Pronic Sphenic Square-free Powerful Perfect power Achilles Smooth Regular Rough Unusual
Constrained divisor sums	Perfect Almost perfect Quasiperfect Multiply perfect Hemiperfect Hyperperfect Superperfect Unitary perfect Semiperfect Practical Erdős–Nicolas
With many divisors	Abundant Primitive abundant Highly abundant Superabundant Colossally abundant Highly composite Superior highly composite Weird
Aliquot sequence-related	Untouchable Amicable (Triple) Sociable Betrothed
Base-dependent	Equidigital Extravagant Frugal Harshad Polydivisible Smith
Other sets	Arithmetic Deficient Friendly Solitary Sublime Harmonic divisor Descartes Refactorable Superperfect