Расчет W для NTT (целочисленное быстрое преобразование Фурье)

Я пытаюсь реализовать NTT (Числовое Теоретическое Преобразование) в Задаче C, однако в опубликованных онлайн абстрактных математических документах отсутствуют важные детали. Я нашел следующий существующий Вопрос о переполнении стека, который подразумевает включение работающей (хотя и неоптимальной) реализации NTT:
Модульная арифметика и NTT (конечное поле DFT) оптимизации

Мой вопрос касается вычисления «W». «р», очевидно, выбрано простое число. Однако эта реализация вычисляет «W = (2 ^ L) mod p». «L» — это предопределенная константа, равная «0x30000000», что, безусловно, не является степенью основания 2. Это прямо противоречит нескольким различным математическим тезисам, которые я нашел, которые казаться чтобы указать, что «L» должно быть не только количеством элементов в исходном массиве (и, следовательно, степенью основания 2), но и переменной для загрузки! Очевидно, я упускаю что-то важное здесь. Может кто-нибудь, пожалуйста, разрешите это противоречие. Как здесь было выбрано значение «L»? Что еще более важно, учитывая другое простое число, как можно определить соответствующее значение «L»?

0

Решение

Задача ещё не решена.

Другие решения


По вопросам рекламы [email protected]