2
$\begingroup$

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.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.