<blockquote>
<p>Is this algorithm inspired by a public paper?
Any reference would be helpful, as I'm unable
to follow reason about the code itself.</p>
</blockquote>
<p>I am not sure about &quot;papers&quot;, but more or less formal articles on <em>modular multiplication</em> in fact abound: indeed, the implementation in question &quot;simply&quot; leverages known properties of modular arithmetic.</p>
<p>As to the specifics, the following is the link to a post about an older and somewhat simpler version of <code>secp256k1_fe_mul_inner</code> than the current one, but it might be enough to support further exploration/reverse-engineering:</p>
<ul>
<li>@cycheng, &quot;Mathematics behind secp256k1_fe_mul_inner&quot;, 2020<br />
<a href="https://free-cy.blogspot.com/2020/04/mathematics-behind-secp256k1femulinner.html" rel="nofollow noreferrer">https://free-cy.blogspot.com/2020/04/mathematics-behind-secp256k1femulinner.html</a></li>
</ul>
<p>That article also contains a link to the relevant modular arithmetic, in a nice and compact series of slides, which I will repost here:</p>
<ul>
<li>Peter Schwabe, &quot;Efficient implementation of finite-field arithmetic,&quot; 2013<br />
<a href="https://cryptojedi.org/peter/data/pairing-20131122.pdf" rel="nofollow noreferrer">https://cryptojedi.org/peter/data/pairing-20131122.pdf</a></li>
</ul>
<p>(There could be some added value in explaining the <em>present</em> implementation of <code>secp256k1_fe_mul_inner</code>, 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.)</p>

CC BY-SA 4.0
2023-12-30T14:55:23.940Z
2023-12-30T14:55:23.940Z
Julio Di Egidio
<p>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 <code>secp256k1_fe_mul_inner</code> in both <a href="https://github.com/bitcoin-core/secp256k1/blob/77af1da9f631fa622fb5b5895fd27be431432368/src/field_10x26_impl.h#L408" rel="nofollow noreferrer">10x26</a> 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.<br />
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.</p>

CC BY-SA 4.0
2023-12-17T12:36:26.113Z
I 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: https://free-cy.blogspot.com/2020/04/mathematics-behind-secp256k1femulinner.html , which I have found from here: https://bitcointalk.org/index.php?topic=5425925
Julio Di Egidio
CC BY-SA 4.0
2023-12-17T17:10:54.360Z
@JulioDiEgidio I would recommend posting an answer with links and a summary of details from the first link.
Hannah Vernon
<cryptography><secp256k1><math>
How does this field multiplication in libsecp256k1 work?
Davidson Souza
# How does this field multiplication in libsecp256k1 work?

(Asked by: username_0 on 2023-02-05)

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](https://github.com/bitcoin-core/secp256k1/blob/77af1da9f631fa622fb5b5895fd27be431432368/src/field_10x26_impl.h#L408) 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.

**Tags:** cryptography, secp256k1, math

> **Comments:**
> **username_1**: I 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: https://free-cy.blogspot.com/2020/04/mathematics-behind-secp256k1femulinner.html , which I have found from here: https://bitcointalk.org/index.php?topic=5425925  
> **username_2**: @username_1 I would recommend posting an answer with links and a summary of details from the first link.  

---

## 1 answers

### Answer by username_1 on 2023-12-30. Score: 2

> 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.)


---

