Now it's a bit difficult, perhaps, to be convinced that this is working.
But you can prove that the algorithm works by looking at, or
by showing that the algorithm satisfies the following invariant.
And the invariant is, that the answer, the correct answer that you're looking for
is always equal to T times X to the B amount N.
And that's certainly true at the beginning of the algorithm when we
initialized the variables because then X is equal to A and T is equal to 1.
And indeed A to the B amount N is exactly the answer we're looking for.
And then you can check throughout the loop.
That if B is even for example,
then what we end up doing is squaring the value of X and reducing B in half.
And so X to the b mod N, or t times x to the b mod N,
is of course equal to T to the X squared, to the B over 2 mod N.
Just algebra.
And similarly, if B is odd, we then shift a factor of X into T, and reduce B by 1.
And you can write down on paper and easily verify that the invariant is satisfied.
At the end of the algorithm, B is equal to 0, and
so the correct answer is given by exactly T.
And T is a value that we return.