I've been researching how to implement RSA encryption using Extended Euclidean Algorithm to find the private key, d. Every article I read about it directs people to Wikipedia's website on the topic.
This is great, and super helpful, except for one thing: I can't understand what Wikipedia's pseudocode is saying.
I am having trouble with the line that states:
(t, newt) := (newt, t - quotient * newt) in the "Modular integers" section. Here's my interpretation:
int tempT = newt;
newt = t - quotient * newt;
t = tempT;
Is this correct? Thank you for your time!
This is the proper way to interpret this pseudocode. This is an assignment of one tuple to another tuple. The elements of each tuple are assigned respective to their positions, and the values are changed simultaneously.
This is best explained with an example.
If t=5, quotient=4, and newt=6 to start with, then (t, newt) := (newt, t - quotient * newt) does the following:
t is assigned to newt's initial value (6). Then newt is assigned as though t was not just re-assigned. newt becomes 5-4*6=-19.In the end, t=6 and newt=-19 (and quotient is unchanged).
In order to achieve this in java, one must store the original value of newt in a temporary variable (tempT in your code).