0

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"?

Community
  • 1
  • 1
JasonA
  • 36
  • 2
  • 2
    wouldn't this question be also good on mathematical stack? – mishan Jul 30 '14 at 06:17
  • (and/or in algorithmic stack) – mishan Jul 30 '14 at 06:18
  • Don't get hung up on the exact letters chosen. What **quantities** do they denote? I suspect one `L` is constant and the other isn't because they denote two different quantities. – MSalters Jul 30 '14 at 06:54
  • The mathematical documents in fact *don't* use the identifier "L" at all. I'm not hung up on the name of the variable. I'm only concerned with its value and how that value is derived. – JasonA Jul 30 '14 at 18:52

0 Answers0