You are doing binary splitting of the exponent.
But it looks like you still have a redundant multiplication step that could be removed with a recursive call. In particular, I believe your routine would need 14 multiplications to compute x^255, whereas only 7 would be needed with a recursive call.
I don't see how it's possible to compute x^255 in 7 multiplies. The best I can come up with is 10: x^2 = x * x x^4 = x^2 * x^2 x^8 = x^4 * x^4 x^16 = x^8 * x^8 x^17 = x^16 * x x^34 = x^17 * x^17 x^51 = x^34 * x^17 x^102 = x^51 * x^51 x^204 = x^102 * x^102 x^255 = x^204 * x^51 In Christ, Steven Watanabe
Thanks. It looks like I was wrong again. I was mostly interested in the author's potential redundant multiplication---which we did successfully identify. I'll try to do better in the future. Best regards, Chris.