Honestly, I don't understand the Schönhage–Strassen algorithm well enough to be able to tell if this makes sense, or if the resulting algorithm would even have competitive performance. It just sounds like a neat idea. I'm looking for somebody who could guide me in the right direction here, or at least tell me that this doesn't work out.

4/4

The idea that's nagging me is abusing the Schönhage–Strassen algorithm. Internally, it computes a * b (mod 2^n+1), choosing a large enough 2^n+1 that the product is computed to full precision. It uses a fast Fourier transform (or a number-theoretic transform?), and performs pointwise multiplication in the frequency domain. From what I understand, 2^n+1 is chosen so that you can simplify some operations, and because it is easy to find a primitive root for it.

Normally, the Schönhage–Strassen algorithm wouldn't be a good fit here -- it's better for larger numbers. However, if we can pick a different modulus -- such as p or q -- then we could stay in the frequency domain for the duration of the whole exponentiation process. The only trouble seems to be finding a primitive root for p and q, but you can do that once and cache the results.

3/4

An RSA signature is just hash(message)^d (mod n), where d is part of your secret key. This is a modular exponentiation, and there are a lot of algorithms for doing it fast.

A common Chinese Remainder Theorem trick lets you break this down into two modular exponentiations, using moduli p and q (which are parts of the secret key: n = pq). It's described pretty well in the Wikipedia page, so I won't repeat it here.

The goal is to perform those modular exponentiations as fast as possible. For RSA keys of standard sizes (2048 to 4096 bits), p and q should be roughly 1024 to 2048 bits in size each. Even with exponentiation by squaring, and ignoring the cost of reductions, that would require 2048 multiplications of 2048-bit numbers, in the worst case.

2/4