Наткнулся на тест для программистов по проверке алгоритмического мышления. один вопрос загнал меня в ступор.
Нужно найти алгоритм для такой задачи
Сообщение от :
p=8; q=16;
n=p*q;
F(n)=(p-1)*(q-1);
Выбрать значение переменной E,с учетом условия:
1<e<=F(n), НОД(E; F(n))=1;
Определить значение d, удовлетворяющее условию:
e*d=1(mod F(n));
d<n;
Сломал весь мозг, пройти не смог.
п.с. НОД -Наибольший общий делитель.
[Ответ]
xxx-men 18:10 18.02.2009
Код:
//--------------както делаем связанный список--------------------
struct _e
{
int e;
_e* pNext;
};
_e* listE = 0;
//---------------------------------------------------------------
int NOD(int a, int b)
{
//гдето слизать алгоритм
//нахождения наибольшего общего делителя
return Result;
};
int main()
{
int p=8;//
int q=16;//или спросить у пользователя
int n=p*q;
int F = (p-1)*(q-1);
for (int e = 2; e<F; e++)
{
if(NOD(e,F)==1)
{
//----------------- добавляем в список подходящие Е----------
_e* tmp = new _e;
tmp->e=e;
tmp->pNext=listE;
listE=tmp;
//----------------------------------------------------------------------
};
};
while (listE)
{
int e = listE->e;
int unknown = 0;//нифига непонял что означает 1(mod F(n));
int d = unknown/e;
if (d<n)
{
printf(d);//кудато сохраняем\выводим результат
};
//--------------- так пробегамся по списку значений Е ---------
_e* tmp = listE->pNext;
delete listE;
listE = tmp;
//-------------------------------------------------------------
};
return 0;
};
связанный список можно заменить согласно релегиозным убеждениям
[Ответ]
][irurg 19:48 18.02.2009
xxx-men, мне кажется алгоритмическое мышление и знание синтаксиса с++ это немного разное ) вопрос как раз в том что бы расписать алгоритм нахождения E и D по известным зависимостям. НОД(E; F(n))=1; насколько понимаю нужно из алгоритма Евклида вытаскивать..
ЗЫ хотя что такое 1(mod F(n)); действительно непонятно
[Ответ]
][irurg, да все пучком у xxx-men - разве что не псевдокод. В принципе можно наверно попроще задачу решить без перебора, но сходу пока решения не видится.
> e*d=1(mod F(n));
Видимо надо воспринимать как e*d (mod F(n)) = 1.
[Ответ]
