Can reinforcement learning speed up modular multiplication?

fgrieu

10/6/23, 8:30 AM

In Discovering faster matrix multiplication algorithms with reinforcement learning (Nature, 2022; lightweight intro), the authors used reinforcement learning (an artificial intelligence technique) to devise a new, slightly faster matrix multiplication algorithm.

Could a similar technique work towards a better multiple-precision modular multiplication algorithm, as at the core of RSA and ECC using prime fields, for practical parameters (say, 256 to 4096-bit modulus)?

The question is focused on computing $a\times b\bmod n$ (or as a special case $a\times a\bmod n$ ) for arbitrary $a,b\in[0,n)$ with $n$ of $\ell$ bits (possibly restricted to odd $n$), using standard CPU instructions operating on $w$-bit words. I'm looking for a practical competitor to Karatsuba, Toom-Cook, or perhaps Schönhage-Strassen multiplication (but AFAIK the later is not competitive until much larger $\ell/w$ than used in RSA).

^{Optimizing modular exponentiation or ECC arithmetic might also be possible, but the question is not about that.}

126

0 + 5

implementation

modular-arithmetic

kelalaka

10/6/23, 8:49 AM

I think, the problem there one needs good insight to find better equations as Strassen did. As we see, there are similar cases with ECC operations that we can expect similar achievements,

Mark

10/6/23, 3:37 PM

Is there as nice of a theory of modular multiplication compared to matrix multiplication? In this setting, the problem reduces to finding tensor rank decompositions iirc. Has something similar to this been found for modular multiplication (or polynomial multiplication more generally)

Maarten Bodewes

10/6/23, 4:14 PM

Hmm, I don't know how we can square that with side channels and such, at least for private / secret key operations. Surprising results none-the-less and an interesting question.

Samuel Neves

10/7/23, 1:55 PM

Pretty much all fast multiplication algorithms can be understood as evaluation-multiplication-interpolation, when treating the integers to multiply as polynomials. For example, Karatsuba evaluates at $0, 1, \infty$, another variant of Karatsuba at $0, -1, \infty$. It can get pretty complicated to find the optimal set of points to evaluate, particularly with Toom-Cook, see for example [this](http://marco.bodrato.it/papers/Bodrato2007-OptimalToomCookMultiplicationForBinaryFieldAndIntegers.pdf).

fgrieu

10/7/23, 2:12 PM

@Samuel Neves: if reinforcement learning could uncover better parameters for a Toom-Cook variant, that would be what I'm dreaming about in this Q.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Can reinforcement learning speed up modular multiplication?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.