GCD is broken/poorly documented

[jceipek]

https://github.com/jtobey/javascript-bignum/blob/master/lib/leemonBigInt.js#L903

I've been trying to implement Pollard's Rho algorithm as part of a demonstration of ElGamal. While testing it, I determined that the GCD function sometimes doesn't return the expected results. For example:

GCD([23018,1,0],[17454,0,0])
[2, 0, 0]
GCD([17454,0,0],[23018,1,0])
[14, 0, 0]

According to http://cacr.uwaterloo.ca/hac/about/chap14.pdf, Lehmer's gcd algorithm imposes x >= y as a condition. Since the condition is not documented in the code, I'm not sure if there are other problems with it.

If not, the condition should probably be documented for GCD_. Perhaps GCD should be changed to pass the larger of x and y as the first parameter of the GCD_ call.

[jtobey]

I suggest you try the latest upstream version: http://www.leemon.com/crypto/BigInt.js

I reported something like this in 2012. Perhaps the author fixed it.

GCD([ 0, 15124, 5601, 2842, 0, 0, 0, 0, 0 ], [ 0, 0, 14736, 15468, 31747, 21936, 17007, 246, 0 ])

It seems to loop consuming CPU on my system. I tested it on Node.js and Rhino. I expect the result [ 0, 15124, 5601, 2842, 0, 0, 0, 0, 0 ].

[jceipek]

Thanks, @jtobey. I've been using that version and it still has the problem I described. After implementing a full prime factoring method and comparing it with results from Wolfram Alpha, I'm relatively convinced that GCD does work as long as x >= y, though.

[jtobey]

Thanks for the tip, I guess we pass the larger number first then!