Помогите понять этот код нахождения обратного значения по модулю $%N$%. Т.е. по сути решается уравнение $%a \ast x=1 \mod N$%. Сначала я понимаю: по алгоритму Евклида записываются множители в $%Q$%. Дальше я лишь знаю, что switch связан с цепными дробями и от них дальше "пляшут". Первый case возвращает $%1$%, если числа не взаимно просты. $%Q$% пересчитываются по формуле $%Q = Q(i) \ast Q(i+1)+Q(i-2)$%. Результат по формуле: $%-1^{(n-1)}*Q($%предпоследнее$%)$%. В коде $%-2$%, т.к. вектор хранит одно "запасное". Если $%-1^{(n-1)}$% положительное понятно. А вот если отрицательное, то почему возвращает $%N-Q($%предпоследнее$%)$%?

int Reverse(int x, int N)
{
    vector<int> Q;

    int NN=N;
    int tmp;
    while(x)
    {
        Q.push_back(NN/x);
        tmp=NN%x;
        NN=x;
        x=tmp;
    }
    switch(Q.size())
    {
        case 1:
            return 1;
        case 2:
            return N-Q[0];
        default:
            Q[1]=Q[1]*Q[0]+1;
            for(int i=2;i<Q.size()-1;i++)
            {
                Q[i]=Q[i]*Q[i-1]+Q[i-2];
            }
            if(Q.size()%2==1)
                return Q[Q.size()-2];
            return N-Q[Q.size()-2];
    }

}

задан 11 Янв '12 1:36

изменен 11 Янв '12 11:28

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

10|600 символов нужно символов осталось
0

тип данных вектор - это массив (в данном случае INT'eger-ов) При первом проходе while() в нулевой индекс массива пишется целая частть от деления NN на x; tmp присваивается значение остатка от деления NN на x; NN приравнивается к x; x приравнивается к tmp; т.о если остаток (x)=0 в дело вступает switch. Если в векторе (массиве) находятся 2 значения (Q[0], Q[1]) то именно case 2 и возвращает вычисленное N-Q[0]. 2 значения могут быть лишь в одном случае: при (x)!=0 (остаток от деления NN на x не равен нулю) после первого прохода while(), но (x)=0 в следующий проход.
Например: (1) 5 mod 2=1; (2) 2 mod 1=0. => Q[0]=2,Q[1]=1. N-Q[0]=5-2=3.

ссылка

отвечен 11 Янв '12 4:27

Ты фактически объяснил мне строчки кода. А мне нужен алгоритм.

(11 Янв '12 15:11) Ray
10|600 символов нужно символов осталось
0

Я понял! Результат вычисляется по формуле: −1 (n−1)∗Q(предпоследнее ) Если результат отрицательный (-xmodN), то нам надо прибавить N. Просто с толку сбил вид записи: N-x. Так понятней: -x+N.

ссылка

отвечен 11 Янв '12 15:12

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×75

задан
11 Янв '12 1:36

показан
1749 раз

обновлен
11 Янв '12 17:33

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru