y=-15+(30/3)t x=35 –(69/3)t для целого t
Если мы проделаем то же для произвольного равенства ax+by=(a,b), мы возможно получим один из коэффициентов равным нулю, а другой – (a,b). В действительности эта процедура представляет собой алгоритм Евклида для нахождения наибольшего общего делителя.
Важно то, что этот процесс реализуем на ЭВМ даже в случае, когда a и b имеют несколько сотен значащих цифр. Легко показать, что 600-значное число не потребует более чем 4000 уравнений. Теорема 1 справедлива и для простых чисел.
|
Следствие 1. |
Если p является простым числом, ar є pas и a № 0, тогда r є s. |
Следствие 2. |
Если p простое число и a № 0 mod p, тогда для любого b существует y, для которого ay є pb. |
Следствие 3. |
("Теорема о китайском остатке"). Если (p,q)=1, тогда для любого a,b существует n, для которого n є pa и nє qb. |
Во многих криптографических приложениях используется:
a a2 a3 … mod p, где a и p целые числа.
Оказывается, можно выполнить такие вычисления даже для случая, когда в указанную процедуру вовлечены достаточно большие числа, например:
432678 mod 987.
Фокус заключается в том, что берется число и осуществляется возведение в квадрат.
4322 = 186624; 186624 mod 987 = 81; 4324 mod 987 = 812 mod 987 = 639
4328 -> 6392 mod 987 -> 690 …. 432512 -> 858
так как 678= 512+128+32+4+2, то:
432678->(81)(639)….(858) -> 204
Вычисления с использованием показателя включают в себя ограниченное число умножений. Если числа содержат несколько сотен цифр, необходимы специальные подпрограммы для выполнения таких вычислений. Рассмотрим последовательность степеней 2n mod 11:
2 4 8 5 10 9 7 3 6 1
Здесь числа от 1 до 10 появляются в виде псевдослучайной последовательности.
Теорема 2
Пусть p является простым числом. Существует такое a, что для каждого 1Ј b Ј p-1, существует такое 1Ј x Ј p-1, что axє pb, a не обязательно равно 2.
Степени 2 mod 7 равны 2, 4, 1. Далее числа повторяются, а числа 3, 5, или 6 не могут быть получены никогда.