Помогите понять этот код нахождения обратного значения по модулю $%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($%предпоследнее$%)$%?
задан 11 Янв '12 1:36 Ray |
тип данных вектор - это массив (в данном случае 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 в следующий проход. отвечен 11 Янв '12 4:27 Bl_cK Ты фактически объяснил мне строчки кода. А мне нужен алгоритм.
(11 Янв '12 15:11)
Ray
|