19 x 31 = 589 >= 587
I implemented safegcd256 for Gnuk. It uses signed 31-bit integers, and it does 19 iterations for p = 2**255 - 19.
Modular inversion
In the computation of X25519, we need to compute the modular inversion at the last step to get the value of x in …