My Squaring Algo Beats Karatsuba and FFT for Real-World Cryptography

4 points by KrishilSheth 15 hours ago

Hi HN, I’m Krishil Rohit Sheth, and over the last 4 years I’ve developed a new algorithm (RPF) for squaring large numbers — and it outperforms Karatsuba, and even FFT-based methods for numbers under 800 digits.

Raw performance: RPF beats Karatsuba in execution time and scales better with input size. With GMP enhancements: Even after both are optimized with GMP, RPF still maintains a performance edge. Better than FFT for mid-size inputs: Up to 800 digits, RPF is also faster than FFT-based multiplication, which usually kicks in beyond this range.

   I’ve attached benchmark charts and comparisons here:
   -https://drive.google.com/file/d/1aZ-JR0Oq5KnY4xKd2tAPEvr1wFPowhSt/view?usp=drive_link
This has applications in:

Cryptography (modular exponentiation)

Blockchain & ZK systems

Financial simulations

Any compute-heavy big-number operations

I’ve filed a provisional patent and I’m looking to either license the algorithm, collaborate, or sell the IP outright.

Would love feedback from devs, researchers, and cryptographers here! Also happy to talk if you work on libraries like GMP, OpenSSL, Java BigInteger, Libgcrypt, etc.

Thanks! —Krishil Sheth -krishilsheth@gmail.com -+91 9372677245

MatteoFrigo 9 hours ago

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?