Задачка по RSA (Срочно)

http://www.citforum.ru/security/belyaev_book/its2000_42.shtml

http://book.itep.ru/6/rsa_642.htm

Позабывал уже всю математику:-((((

Итак: p=3 q=11

Вычисляем n; n=3*11=33

Выбираем е; е=17

Выбираем d; Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.

И как это решить?

> Выбираем d; Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах. 

> И как это решить?

это стандартное рассуждение:

Если есть ур-е a*x + b*y = 1
И a и b взаимно просты.

то берутся a и b и к ним проводится ал-ритм Евклида:

a b
a1 b
a1 b1
a2 b1
a2 b2
...
an bn

где an это уже их НОД=1, а bn это ноль.

Теперь ты смотришь с конца.
an*1 + bn*0 = 1

Дальше b[n-1] это bn плюс сколько-то an.  Ты подстраиваешь уравнение и получаешь a[n]*u + b[n-1]*v = 1

И так двигаешься к началу и получаешь a*x + b*y = 1.

так ты получишь одну пару, все пары получаются сдвигом на решение однородного уравнения ax + by = 0. Это просто кратные пары (НОК/b -НОК/a)