2.1. Метод пробных делений.
Этот метод является методом специального назначения и рекомендуется для отсеивания маленьких делителей на первом шаге. Если известно, что число не имеет малых делителей (например, модуль RSA), то этот метод не стоит применять.
Прежде чем приступать к факторизации числа этим методом, следует выделить все степени двойки и тройки.
Задается некая теоретическая граница B ≤, которая задает максимальную величину испытываемых делителей и обусловливается доступным объемом памяти и вычислительными возможностями, а также некоторыми априорными сведениями о структуре числаn.
Если В невелико, то строим заранее таблицу простых чисел, меньших или равных В и проверяем делимость n на эти числа.
Иначе выбираем числа d1=5, d2=5+2=7, d3=d2+4=11, d5=d4+2, … , dk > B. (чередуем шаг +2 и +4 с тем, чтобы отсеять числа, кратные «2» и «3»).
Эти d1, … , dk являются возможными делителями n. Осуществляем пробные деления на di (i = ). При этом действия осуществляются в следующем порядке:
Для каждого i:
Ш.1. Генерируем di.
Ш.2. Осуществляем пробное деление на di. Если di\n, то n=n/di и повторяем
Шаг 2. Если di не делит n, то идем на Шаг 3.
Ш.3. Уничтожаем di, освобождаем память.
Заметим, что все малые делители, выделенные вышеуказанным способом, будут простыми.
- Теоретико-числовые методы в криптографии
- Аннотация.
- Предисловие
- Введение
- Глава 1. Основы теории чисел. §1. Теория делимости.
- 1.1. Основные понятия и теоремы.
- 1.2. Наибольший общий делитель.
- 1.3 Нок (наименьшее общее кратное)
- 1.4. Простые числа
- Решето Эратосфена
- 1.5. Единственность разложения на простые сомножители.
- 1.6. Асимптотический закон распределения простых чисел.
- §2. Функция Эйлера.
- 2.1. Мультипликативные функции.
- 2.2. Функция Эйлера.
- §3. Теория сравнений
- 3.1. Свойства сравнений:
- 3.2. Полная система вычетов.
- 3.3. Приведенная система вычетов
- 3.4. Обратный элемент.
- 3.5. Алгебраические структуры на целых числах.
- 3.6. Теоремы Эйлера и Ферма. Тест Ферма на простоту.
- Тест Ферма на простоту
- 3.7. Применение теоремы Эйлера в rsa:
- §4. Сравнения с одним неизвестным
- 4.1. Сравнения первой степени.
- 4.2. Система сравнений первой степени. Китайская теорема об остатках.
- 4.3. Применения китайской теоремы об остатках.
- 4.4. Сравнения любой степени по простому модулю.
- 4.5. Сравнения любой степени по составному модулю.
- §5. Теория квадратичных вычетов
- 5.1. Квадратичные вычеты по простому модулю.
- 5.2. Символ Лежандра. Символ Якоби.
- Свойства символа Лежандра:
- Свойства символа Якоби:
- 5.3. Тест на простоту Соловея-Штрассена.
- Тест Соловея-Штрассена:
- 5.4. Решение квадратичных сравнений по простому модулю.
- 5.5. Квадратичные сравнения по составному модулю.
- 5.6. Тест на простоту Миллера-Рабина.
- 5.7. Связь задач извлечения квадратных корней и факторизации по модулю rsa. Криптосистема Рабина.
- 5.8. Квадраты и псевдоквадраты.
- 5.9. Числа Блюма.
- §6. Первообразные корни и индексы. Порождающий элемент и дискретный логарифм.
- 6.1. Основные понятия и теоремы.
- 6.2. Существование первообразных корней по модулю p.
- 6.3. Первообразные корни по модулям pα, 2pα.
- 6.4. Нахождение первообразных корней по простому модулю.
- 6.5. Существование и количество первообразных корней.
- 6.6. Дискретные логарифмы.
- 6.7. Проблема Диффи-Хеллмана.
- 6.8. Условная стойкость шифра Эль Гамаля.
- §7. Построение доказуемо простых чисел общего и специального вида.
- 7.1. Теорема Сэлфриджа и доказуемо простые числа общего вида на основании полного разложения (n—1).
- 7.2. Теорема Поклингтона и доказуемо простые числа общего вида на основании частичного разложения (n—1).
- 7.3. Числа Ферма. Теорема Пепина.
- 7.4. Числа Мерсенна.
- 7.5. Теорема Диемитко и процедура генерации простых чисел заданной длины гост р 34.10-94.
- Глава 2. Алгебраические основы теории чисел.
- §1. Основные понятия алгебры.
- 1.1. Начальные понятия.
- 1.2. Делимость в кольцах.
- 1.3. Деление с остатком.
- 1.4. Основная теорема арифметики.
- §2. Конечные поля и неприводимые многочлены.
- §3. Кольца многочленов.
- 3.1. Кольца многочленов.
- 3.2. Кольцо многочленов Zp[X].
- 3.3. Конечные поля многочленов.
- Глава 3. Алгоритмы в криптографии и криптоанализе. §1. Элементы теории сложности.
- §2. Алгоритмы факторизации.
- 2.1. Метод пробных делений.
- 2.2. Метод Ферма.
- 2.3. Метод квадратичного решета.
- 2.6. Методы случайных квадратов.
- §3. Алгоритмы дискретного логарифмирования.
- 3.1. Метод прямого поиска.
- 3.2. Шаг младенца – шаг великана.
- 3.4. Алгоритм Полига-Хеллмана.
- 3.5. Алгоритм исчисления порядка (index-calculus algorithm).
- Задачи и упражнения.
- Упражнения к Главе 2.
- Ответы к упражнениям.
- 1. Пояснительная записка
- 1.1. Цели и задачи дисциплины
- 1.2. Требования к уровню освоения содержания дисциплины
- 2. Объем дисциплины и виды учебной работы
- 3. Тематический план изучения дисциплины
- 4. Содержание разделов дисциплины
- 6. Вопросы к экзаменам
- 7.Литература основная:
- Дополнительная:
- Оглавление