Discrete Mathematics - Contemporary Cryptography - page 70

In this case, a = 100 and b =35. After the initialization phase of the algorithm, we
come to the first incarnation of the while-loop with i =0. We compute

r 0 = ax 0 + by 0 = 100 · 0+35 · 1=35 .

Because this value is not equal to 0, we enter the loop. The variable q is set to
r − 1 div r 0 . In our example, this integer division yields 100 div 35 = 2. Using q =2,
we compute the following pair of values:

x 1 = x − 1 − qx 0 =1 − 2 · 0=1

y 1 = y − 1 − qy 0 =0 − 2 · 1= − 2

After having incremented i with 1, we have i =1and come back to the second
incarnation of the while-loop. We compute

r 1 = ax 1 + by 1 = 100 · 1+35 · ( − 2) = 100 − 70 = 30 .

Because this value is again not equal to 0, we enter the loop again. This time,
the variable q is set to r 0 div r 1 =35div30=1.Using q =1, we then compute the
following pair of values:

x 2 = x 0 − qx 1 =0 − 1= − 1

y 2 = y 0 − qy 1 =1 − (1 · ( − 2)) = 1 + 2 = 3

After having incremented i with 1, we have i =2and come back to the third
incarnation of the while-loop. We compute

r 2 = ax 2 + by 2 = 100 · ( − 1) + 35 · 3= − 100 + 105 = 5 .

Because this value is not equal to 0, we enter the loop. This time, the variable
q is set to r 1 div r 2 =30div 5 = 6. Using q =6, we compute the following pair of
values: