1
$\begingroup$

I'm trying to implement the Number Theoretic Transform with an elliptic curve for learning about SNARKs, and the curve I'm working with is an Edwards curve implemented on the scalar field of BLS12-377 (described here: https://docs.rs/ark-ed-on-bls12-377/latest/ark_ed_on_bls12_377/). With an $$r = 2111115437357092606062206234695386632838870926408408195193685246394721360383,$$ $r-1$ is not divisible by $2^n$ for any $n > 1$, which means it should not have subgroups of $2^n$ order (referencing this [1] answer).

How would I go about implementing NTT for this curve? This answer [2] mentions working in a field extension to find the root. But this is for Kyber, and I'm not familiar with the math behind extensions and how I would obtain one out of the curve I'm working with. Additionally, if I switched to working with the "regular" BLS12-377 curve with $$r = 8444461749428370424248824938781546531375899335154063827935233455917409239041,$$ will following the algorithm of picking a $g=x^{(q−1)/n}$ with a random $x$ work as answer [1] describes?

Improve this question
$\endgroup$
1
  • $\begingroup$ Note that you would, at best, implement NTT for the field the curve is based on. It's not immediately obvious to me how such an operation on the field would be useful for the curve operations. $\endgroup$ Commented Oct 27 at 12:24

1 Answer 1

Reset to default
0
$\begingroup$

Is it possible to find a $2^n$th root of unity in the scalar field of the Edwards curve on BLS12-377?

Yes that is possible, but probably not what's really wanted: for any strictly positive integer $n$, the only two $2^n$th root of unity in this field are $1$ and $r-1$.

Argument: Such root of unity is a solution $x\in\mathbb F_r$ to the equation $x^{\left(2^n\right)}\equiv 1\pmod r$ with $r$ the prime 0x4aad957a68b2955982d1347970dec005293a3afc43c8afeb95aee9ac33fd9ff.

$x=1$ and $x=r-1$ are solutions, because they are solutions to $x^2\equiv 1\pmod r$, and then $1^{\left(2^{n-1}\right)}\equiv 1\pmod r$. And there are no others solutions, because $x=1$ and $x=r-1$ are the only solutions to $x^2\equiv 1\pmod r$, and there are no solutions to $x^2\equiv r-1\pmod r$, because the Legendre symbol $\left(\frac{r-1}r\right)=-1$, because $(r-1)/2$ is an odd integer.

Things are different working in the base field of BLS12-377, that is working in $\mathbb F_q$ with $q$ the prime 0x12ab655e9a2ca55660b44d1e5c37b00159aa76fed00000010a11800000000001: now we have $2^{\min(n,47)}$ roots. Part of the argument for this is $q\equiv1\pmod{2^{47}}$ and $q\not\equiv1\pmod{2^{48}}$. It's easy to compute such roots (if only by using Tonelli-Shanks repeatedly).

How would I go about implementing NTT for this curve?

I don't know.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.