# Fast GCD algorithm [closed]

I'm trying to implement the extended Lehmer algorithm (search for GCD and Bezout coefficients) from the book "Handbook of Elliptic and Hyperelliptic Curve Cryptography".

It seems to me that there is an error in this algorithm, here is an example:

For example, take numbers:
x = 0x3 3333 3333 3333 3333
N = 0xA AAAA AAAA AAAA AAAA
Platform is x64, so l = 64

A = 0xA AAAA AAAA AAAA AAAA, B = 0x3 3333 3333 3333 3333, Ua = 0, Ub = 1

A^ = 0xAAAA AAAA AAAA AAAA, B^ = 0x3333 3333 3333 3333, alpha = 1, beta = 0, alpha' = 0, beta' = 1
B^ != 0, so q <- [A^/B^] = 3, T <- A^ mod B^ = 0x1111 1111 1111 1111
T >= 2^(l/2), so q' <- [B^/T] = 3, T' <- B^ mod T = 0
T' < 2^(l/2), so break;
beta == 0, so alpha = 0, beta = 1, alpha' = 1, beta' = -[A/B] = -3
return {alpha, beta, alpha', beta'} = {0,1,1,-3}

[A] = [alpha  beta ]*[A] = [0  1][0xA AAAA AAAA AAAA AAAA] = [0x3 3333 3333 3333 3333]
[B]   [alpha' beta'] [B]   [1 -3][0x3 3333 3333 3333 3333]   [0x1 1111 1111 1111 1111]

[Ua] = [alpha  beta ]*[Ua] = [0  1] = [1 ]
[Ub]   [alpha' beta'] [Ub]   [1 -3]   [-3]

A = 0x3 3333 3333 3333 3333, B = 0x1 1111 1111 1111 1111, Ua = 1, Ub = -3
A^ = 0xCCCC CCCC CCCC CCCC, B^ = 0x4444 4444 4444 4444, alpha = 1, beta = 0, alpha' = 0, beta' = 1
B^ != 0, so q <- [A^/B^] = 3, T <- A^ mod B^ = 0
T' < 2^(l/2), so
beta == 0, so alpha = 0, beta = 1, alpha' = 1, beta' = -[A/B] = -3
return {alpha, beta, alpha', beta'} = {0,1,1,-3}

[A] = [alpha  beta ]*[A] = [0  1][0x3 3333 3333 3333 3333] = [0x1 1111 1111 1111 1111]
[B]   [alpha' beta'] [B]   [1 -3][0x1 1111 1111 1111 1111]   

[Ua] = [alpha  beta ]*[Ua] = [0  1][ 1] = [-3]
[Ub]   [alpha' beta'] [Ub]   [1 -3][-3]   

A = 0x1 1111 1111 1111 1111, B = 0, Ua = -3, Ub = 10
Next step we must compute (u, v, d) by Algorithm 10.42
with arguments A and B, but B is zero and algorithm 10.42
crushes at line 3
q <- [A/B]
In description to algorithm 10.42 says:
INPUT: Two POSITIVE integers,
but it called with B = 0 in algorithm 10.45.


Problem is that at the end of the algorithm (the last 3 lines of my calculations) there is a division by zero occurs.

My question is the following:

1) Is the error really in the book, or I'm mistaken in my calculations?
2) If there is an error in the book, what needs to be changed in the algorithm to make it work?

## closed as unclear what you're asking by draks ..., Alex Provost, hardmath, Especially Lime, C. FalconMay 31 '17 at 0:04

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• I've spent a bit of time going through your post and the links. As your edit reflects, the problem is about the dependence of Alg. 10.45 on Alg. 10.42, where the latter is a general extended GCD algorithm, and the former is a treatment of extended GCD for multiprecision integers (using most significant "digits" of $A$ and $B$). In its current form the Question doesn't convey the issue very clearly to Readers. – hardmath May 31 '17 at 14:33