"Desbordamiento" en Algoritmo Euclidiano Extendido

Lo siento si me equivoco con el lugar para hacer la pregunta (¿tal vez debería ir a stackoverflow.com/mathoverflow.net?).

Me pregunto si hay una prueba de que al evaluar el algoritmo euclidiano extendido, los coeficientes de Bézout (es decir, s y t en identidad como + bt = mcd ( a , b )) no excederán algunos valores razonables (dependiendo de a, b, supongo ) En particular, la implementación en algún lenguaje de programación de propósito general, estoy interesado en la corrección del desbordamiento del programa.

Para ser precisos, puedo mencionar que utilizo la descripción del algoritmo de Victor Shoup (4.2 en su libro " Una Introducción Computacional a la Teoría de Números y Algebra " disponible gratuitamente desde su página de inicio).

Esto se llama identidad / lema de Bézout (no debe confundirse con el teorema de Bézout en geometría algebraica), que establece:

$a,b \neq 0$$\gcd(a,b) = ax + by$$x,y$$|x| \leq |b|$$|y| \leq |a|$

Las pruebas se pueden fundar en libros de texto de álgebra estándar. También puede probarlo usted mismo por inducción en las iteraciones del proceso gcd.

$R$$f$$R = \mathbf{Z}$$f(x) = |x|$