arcfide
commented
7 years ago Looks like progress, I'll take it.
Closed Tikhon03 closed 7 years ago
arcfide
commented
7 years ago Looks like progress, I'll take it.
Improvements of code you already have: 1) IE removed, replaced by GE 2) Xtimes (XT) factored and substantially improved: it now works for a vector times an array 3) MA and MS renamed A and S. They are becoming less relevant and may be removed completely at some point. 4) C improved to work on arrays. 5) I∆R was wrong. We now have Newton-Raphson (INV) and modular inverse (MINV). Both are needed.
Current standards: 1) All code should work for any base B that is a power of 2 less than or equal to 2^32. B=256 is the current default. Some code assumes that the input has shape is such a power of 2 (e.g. FT, IFT and LGCD) 2) Almost all code is in (mostly) uniform time. LGCD is an exception.
My strategy for verifying uniform time: In testing, I compare something random to something trivial. For the most part though, I keep a toolbox of uniform time tricks in mind at all times, and use only tools from that box.
New features: 1) Newton Raphson: INV 2) Extended Lehmer GCD: LGCD 3) Modular Inverse: MINV 4) Montgomery Ladder: ML. The comment about the assumed form of the identity means that the implementation will not work for elliptic curves. 5) Montgomery Reduction: REDC 6) Barret Reduction: BMOD 7) Modular Exponentiation with BMOD and ML: BEXP 8) Some AES Components. Mixcolumns (MC) is a particular favorite. 9) FT, IFT, and C all work on arbitrary arrays by working on the 0 axis, and XT which is based on them works for a vector times an array.
Note that BMOD and REDC both are implemented as operators, with the needed inverse computed outside, so that it only needs to be computed once during the exponentiation process. The overhead is still high, but that should be resolved by the first two pending improvements below.
Pending features/improvements: 1) Extended Binary GCD (will be named BGCD) 2) Partial carrying 3) Exponentiation with REDC.
Wish list: 1) Getting XT to work for an array times an array by working on the 0 axis of each array. 2) Other methods of exponentiation other than ML (I know how to give uniform time implementations of several of them).
The first item on this wish list may provide a time improvement to BMOD and REDC by the substantial simplification of one step modular reduction it would allow. The second item may or may not provide a time improvement to exponentiation.