Timeline for Origin of square-and-multiply algorithm
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 22, 2012 at 10:01 | history | edited | Carlo Beenakker | CC BY-SA 3.0 |
one more reference
|
| Sep 22, 2012 at 0:13 | comment | added | Kevin O'Bryant | But is Chandah-sutra open access? | |
| Sep 21, 2012 at 1:49 | comment | added | Joe Silverman | @Carlo: Thanks, that's just what I was looking for. | |
| Sep 21, 2012 at 1:48 | vote | accept | Joe Silverman | ||
| Sep 20, 2012 at 20:06 | comment | added | Gerhard Paseman | To be clear, square for even exponents, square and multiply one more for an odd exponent. Gerhard "Or Some Other Variation Thereupon" Paseman, 2012.09.20 | |
| Sep 20, 2012 at 19:57 | comment | added | Carlo Beenakker | this is the binary method for exponentiation, which is what is called the "square and multiply" method. | |
| Sep 20, 2012 at 19:55 | history | edited | Carlo Beenakker | CC BY-SA 3.0 |
typo
|
| Sep 20, 2012 at 19:42 | comment | added | Noam D. Elkies | Is this for square-and-multiply or double-and-add (en.wikipedia.org/wiki/Ancient_Egyptian_multiplication)? I thought that the Legendre formula $a^{(p-1)/2} \bmod p$ was originally thought impractical for lack of square-and-multiply. Note that the "mod $p$" part is essential, otherwise $a^n$ soon becomes so large that writing out $a^n$ in full becomes infeasible in any case. | |
| Sep 20, 2012 at 19:33 | history | answered | Carlo Beenakker | CC BY-SA 3.0 |