Tikhon03
commented
9 years ago For an implementation on binary arrays, the Montgomery ladder seems almost trivial in APL, and may not take more than one line of code. Sliding window exponentiation should still be reasonable but requires precomputation of odd powers up to some prescribed exponent. Both algorthims should be easy to implement in a way that is independent of the group law, since the power operator already has this capability built in.
This requires implementation of modular exponentiation. Several algorithms for modular exponentiation exist, not all of which seem likely to have uniform time implementations. The most promising two are:
(1) Sliding window exponentiation (2) The Montgomery ladder
The Chinese Remainder Theorem, which should already have been implemented in Step 4 and 5 of Key Generation, should make the implementation more efficient, since reduction mod p and mod q will be faster than reduction mod pq.