Talk:Modular exponentiation
Draft change
About 21 hours after I posted this draft, I changed the task from "last 20" to "last 40 decimal digits". I adjusted some solutions to print 40 digits, but I did not change the Go or Java programs. --Kernigh 19:49, 19 December 2011 (UTC)
What if m < 0?
My draft currently specifies m ≠ 0. The answer when m < 0 might be ill-defined or inconsistent. Should I change from m ≠ 0 to m > 0 here? --Kernigh 23:18, 20 December 2011 (UTC)
- You could specify them all to be positive integers without causing problems; that's the only case that anyone actually wants in practice, and the others get into arguments (due to differing interpretations of how to extend the modulus operation to non-positive-valued domains). –Donal Fellows 02:00, 21 December 2011 (UTC)
Tell algorithm?
What's with needs improvement on the Java solution? A number of other solutions here just call a library function. In general, library algorithms might not always be known, or may change without notice so I'm not a big fan of telling library algorithms. As with so many other tasks, this one could go in different directions: Allowing simple library solutions, disallowing simple library solutions, or requiring a specific algorithm. The binary algorithm is an important one. It wouldn't be so bad to require an implementation of that specific algorithm. —Sonia 18:19, 24 December 2011 (UTC)
- I put the needs improvement on my own solution. I thought I would be able to figure out which alorithm it uses but I couldn't. I also thought other languages would have scratch implementations of specific algorithms so it would be nice to know which one it uses. You can take it off if you don't like it. --Mwn3d 19:37, 24 December 2011 (UTC)
- I suspect that all practical implementations use the “Right-to-left binary method” (the Tcl version certainly does) as that is clearly much more efficient than the others listed on the WP page for large exponents (which is what you need for the RSA encryption algorithm, by far the most important consumer of this function). Or they use a “left-to-right” method which is actually equivalent but consumes the bits in reverse order. –Donal Fellows 20:35, 24 December 2011 (UTC)
I find Kernigh's notes on the OpenJDK algorithm interesting! I'd be in favor of adding an extra credit task to provide a description like this. —Sonia 18:40, 25 December 2011 (UTC)
task requirements
Did the task's author really mean that the algorithm must work with any integers where and ?
I re-worked the REXX example to try to accomodate the task's requirements, but nobody else even bothered to address their language's limitation on this issue. -- Gerard Schildberger 23:55, 14 May 2012 (UTC)
