О количестве регулярных целых чисел по модулю $n$ и его значении для криптографии

Основная информация

• ID статьи: 2304.02471
• Название: On the Number of Regular Integers Modulo $n$ and Its Significance to Cryptography
• Авторы: Klaus Dohmen, Mandy Lange-Geisler (Hochschule Mittweida, Германия)
• Классификация: math.CO (комбинаторика), math.GR (теория групп), math.NT (теория чисел)
• Дата публикации: 9 октября 2025 г. (версия arXiv)
• Ссылка на статью: https://arxiv.org/abs/2304.02471v6

Аннотация

В данной работе на основе принципа биекции и принципа включения-исключения предоставляются четыре комбинаторных доказательства формулы Morgado для количества регулярных целых чисел по модулю $n$. Эта формула соответствует последовательности A055653 в OEIS, где целое число $m$ называется регулярным по модулю $n$ тогда и только тогда, когда сравнение $m^2x \equiv m \pmod{n}$ имеет решение в кольце целых чисел $\mathbb{Z}$. Для подчёркивания значимости исследования авторы связывают данную последовательность и формулу Morgado с недавно предложенным обобщением криптосистемы RSA на случай нескольких простых чисел и степеней.

Исследовательский контекст и мотивация

Основная проблема

Основной вопрос, решаемый в данном исследовании, заключается в вычислении количества регулярных целых чисел по модулю $n$ и изучении их значения в криптографии.

Значимость проблемы

1. Теоретическое значение: Концепция регулярных целых чисел была впервые введена Morgado в 1972 году и представляет собой важный комбинаторный объект в теории чисел. Формула подсчёта включает унитарные делители и функцию Эйлера — фундаментальные понятия теории чисел.
2. Практическое применение: В предложенном авторами обобщении криптосистемы RSA регулярные целые числа составляют пространство сообщений, которые могут быть правильно расшифрованы. Следовательно, их количество напрямую влияет на вероятность корректной расшифровки криптосистемы.

Ограничения существующих методов

Предыдущие доказательства формулы Morgado в основном опирались на мультипликативность функции $\varrho(n)$, что не обеспечивало интуитивного комбинаторного объяснения. Данная работа предоставляет более глубокое понимание посредством чистых комбинаторных методов.

Исследовательская мотивация

Мотивация авторов исходит из практических потребностей, возникших при работе над обобщением RSA для нескольких простых чисел и степеней, где требуется оценить вероятность корректной расшифровки произвольного сообщения.

Основные вклады

1. Четыре комбинаторных доказательства: На основе принципа биекции и принципа включения-исключения предоставляются четыре различных комбинаторных доказательства формулы Morgado
2. Построение схемы кодирования: Четвёртое доказательство даёт явное кодирование регулярных целых чисел, что может быть полезно для дальнейшего изучения последовательности A055653
3. Криптографическое применение: Связь теории регулярных целых чисел с обобщением криптосистемы RSA раскрывает практическое значение этого теоретико-числового концепта
4. Теоретические insights: Комбинаторные методы естественным образом приводят к мультипликативности функции $\varrho(n)$

Подробное описание методов

Определение задачи

Входные данные: Натуральное число $n$Выходные данные: Количество регулярных целых чисел по модулю $n$ — $\varrho(n)$Ограничения: Целое число $m$ является регулярным по модулю $n$ тогда и только тогда, когда существует $x \in \mathbb{Z}$ такое, что $m^2x \equiv m \pmod{n}$

Основы теории

Определение: Целое число $m$ называется регулярным по модулю $n$, если сравнение $m^2x \equiv m \pmod{n}$ имеет целочисленное решение.

Формула Morgado (теорема 1): $\varrho(n) = \sum_{d \parallel n} \varphi(d)$ где $d \parallel n$ означает, что $d$ является унитарным делителем $n$ (то есть $d|n$ и $\gcd(d, n/d) = 1$).

Ключевые свойства (предложение 2): Для любых $n \in \mathbb{N}$ и $m \in \mathbb{Z}$ следующие условия эквивалентны:

• (a) $m$ является регулярным по модулю $n$
• (b) $\gcd(m^2, n) = \gcd(m, n)$
• (c) $\gcd(m, n) \parallel n$

Четыре метода доказательства

Метод 1: Доказательство через отношение эквивалентности

Путём определения отношения эквивалентности $m_1 \sim m_2 \Leftrightarrow \gcd(m_1, n) = \gcd(m_2, n)$ на множестве $\mathbb{Z}^{\text{reg}}_n$ устанавливается биекция между классами эквивалентности и $\mathbb{Z}^*_{n/d}$.

Метод 2: Чистое доказательство через биекцию

Конструируется отображение $f_n: \mathbb{Z}^{\text{reg}}_n \to \{(d, d') | d \parallel n, d' \in \mathbb{Z}^*_d\}$: $f_n(m) := \left(\frac{n}{\gcd(m,n)}, m \bmod \frac{n}{\gcd(m,n)}\right)$

Обратное отображение имеет вид: $f_n^{-1}(d, d') = \frac{n}{d}\left(((n/d \bmod d)^{-1}d') \bmod d\right)$

Метод 3: Доказательство через несократимые дроби

Каждому $m \in \mathbb{Z}^{\text{reg}}_n$ ставится в соответствие несократимая дробь $m/n$. Доказывается, что знаменатели этих дробей совпадают со всеми унитарными делителями $n$.

