我正在尝试在 Objective C 中实现 NTT（数论变换），但是在线发布的抽象数学文档缺少关键细节。我发现了以下关于 Stack Overflow 的现有问题，该问题声称包括 NTT 的工作（尽管不是最佳）实现： 模块化算法和 NTT（有限域 DFT）优化
我的问题是关于“W”的计算。“p”显然是一个选择的素数。然而，这个实现计算“W=(2^L) mod p”。“L”是一个预定义的常数，等于“0x30000000”，这绝对不是以 2 为底的幂。这与我发现的几个不同的数学摘要直接矛盾，这似乎表明“L”不仅应该是源数组中的元素（因此是基数 2 的幂），但也可以启动！显然我在这里遗漏了一些重要的东西。有人可以解决这个矛盾吗？此处“L”的值是如何选择的？更重要的是，给定一个不同的素数，如何确定“L”的对应值？