Интегрированные сети ISDN


Таблица - часть 4


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 не могут быть получены никогда.


Начало  Назад  Вперед