prog2222 wrote: |
---|
can you explain me what means xb, a0, x0? |
I coded directly from the algorithm in
https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
(Look at their segment of pseudocode.)
x and y correspond to what are called s and t respectively in that write-up.
The usual Euclidean algorithm uses updates of a and b rather than the sequence r
_{k}, so that is the notation that I used.
Since I don't bother to store whole sequences I need to store and update two iteration levels for each step, and you need to advance these forward. So a0, x0 and y0 store the values that you are eventually going to have to assign to a, x and y (or r
_{k}, s
_{k} and t
_{k} in the Wikipedia notation), whilst b, xb and yb are updated to what is r
_{k+1}, s
_{k+1} and t
_{k+1} in the Wikipedia notation.
You need to sit down and follow the Wikipedia article or similar.
Incidentally, the code in your original post presumably gives the same result (difficulty to tell: it's indecipherable), and for all I know it might be faster, but I'm pretty sure it's not following the same algorithm. There is no evidence of extracting a quotient, for example.