扩展欧几里得算法与模乘逆元的程序

2019-04-13 12:47发布

站内文章 / 模拟电子
14514 0 1633
代码来自维基百科的Extended Euclidean algorithm。 扩展欧几里得算法程序： function extended_gcd(a, b) s := 0; old_s := 1 t := 1; old_t := 0 r := b; old_r := a while r ≠ 0 quotient := old_r div r (old_r, r) := (r, old_r - quotient * r) (old_s, s) := (s, old_s - quotient * s) (old_t, t) := (t, old_t - quotient * t) output "Bézout coefficients:", (old_s, old_t) output "greatest common divisor:", old_r output "quotients by the gcd:", (t, s)
两段计算模乘逆元的程序分别如下： function inverse(a, n) t := 0; newt := 1; r := n; newr := a; while newr ≠ 0 quotient := r div newr (t, newt) := (newt, t - quotient * newt) (r, newr) := (newr, r - quotient * newr) if r > 1 then return "a is not invertible" if t < 0 then t := t + n return tfunction inverse(a, p) t := 0; newt := 1; r := p; newr := a; while newr ≠ 0 quotient := r div newr (r, newr) := (newr, r - quotient * newr) (t, newt) := (newt, t - quotient * newt) if degree(r) > 0 then return "Either p is not irreducible or a is a multiple of p" return (1/r) * t

热门文章