Намиране обратно пропорционални модул
Намирането на обратен елемент на модула. Това е, което искате да намерите, така че. Или ако пишем по различен начин :. Първо, имайте предвид, че елементът на пръстен е обратимо, ако и само ако GCD (а, п) = 1. Това означава, че отговорът не е винаги. От определението на алгоритъма на обратен елемент трябва да се прави.
- Вход: от.
- Резултат: обратно към пръстена, ако има такъв.
- Използвайте удължен Euclidean алгоритъм за намиране на х и у, така че брадва + NY = г.
- Ако D> 1, тогава обратен елемент не съществува. В противен случай, той се връща х.