类欧几里得算法

给定数字 ，在 时间内求出

令 。

f 的推导

当 或 时，

令 ： 否则，令 ：

g 的推导

当 或 时，

令 ： 否则，令 ：

h 的推导

当 或 时，

令 ：

否则，注意到 。

令 ： 三个函数一起算，时间复杂度为 。