3 ms·

I could not find a description of your algorithm, which makes it hard to give you feedback. However, here are a few questions that come to my mind from a crypt

I could not find a description of your algorithm, which makes it hard to give you feedback. However, here are a few questions that come to my mind from a cryptography/ZK perspective. 1) elliptic-curve cryptography cares about 256-bit multiplication (and perhaps 384 or 521 bits for the truly paranoid). Is your algorithm better than alternatives in that regime? 2) cryptography/ZK cares about multiplication mod p, and not about multiplication per se. Of course you can perform the multiplication and then reduce mod p, but other techniques exist (e.g. Montgomery multiplication) that interleave the multiplication and the reduction for better performance. It is hard to combine Montgomery and Karatsuba. Can your technique be combined with Montgomery? 3) ZK also cares about binary fields GF(2^k). Does your technique work in those fields?

KrishilSheth 1y ago
1) Is your algorithm better than alternatives for 256-bit multiplication (or 384/521 bits)? Yes. RPF consistently outperforms Karatsuba and other classic methods (including Toom-Cook and even some FFTs) in the 128–800 digit (approx. 400–2600 bit) range. Specifically, at 256, 384, and 521 bits, which are critical for elliptic curve cryptography, RPF is faster in squaring — both in raw integer mode and when enhanced with GMP. We observed: Lower execution times than Karatsuba starting from 150–180 bits onward. Better scaling, meaning performance advantage widens as bit size increases. 2) Can your technique be combined with Montgomery multiplication? Yes, and this is one of RPF’s strong points. Karatsuba and Montgomery are hard to combine efficiently due to their recursive and carry-heavy nature. RPF, however, has a more linear and structured squaring layout, making it much easier to wrap inside Montgomery’s reduction loop. In initial tests, we were able to: Integrate RPF inside a Montgomery-style multiplication framework with minimal change. Maintain a performance lead compared to Karatsuba-integrated approaches. We’re exploring even more optimized coupling with Montgomery reductions for modular cryptography applications. 3) Does your technique work in binary fields GF(2^k)? RPF can be adapted to binary fields. Since GF(2^k) squaring operations have specific bit-level behaviors (like lack of carry propagation), the base version of RPF designed for integers won’t directly transfer. However, we are working on a variant of RPF optimized for GF(2^k) that leverages: XOR-style operations instead of additions, and efficient bit-splitting to emulate RPF’s structure in binary logic.

KrishilSheth 1y ago

1) Is your algorithm better than alternatives for 256-bit multiplication (or 384/521 bits)? Yes. RPF consistently outperforms Karatsuba and other classic methods (including Toom-Cook and even some FFTs) in the 128–800 digit (approx. 400–2600 bit) range. Specifically, at 256, 384, and 521 bits, which are critical for elliptic curve cryptography, RPF is faster in squaring — both in raw integer mode and when enhanced with GMP. We observed: Lower execution times than Karatsuba starting from 150–180 bits onward. Better scaling, meaning performance advantage widens as bit size increases. 2) Can your technique be combined with Montgomery multiplication? Yes, and this is one of RPF’s strong points. Karatsuba and Montgomery are hard to combine efficiently due to their recursive and carry-heavy nature. RPF, however, has a more linear and structured squaring layout, making it much easier to wrap inside Montgomery’s reduction loop. In initial tests, we were able to: Integrate RPF inside a Montgomery-style multiplication framework with minimal change. Maintain a performance lead compared to Karatsuba-integrated approaches. We’re exploring even more optimized coupling with Montgomery reductions for modular cryptography applications. 3) Does your technique work in binary fields GF(2^k)? RPF can be adapted to binary fields. Since GF(2^k) squaring operations have specific bit-level behaviors (like lack of carry propagation), the base version of RPF designed for integers won’t directly transfer. However, we are working on a variant of RPF optimized for GF(2^k) that leverages: XOR-style operations instead of additions, and efficient bit-splitting to emulate RPF’s structure in binary logic.