Метод 4: Доказательство через принцип включения-исключения

Для каждого простого делителя $p \in P(n)$ определяется: $A_p = \{m \in \mathbb{Z}_n | 0 < m_p < n_p\}$ где $m_p$ обозначает показатель степени $p$ в разложении $m$ на простые множители. Затем применяется принцип включения-исключения.

Технические инновации

1. Комбинаторная перспектива: В отличие от предыдущих доказательств, основанных на мультипликативности, данная работа предоставляет интуитивное комбинаторное объяснение
2. Построение биекции: Второе доказательство даёт явное кодирование и алгоритм декодирования регулярных целых чисел
3. Многоаспектный анализ: Четыре доказательства раскрывают структуру регулярных целых чисел с разных углов зрения
4. Связь с криптографией: Впервые устанавливается связь между теорией регулярных целых чисел и современными криптографическими приложениями

Экспериментальная установка

Численная верификация

Теоретические результаты проверяются на конкретных примерах:

Пример: Случай $n = 20$

• Унитарные делители: $1, 4, 5, 20$
• $\varphi(1) = 1, \varphi(4) = 2, \varphi(5) = 4, \varphi(20) = 8$
• Предсказанное значение: $\varrho(20) = 1 + 2 + 4 + 8 = 15$
• Регулярные целые числа: $\{0, 1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19\}$
• Проверка: $|\mathbb{Z}^{\text{reg}}_{20}| = 15$ ✓

Примеры отображений

В работе подробно представлены все соответствия отображения $f_{20}$, что подтверждает корректность биекции.

Результаты экспериментов

Теоретическая верификация

Все четыре доказательства успешно устанавливают корректность формулы Morgado, каждый метод предоставляет уникальные комбинаторные insights.

Результаты криптографического применения

В обобщении RSA для нескольких простых чисел и степеней:

• Вероятность корректной расшифровки: $\frac{\varrho(n)}{n} = \frac{1}{n}\sum_{d \parallel n} \varphi(d)$
• Нижняя граница: Для $n = p_1^{e_1} \cdots p_r^{e_r}$ (где $p_i$ — $k$-битовые простые числа) имеет место $\frac{\varrho(n)}{n} \geq 1 - \frac{r}{2^{k-1}}$
• Практическое значение: При $k = 1024$ почти все сообщения расшифровываются корректно

Связанные работы

Историческое развитие

1. Morgado (1972): Впервые определил концепцию регулярных целых чисел и дал формулу подсчёта
2. Alkam & Osba (2008): Дальнейшее изучение свойств регулярных целых чисел
3. Apostol & Petrescu (2013): Исследование экстремальных свойств связанных функций
4. Tóth (2008): Асимптотические результаты и анализ связанных функций

Вклад данной работы

По сравнению с существующими работами, данная статья впервые предоставляет чистые комбинаторные доказательства и устанавливает важную связь с криптографией.

Заключение и обсуждение

Основные выводы

1. Формула Morgado имеет богатые комбинаторные интерпретации, каждое доказательство раскрывает структуру на разных уровнях
2. Регулярные целые числа играют ключевую роль в обобщении криптосистемы RSA
3. Для практических параметров вероятность корректной расшифровки близка к 1

Ограничения

1. Криптографическое применение ограничено конкретным обобщением RSA
2. Асимптотический анализ требует дальнейших исследований
3. Анализ вычислительной сложности недостаточно глубок

Направления будущих исследований

1. Разработка более точных вероятностных границ
2. Изучение асимптотических свойств последовательности A055653
3. Исследование других криптографических приложений

Глубокая оценка

Преимущества

1. Теоретическая инновация: Четыре комбинаторных доказательства каждое по-своему уникальны и обогащают понимание регулярных целых чисел
2. Методологическая строгость: Доказательства логически безупречны и ясно изложены
3. Прикладная ценность: Связь с криптографией повышает практическую значимость теоретического исследования
4. Ясное изложение: Логическая структура работы хорошо организована с обилием примеров

Недостатки

1. Ограниченность приложений: Криптографическое применение ограничено обобщением RSA, предложенным самими авторами
2. Анализ сложности: Отсутствует глубокий анализ алгоритмической сложности
3. Экспериментальная верификация: Представлены только малые численные примеры, отсутствуют крупномасштабные вычислительные эксперименты

Влияние

1. Академическая ценность: Предоставляет новые подходы к исследованиям в теоретико-числовой комбинаторике
2. Практический потенциал: Имеет потенциальное применение в криптографии
3. Воспроизводимость: Теоретические доказательства полны, результаты легко верифицируются

Области применения

1. Теоретические исследования в теории чисел и комбинаторике
2. Криптографические приложения, связанные с модульной арифметикой
3. Приложения, требующие вычисления размера специальных множеств целых чисел

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

В работе цитируется 8 соответствующих источников, охватывающих основные этапы развития теории регулярных целых чисел и связанные математические основы, предоставляя читателям полный контекст.

Общая оценка: Это высокачественная математическая работа, которая углубляет понимание классической теоретико-числовой задачи посредством различных комбинаторных методов и успешно устанавливает связь с современной криптографией. Теоретический вклад работы солиден, перспективы применения широки, и она представляет ценный результат в области теоретико-числовой комбинаторики.