cp58
Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
A1exSun
Цитата:| А как программно сделать поиск секретной экспоненты? |
Суть задачи в том, чтобы решить d*e mod phi(n) = 1, где phi - функция эйлера, у вас значение функции 220.
Решить можно с помощью расширенного алгоритма Евклида:
Код: int euc_mod(int a, int b)
{
int x=0,y=1,g=b,u=1,v=0,m,n,q,r;
while (a!=0) {
q=g/a;
r=g%a;
m=x-u*q;
n=y-v*q;
g=a;a=r;x=u;
y=v;u=m;v=n;
}
if (x<0)
return ((x%b)+b)%b;
else
return x%b;
} |
Где "a" будет e(17), а "b" значение функции эйлера от p,q, то есть 220. |
