Вычисление W для NTT (целочисленное быстрое преобразование Фурье)
Я пытаюсь реализовать NTT (Числовое Теоретическое Преобразование) в Задаче C, однако в опубликованных онлайн абстрактных математических документах отсутствуют важные детали. Я нашел следующий существующий Вопрос о переполнении стека, который подразумевает включение работающей (хотя и неоптимальной) реализации NTT: модульная арифметика и оптимизация NTT (конечное поле DFT)
Мой вопрос касается вычисления "W". "р", очевидно, выбрано простое число. Однако эта реализация вычисляет "W=(2^L) mod p". "L" - это предопределенная константа, равная "0x30000000", что, безусловно, не является степенью основания 2. Это прямо противоречит нескольким разным математическим тезисам, которые я обнаружил и которые указывают, что "L" должно быть не только числом элементы в исходном массиве (и, следовательно, степень основания 2), но также переменная для загрузки! Очевидно, я упускаю что-то важное здесь. Может кто-нибудь, пожалуйста, разрешите это противоречие. Как здесь было выбрано значение "L"? Что еще более важно, учитывая другое простое число, как можно определить соответствующее значение "L"?