this is a first step towards addressing https://github.com/0xPolygonZero/plonky2/issues/850. note that 0x64fdd1a46201e246^(2^30) == 0x1000000000000 holds modulo p, as desired. we don't actually change the FFT in this PR; but this paves the way for that as a future change.
both Hermez and Miden already currently use this new generator.
upon changing the main 2^32nd root of unity of Goldilocks, a few auxiliary values also need to change. these include:
the multiplicative generator here. this is a generator of Goldilocks' entire multiplicative group of units, which moreover "lifts" the main 2-adic generator above in the sense that MULTIPLICATIVE_GROUP_GENERATOR^((p - 1) / 2^32) == POWER_OF_TWO_GENERATOR holds. this isn't too hard to construct; essentially, it amounts to finding a multiplicative generator of $\mathbb{F}_p^*$'s order-(p - 1) / 2^32 subgroup, which is not hard.
in the extension fields, we need to do something analogous, but for 2-adic generators. for example, in the quadratic extension of Goldilocks given by X^2 - 7, we now get 2^33-order 2-adicity; the value EXT_POWER_OF_TWO_GENERATOR needs to be a primitive 2^33nd root of unity which moreover lifts POWER_OF_TWO_GENERATOR, in the sense that EXT_POWER_OF_TWO_GENERATOR^2 = POWER_OF_TWO_GENERATOR. this is a bit tricky to do; we were able to construct this efficiently using essentially a Pohlig–Hellman-type idea.
Finally, this 2-adic generator itself also needs to be lifted to a full multiplicative generator EXT_MULTIPLICATIVE_GROUP_GENERATOR of $\mathbb{F}_{p^2}^*$, i.e., so that EXT_MULTIPLICATIVE_GROUP_GENERATOR^((p^2 - 1) / 2^33) == EXT_POWER_OF_TWO_GENERATOR holds.
we also need to do something analogous for the quartic and quintic extensions.
0x64fdd1a46201e246^(2^30) == 0x1000000000000
holds modulo p, as desired. we don't actually change the FFT in this PR; but this paves the way for that as a future change.upon changing the main 2^32nd root of unity of Goldilocks, a few auxiliary values also need to change. these include:
MULTIPLICATIVE_GROUP_GENERATOR^((p - 1) / 2^32) == POWER_OF_TWO_GENERATOR
holds. this isn't too hard to construct; essentially, it amounts to finding a multiplicative generator of $\mathbb{F}_p^*$'s order-(p - 1) / 2^32 subgroup, which is not hard.X^2 - 7
, we now get 2^33-order 2-adicity; the valueEXT_POWER_OF_TWO_GENERATOR
needs to be a primitive 2^33nd root of unity which moreover liftsPOWER_OF_TWO_GENERATOR
, in the sense thatEXT_POWER_OF_TWO_GENERATOR^2 = POWER_OF_TWO_GENERATOR
. this is a bit tricky to do; we were able to construct this efficiently using essentially a Pohlig–Hellman-type idea.EXT_MULTIPLICATIVE_GROUP_GENERATOR
of $\mathbb{F}_{p^2}^*$, i.e., so thatEXT_MULTIPLICATIVE_GROUP_GENERATOR^((p^2 - 1) / 2^33) == EXT_POWER_OF_TWO_GENERATOR
holds.we also need to do something analogous for the quartic and quintic extensions.