## Week 50, notes.

Still working on understand the fft algorithm against two test fields. One of prime order $p = 18446744069414584321$ and agaisnt BN256.

In order to understand how fft is calculated in the field, we have to understand how the twiddles are calculated.

Working on understanding the calcualtion of the primitive roots of unity.

    /// Returns a primitive root of unity of order $2^{order}$.
    fn get_primitive_root_of_unity<F: IsFFTField>(
        order: u64,
    ) -> Result<FieldElement<F>, FieldError> {

        println!("order  = {}", order);

        let two_adic_primitive_root_of_unity =
            FieldElement::new(F::TWO_ADIC_PRIMITVE_ROOT_OF_UNITY);

        println!("TWO_ADIC_PRIMITVE_ROOT_OF_UNITY --> {}", format!("{:?}", F::TWO_ADIC_PRIMITVE_ROOT_OF_UNITY));
        println!("FE two_adic_primitive_root_of_unity --> {}", format!("{:?}", two_adic_primitive_root_of_unity));


        if order == 0 {
            return Ok(FieldElement::one());
        }
        if order > F::TWO_ADICITY {
            return Err(FieldError::RootOfUnityError(order));
        }

        let h: FieldElement<F> = FieldElement::new(F::TWO_ADIC_PRIMITVE_ROOT_OF_UNITY);
        println!("FE new 2-adic primitive root of unity : {:?}", h);
        println!("\t\t --> {}", format!("{:?}", h));

        let log_power = F::TWO_ADICITY - order;

        println!("F TWO_ADICITY : {:?}", F::TWO_ADICITY);    // F::TWO_ADICITY
        println!("log_power : {:?}", log_power);    // log_power = 2-adic - order


        // Initialize the result with the Two-Adic primitive root of unity
        let mut root = two_adic_primitive_root_of_unity.clone();
        for _ in 0..log_power {
            root = root.square();
            println!("root = {:?}", root)
        }
        
        println!("---------------------------");
        let mut root_test = two_adic_primitive_root_of_unity;
        let mut i = 0;
        for _ in 0..log_power {
            println!("root   = {:?}", root_test);
            root_test = root_test.square();
            println!("root^{} = {:?}", i, root_test);
            // println!("[{}]", i);
            i += 1;
        }
        println!("\n root_test = {:?}", root_test);

        Ok(root)
    }

in the test prime field. getting the values for the generator, 2-adicity, 2-adic-root-of-unity, and actually understanding how these are calcualted, using sage:

modulus = 18446744069414584321

assert(modulus.is_prime())

Fp = GF(modulus)

generator = Fp(0);
for i in range(0, 20):
    i = Fp(i);
    neg_i = Fp(-i)
    if not(i.is_primitive_root() or neg_i.is_primitive_root()):
        continue
    elif i.is_primitive_root():
        assert(i.is_primitive_root());
        print("Generator: %d" % i)
        generator = i
        break
    else:
        assert(neg_i.is_primitive_root());
        print("Generator: %d" % neg_i)
        generator = neg_i
        break


two_adicity = valuation(modulus - 1, 2);
trace = (modulus - 1) / 2**two_adicity;
two_adic_root_of_unity = generator^trace
print("2-adicity: %d " % two_adicity)
print("2-adic Root of Unity: %d " % two_adic_root_of_unity)

Generator: 7
2-adicity: 32 
2-adic Root of Unity: 175363513344016577

Similarly for BN254. These numders are not in any of the popular `Fr` library files from `halo2_proofs::pairing::bn256::Fr` or in halo2curves/src/bn256/fr.rs. Generating the values using sage to actually figure out if any of the numbers im getting out of the fft algorithms make sense (using scalar field modulus for BN256).

modulus = 21888242871839275222246405745257275088548364400416034343698204186575808495617

assert(modulus.is_prime())

Fp = GF(modulus)

generator = Fp(0);
for i in range(0, 20):
    i = Fp(i);
    neg_i = Fp(-i)
    if not(i.is_primitive_root() or neg_i.is_primitive_root()):
        continue
    elif i.is_primitive_root():
        assert(i.is_primitive_root());
        print("Generator: %d" % i)
        generator = i
        break
    else:
        assert(neg_i.is_primitive_root());
        print("Generator: %d" % neg_i)
        generator = neg_i
        break


two_adicity = valuation(modulus - 1, 2);
trace = (modulus - 1) / 2**two_adicity;
two_adic_root_of_unity = generator^trace
print("2-adicity: %d " % two_adicity)
print("2-adic Root of Unity: %d " % two_adic_root_of_unity)


Generator: 5
2-adicity: 28 
2-adic Root of Unity: 19103219067921713944291392827692070036145651957329286315305642004821462161904 
0x2a3c09f0a58a7e8500e0a7eb8ef62abc402d111e41112ed49bd61b6e725b19f0

Notice that the popular BN256 libraries use a generator

/// `GENERATOR = 7 mod r` is a generator of the `r - 1` order multiplicative
/// subgroup, or in other words a primitive root of the field.
const GENERATOR: Fr = Fr::from_raw([0x07, 0x00, 0x00, 0x00]);

const S: u32 = 28;

/// GENERATOR^t where t * 2^s + 1 = r
/// with t odd. In other words, this
/// is a 2^s root of unity.
/// `0x3ddb9f5166d18b798865ea93dd31f743215cf6dd39329c8d34f1ed960c37c9c`
const ROOT_OF_UNITY: Fr = Fr::from_raw([
    0xd34f1ed960c37c9c,
    0x3215cf6dd39329c8,
    0x98865ea93dd31f74,
    0x03ddb9f5166d18b7,
]);

the test if these values are correct should be:

    F::TWO_ADIC_ROOT_OF_UNITY.pow([1 << F::::TWO_ADICITY]),
    F::one()