I'm teaching an introductory course in cryptography and explained the square-and-multiply algorithm to the class.

http://en.wikipedia.org/wiki/Square-and-multiply_algorithm

Someone asked who discovered the algorithm, which I didn't know, so after a short web search that gave no answers, I thought I'd ask on MO. In particular, the above wikipedia article is not helpful, and I didn't see any MO questions that address the issue. This seems like something that Gauss and Euler, or even Fermat, might have known, and ditto for Indian and Chinese mathematicians centuries earlier, but I'm just speculating. Specific references would be appreciated. (Sorry if this isn't really a research level question, although maybe it qualifies as historical research.)