Talk:Addition-chain exponentiation: Difference between revisions
→Montgomery reduction: new section
(lots of thoughts after implementing a solution) |
(→Montgomery reduction: new section) |
||
Line 130:
==Optimal solution, A003313, and κῦδος==
Any technique that guarantees optimal solutions produces A003313 so if the task allows only optimal solutions, then 1) the task requires an expensive computation, and 2) κῦδος are cheap for any valid solution. I would like to see the task allow solutions that are not guaranteed to be optimal but which generally improve on binary solutions. This is arguing for the practical result of accelerating a computation as opposed to the mathematical result of finding a limit. The rich literature out there seems mostly focused on the practical application of finding near-optimal solutions (for the purpose of accelerating RSA encryption.) κῦδος could still go to the mathematical result of A003313, but it could be made more challenging by requiring later terms of the sequence. Terms 8190-8195, for example, which are verifiable from a link from the OEIS page. Actually I'd like to see κῦδος awarded for reproducing those terms using a near-optimal technique. —[[User:Sonia|Sonia]] 23:08, 13 February 2012 (UTC)
== Montgomery reduction ==
I just tried a fun experiment of combining this task with the [[Montgomery reduction]] task and it worked just fine. It's not that much of a stretch since Montgomery reduction is just another way to do multiplication, but still it was fun to see addition chain exponentiation work with this alternative operation and also see it work on some bigger numbers. The 100 bit exponents of my example there take about 150 multiplies using binary exponentiation but about 130 multiplies with the addition chains. —[[User:Sonia|Sonia]] 01:59, 2 March 2012 (UTC)
| |||