From 548b164a2dd4422e3273ff2abc0fb6803a76ada7 Mon Sep 17 00:00:00 2001 From: Luke Kenneth Casson Leighton Date: Tue, 5 Apr 2022 16:12:17 +0100 Subject: [PATCH] code-comments, restructure gfpinv slightly --- gf_reference/gfpinv.py | 32 ++++++++++++++++++++------------ 1 file changed, 20 insertions(+), 12 deletions(-) diff --git a/gf_reference/gfpinv.py b/gf_reference/gfpinv.py index ba1494e..15c1f2c 100644 --- a/gf_reference/gfpinv.py +++ b/gf_reference/gfpinv.py @@ -4,6 +4,7 @@ from .state import ST def gfpinv(a): # based on Algorithm ExtEucdInv from: # https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.5233&rep=rep1&type=pdf + # designed to be dead-easy (and efficient) to implement in hardware p = ST.GFPRIME assert p >= 2, "GFPRIME isn't a prime" assert a != 0, "TODO: decide what happens for division by zero" @@ -11,10 +12,13 @@ def gfpinv(a): if p == 2: return 1 # the only value possible + # initial values` u = p v = a r = 0 s = 1 + + # main loop while v > 0: # implementations could use count-zeros on # both u and r to save cycles @@ -23,25 +27,29 @@ def gfpinv(a): r += p u >>= 1 r >>= 1 + continue # loop again # implementations could use count-zeros on # both v and s to save cycles - elif v & 1 == 0: + if v & 1 == 0: if s & 1 != 0: s += p v >>= 1 s >>= 1 + continue # loop again + # both LSB of u and v are 1 + x = u - v + if x > 0: + u = x + r -= s + if r < 0: + r += p else: - x = u - v - if x > 0: - u = x - r -= s - if r < 0: - r += p - else: - v = -x - s -= r - if s < 0: - s += p + v = -x + s -= r + if s < 0: + s += p + + # make sure result r within modulo range 0 <= r <= p if r > p: r -= p if r < 0: -- 2.30.2