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

4 points

a year 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 [email protected] -+91 9372677245

2 comments