Given positive integer inputs $x$ and $y$ , with $0<x<y$ and $y$ an odd prime (or $\gcd(x,y)=1$ and $y$ odd), the following algorithm computes $x^{-1}\bmod y$ per the (half-)extended binary GCD. All quantities are non-negative.

What's an upper bound of the value internally reached by integers $a$ and $d$ , as a function of input $y$ ? I'm content with a number of bits: the objective is deciding a number of words for $a$ and $d$ when dealing with $y$ in the order of 256 bits.

  • If $x$ is odd then $u\gets x$ ; else $u\gets x+y$ ;
  • $v\gets y$ ; $a\gets0$ ; $d\gets p-1$ ;
  • While $v\ne1$
    [invariant here and at start of the next while loop: $u$ and $v$ are odd and distinct]
    • While $v<u$
      • $u\gets u-v$ ; $d\gets d+a$ ;
      • While $u$ is even (that's at least once)
        • If $d$ is odd then $d\gets d+y$ ;
        • $u\gets u/2$ ; $d\gets d/2$ ;
    • $v\gets v-u$ ; $a\gets a+d$ ;
    • While $v$ is even (that's at least once)
      • If $a$ is odd then $a\gets a+y$ ;
      • $v\gets v/2$ ; $a\gets a/2$ ;
  • $a\gets a\bmod y$ ; that's the desired inverse.

Note: I'm aware that by changing $a\gets a+y$ to:
  if $a<y$ then $a\gets a+y$ ; else $a\gets a-y$ ;
and same for $d\gets d+y$ , we keep $a$ and $d$ below $4y$ ; I'm asking what if we do not.

There's a similar upper-bound issue in the classical extended binary GCD algorithm using signed variables, as in the Handbook of Applied Cryptography's algorithm 14.61. This question's $d$ (resp. $a$) is similar in role to $-D$ (resp. $C$ and $a$) in that algorithm.

Update: I'm leaning towards $\max(a,d)<4y\log_2(y)$ or something on that tune, but fail to make a proof.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.