I'm looking at libsecp256k1's codebase, for learning reasons (doubt I can contribute with anything useful there). While looking at the field implementation, the implementation of secp256k1_fe_mul_inner in both 10x26 and 5x52 is a little strange to me. I know some multiplication algorithms, like Karatsuba and Toom's algorithms, but this one doesn't look like one of them, at least I couldn't relate.
Looking at the source and git history, I only see a reference to Peter Dettman, but I was unable to find any paper authored by him. Is this algorithm inspired by a public paper? Any reference would be helpful, as I'm unable to follow reason about the code itself. I understand what it is doing, but I don't know exactly how.
-
1I am not sure whether I should post this as an answer (can I just answer with a couple of links?), anyway have a look at this: free-cy.blogspot.com/2020/04/… , which I have found from here: bitcointalk.org/index.php?topic=5425925– Julio Di EgidioCommented Dec 17, 2023 at 12:36
-
2@JulioDiEgidio I would recommend posting an answer with links and a summary of details from the first link.– Hannah Vernon ♦Commented Dec 17, 2023 at 17:10
Add a comment
|
1 Answer
Is this algorithm inspired by a public paper? Any reference would be helpful, as I'm unable to follow reason about the code itself.
I am not sure about "papers", but more or less formal articles on modular multiplication in fact abound: indeed, the implementation in question "simply" leverages known properties of modular arithmetic.
As to the specifics, the following is the link to a post about an older and somewhat simpler version of secp256k1_fe_mul_inner than the current one, but it might be enough to support further exploration/reverse-engineering:
- @cycheng, "Mathematics behind secp256k1_fe_mul_inner", 2020
https://free-cy.blogspot.com/2020/04/mathematics-behind-secp256k1femulinner.html
That article also contains a link to the relevant modular arithmetic, in a nice and compact series of slides, which I will repost here:
- Peter Schwabe, "Efficient implementation of finite-field arithmetic," 2013
https://cryptojedi.org/peter/data/pairing-20131122.pdf
(There could be some added value in explaining the present implementation of secp256k1_fe_mul_inner, since it adds few more optimizations on top of the basic modular arithmetic. But I think that would require a level of detail and formality that is well beyond the scope of the present question.)
