Cf. https://www.ingonyama.com/blogs/goldilocks-ntt-trick some of the primitive roots of unity can be implemented as powers of 2. This holds for the roots with order 4 to 64 (both inclusive).
With this trick, the new orders of unity become:
static PRIMITIVE_ROOTS: phf::Map<u64, u64> = phf_map! {
2u64 => Q - 1,
4u64 => 1u64 << 48,
8u64 => 1u64 << 24,
16u64 => 1u64 << 12,
32u64 => 1u64 << 6,
64u64 => 1u64 << 3,
128u64 => 2198989700608,
256u64 => 4404853092538523347,
512u64 => 6434636298004421797,
1024u64 => 4255134452441852017,
2048u64 => 9113133275150391358,
4096u64 => 4355325209153869931,
8192u64 => 4308460244895131701,
16384u64 => 7126024226993609386,
32768u64 => 1873558160482552414,
65536u64 => 8167150655112846419,
131072u64 => 5718075921287398682,
262144u64 => 3411401055030829696,
524288u64 => 8982441859486529725,
1048576u64 => 1971462654193939361,
2097152u64 => 6553637399136210105,
4194304u64 => 8124823329697072476,
8388608u64 => 5936499541590631774,
16777216u64 => 2709866199236980323,
33554432u64 => 8877499657461974390,
67108864u64 => 3757607247483852735,
134217728u64 => 4969973714567017225,
268435456u64 => 2147253751702802259,
536870912u64 => 2530564950562219707,
1073741824u64 => 1905180297017055339,
2147483648u64 => 3524815499551269279,
4294967296u64 => 7277203076849721926,
};I think the NTT/INTT is only determined up to a constant so there might be some intermediate NTT results that are no longer valid.
Cf. https://www.ingonyama.com/blogs/goldilocks-ntt-trick some of the primitive roots of unity can be implemented as powers of 2. This holds for the roots with order 4 to 64 (both inclusive).
With this trick, the new orders of unity become:
I think the NTT/INTT is only determined up to a constant so there might be some intermediate NTT results that are no longer valid.