ВУЗ:
Составители:
Рубрика:
48
Продолжаем до тех пор, пока (x – y, N) не станет равным 1 или N (или
должно быть выполнено столько шагов, что Вам надоест ждать). Конечно, х и у
сокращаются по модулю n на каждой стадии, используя операцию x: = x –
– N*INT(x/N), и т. д. Заметим, что вышеприведённый метод значительно луч-
ше, чем сохранение a
i
в массиве; даже учитывая, что a
i
вычисляется дважды,
при этом удаётся избежать проблемы, связанной с большими массивами чисел
повышенной точности. После того, как число прошло цикл из нескольких ите-
раций, Вы знаете, что t обеспечивает (a
2t
– a
t
, N) нетривиальный делитель N.
Напишите программу, выполняющую этот алгоритм для определения
значений N со, скажем, восьмью цифрами, и проверьте этот метод умноже-
нием совместно двух или трёх простых чисел приемлемого размера для оп-
ределения значения N. Вы, вероятно, будете удивлены скорости представ-
ленного метода для значений чисел около определённого размера.
Действи-
тельно, возможно сделать его более эффективным с помощью некоторой
хитрости; версия этого метода была использована Р. П. Брентом и
Ж. М. Поллардом для факторизации огромного числа Ферма 2
256
+ 1 в 1980
г. Два простых сомножителя этого числа имели 16 и 62 цифры!
Что представляет собой
ρ
-метод? См. рисунок 2!
a
i+1
a
i+2
a
i
≡ a
j
a
i-1
a
j-1
a
2
a
j-2
a
1
Рис. 2
12. Степени
12.1. Малая теорема Ферма.
Пусть р будет простым числом, а а бу-
дет некоторым целым числом. Тогда a
p
≡ a (mod p). Если p не делит a, тогда
a
p–1
≡ 1 (mod p).
12.2. Упражнения
1. Используя 2
12
≡ 1 (mod 13), докажите, что 4 ⋅ 2
70
≡ 1 (mod 13), и отсюда
2
70
≡ 10 (mod 13). Заметьте, что это показывает, что 2
70
+ 3
70
делится на 13.
2. Аналогично пункту 1, покажите, что 2
98
+ 3
98
делится на 13, а
2
100
+ 3
100
делится на 97.
Страницы
- « первая
- ‹ предыдущая
- …
- 46
- 47
- 48
- 49
- 50
- …
- следующая ›
- последняя »
