5 ms·
Instead of computing nA = A + A + … + A you can use the “exponentiation” by squaring trick: nA = (n/2)A + (n/2)A + (n%2)A. It takes logarithmically many steps.
by quantumcrypt 4y ago
Instead of computing nA = A + A + … + A you can use the “exponentiation” by squaring trick: nA = (n/2)A + (n/2)A + (n%2)A. It takes logarithmically many steps.