I'm attempting to implement an NTT (Number Theoretic Transform) in Objective C, however the abstract mathematical documents posted online are missing crucial details. I've found the following existing Question on Stack Overflow which purports to include a working (albeit non-optimal) implementation of NTT: Modular arithmetics and NTT (finite field DFT) optimizations
My question is regarding the computation of "W". "p" is obviously a chosen prime number. However this implementation computes "W=(2^L) mod p". "L" is a predefined constant equal to "0x30000000", which is most definitely not a power of base 2. This directly contradicts several different mathematical abstracts I've found which seem to indicate that "L" should not only be the number of elements in the source array (and thus a power of base 2), but also variable to boot! Obviously I'm missing something important here. Can someone please resolve this contradiction. How was the value of "L" chosen here? More importantly, given a different prime number how would one go about determining the corresponding value of "L"?