Fix error in WithSmallOrderMulGroup impl for Bn254::Fr

[CPerezz]

The current definition of this trait is: https://github.com/privacy-scaling-explorations/halo2curves/blob/main/src/bn256/fr.rs#L336-L338

This is not correct.

N is meant to be the order of a small multiplicative sub-group. Not it's generator. The error can be seen if we execute:

modulus = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001
sage: factor(modulus-1)
2^28 * 3^2 * 13 * 29 * 983 * 11003 * 237073 * 405928799 * 1670836401704629 * 13818364434197438864469338081
 GF(modulus).primitive_element() ^ ((modulus - 1) // 2)
21888242871839275222246405745257275088548364400416034343698204186575808495616
sage: print(21888242871839275222246405745257275088548364400416034343698204186575808495616.hex())
30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000000

According to the formula in the ff crate:

pub trait WithSmallOrderMulGroup<const N: u8>: PrimeField {
    /// A field element of small multiplicative order $N$.
    ///
    /// The presense of this element allows you to perform (certain types of)
    /// endomorphisms on some elliptic curves.
    ///
    /// It can be calculated using [SageMath] as
    /// `GF(modulus).primitive_element() ^ ((modulus - 1) // N)`.
    /// Choosing the element of order $N$ that is smallest, when considered
    /// as an integer, may help to ensure consistency.
    ///
    /// [SageMath]: https://www.sagemath.org/
    const ZETA: Self;
}

We can see that N should be the order of the multiplicative sub-group which has 3 as a generator and order 2. Luckily, the generic doesn't affect the implementation. And indeed, if you compute ZETA you will get the correct result (that matches the one used in the repo.

So the only wrong thing is the generic which should be N=2.

Edit: I'm definitely missing something as the pasta_curves forces the multiplicative subgroup order to be 3 always.. What is true, is that with N =3 we don't get the ZETA used actually.

[davidnevadoc]

I see the source of the confusion. This trait is meant to be used for the implementation of efficient endomorphisms:

 /// The presence of this element allows you to perform (certain types of)
 /// endomorphisms on some elliptic curves.

In the case of bn and many other curves we are interested in the cubic endomorphism, hence we look for an element of order 3: zeta. The subgroup generated by this element is the small group this trait refers to, which has order N=3.

With regards to the actual ZETA, notice that this can be any generator of the subgroup, so it can be either zeta or zeta^2. AFAIK different versions of Sage may output one or the other so that may be the source of the discrepancy.

[davidnevadoc]

Can we mark this as solved? @CPerezz