25 Mar
2013
25 Mar
'13
8:12 a.m.
I'm looking for the _simplest_ binary _recursive_ GCD algorithm that has "pretty good" performance. I.e., a GCD algorithm that takes two length 2m integers and reduces this to a number of computations on length m integers. I did a quick Google search, and there seems to be a plethora of different such algorithms, but most are worried about the best possible performance at the expense of simplicity. I'm looking for something about as simple as Karatsuba squaring: (a+bx)^2 = a^2 + b^2x^2 + (a^2+b^2-(a-b)^2)*x