1
$\begingroup$

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".

Here is the link.

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][0] = [1 ]
[Ub]   [alpha' beta'] [Ub]   [1 -3][1]   [-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]   [0]

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

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?

$\endgroup$

closed as unclear what you're asking by draks ..., Alex Provost, hardmath, Especially Lime, C. Falcon May 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.

  • 2
    $\begingroup$ Your link doesn't work, and what your wrote isn't remotely readable or coherent. $\endgroup$ – DanielV May 30 '17 at 15:26
  • $\begingroup$ This link like should work. Lehmer extended gcd is on 192 page. $\endgroup$ – Axrud May 30 '17 at 16:20
  • $\begingroup$ It is not clear what "algorithm" you are asking about. Indeed it seems more likely you are asking about an implementation having a bug (error), but I'm judging from the appearance of your post. If you want to ask about an error in an algorithm, you should give the algorithm here in the Question. $\endgroup$ – hardmath May 30 '17 at 20:41
  • $\begingroup$ The algorithm is pretty big to write it entirely, so I decided to give a link to it. $\endgroup$ – Axrud May 31 '17 at 7:06
  • $\begingroup$ 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. $\endgroup$ – hardmath May 31 '17 at 14:33