- •Глава 3. Машинная арифметика
- •3.1. Машинное представление целых чисел
- •3.2. Арифметика чисел с фиксированной точкой
- •3.3. Арифметика чисел с плавающей точкой
- •3.3.2. Сложение чисел в форме с плавающей точкой
- •3.3.3. Умножение и деление чисел в форме с плавающей точкой
- •3.3.4. Точность арифметических операций с числами в форме с плавающей точкой
- •3.4. Вычисления с многократной точностью
- •3.4.1. Вычисления с большими целыми числами
- •3.4.2. Модулярная арифметика
- •3.4.3. Ускорение процесса умножения
- •3.5. Эффективные алгоритмы вычисления степеней
- •3.5.1. Бинарный метод
- •3.5.2. Метод факторизации показателя
- •3.6. Эффективные действия с дробями
- •3.7. Алгоритм Евклида для больших чисел
- •3.8. Алгоритмы разложения на простые множители
- •3.8.1.Метод пробных делений
- •3.8.2. Метод Ферма
- •3.8.3. Метод Крайчика
3.8.2. Метод Ферма
Метод Ферма основан на формуле разности квадратов: если нечётное , то, где
. Если множители нетривиальны (отличны оти), то дальнейшая факторизация сводится к работе с меньшими числами. При этомявляется полным квадратом:. Поиск такогоможно начинать с проверки наименьшего значения, при котором, то есть с. Если не является квадратом, то далее проверяются .Если при всех разность не является квадратом, то— простое(см. [1]).
Пример. Факторизация числа . Имеем;
;
—не является квадратом;
—не является квадратом;
.
Итак, .
Дальнейшая факторизация осуществляется просто: , и.В итоге .
3.8.3. Метод Крайчика
В этом методе нетривиальный делитель числаищется как НОД числаи числа:; при этомиподбираются так, чтобы заведомо выполнялось условие. Имеет место
Теорема. Пусть выполняются три условия:
1) илежат в разных классах вычетов по модулю;
2) и, лежат в разных классах вычетов по модулю;
3) .
Тогда .
Пусть, . Численные эксперименты показывают, что в разложении на множители чисел(остатков от деленияна , так что) довольно часто участвуют только небольшие простые множители (такие числа называютгладкими). Путём перемножения некоторых из сравнений
, … ,,
в правой части удаётся получить полный квадрат:. Тогда в левой части сравнения квадрат получается автоматически:, где.
Если при этом для иоказываются выполненными первые два условия теоремы, то наибольший общий делитель(то есть нетривиальный делитель) находится с помощью алгоритма Евклида или каким-нибудь другим методом (см. п. 3.7).
Пример. Рассмотрим факторизацию числа . Здесь. Для чиселпри последовательно получаем:
;
;
;
;
;
.
Полным квадратом оказывается произведение
.
Теперь
,
,
и полагаем заново
.
Проверяем: .