A surprise rediscovery of a manuscript on the correctness proof of the Barrett algorithm

Life is a chance encounter, full of surprises. 😄

During my first RSA endeavor, I not only missed the Montgomery algorithm, but also missed the Barrett algorithm. What a shame! Later, I got a photocopy of the Montgomery algorithm and used it to implement elliptic curve cryptography, but I didn't have chance to implement the Barrett algorithm in full though I recall I did look into it in detail. Perhaps, the streamlined Montgomery algorithm became the mainstream implementation after the excellent paper by Burt Kaliski Jr. Most people just moved to efficient implementation of Montgomery multiplication.

Anyway, I'd totally forgotten what I did for the Barrett algorithm until a few days ago I incidentally found a photocopy of the paper sandwiched in the pages of my master degree thesis:

It was a photocopy from the Proceedings of Crypto'86 which was published in 1987. I think I got it in 1988 because it is with my old thesis. In page 318, it read as the proof of correctness of the algorithm, which made sure that at most two correcting subtractions were needed, was too complex to be provided in the paper (see that in the red rectangle):

Well, I found a proof by myself that time, written on a piece of dot matrix printer paper, very much yellowed with time having passed by:

With curiosity, I went through the manuscript written in 30 years ago and it is correct. It wasn't written down by chance, but I wasn't able to recall why started with y = [w/b^(n - 1)] * r. No clue at all.