Описание тега ntt
Number Theoretic Transform - form of discrete Fourier transform on finite fields
1
ответ
Модульная арифметика и NTT (конечное поле DFT) оптимизации
Я хотел использовать NTT для быстрого возведения в квадрат (см. Быстрое вычисление квадрата bignum), но результат был медленным даже для действительно больших чисел - более 12000 бит. Итак, мой вопрос: Есть ли способ оптимизировать мое преобразовани…
02 сен '13 в 16:01
1
ответ
Реализация БПФ над конечными полями
Я хотел бы реализовать умножение полиномов с использованием NTT. Я следовал за Теоретико-числовым преобразованием (целое число DFT), и это, кажется, работает. Теперь я хотел бы реализовать умножение многочленов над конечными полями Z_p[x] где p прои…
11 сен '18 в 06:57
1
ответ
Несколько где условие в NTT Framework MVC
Несколько, где условие в следующем коде приводит к отображению только первой строки, public bill_transaction Getbill_transaction(int id) { bill_transaction bill_transaction = db.bill_transaction.Where(m => m.Cust_Id == id && m.Bill_Status…
01 сен '15 в 17:41
0
ответов
Вычисление W для NTT (целочисленное быстрое преобразование Фурье)
Я пытаюсь реализовать NTT (Числовое Теоретическое Преобразование) в Задаче C, однако в опубликованных онлайн абстрактных математических документах отсутствуют важные детали. Я нашел следующий существующий Вопрос о переполнении стека, который подразу…
30 июл '14 в 06:15
0
ответов
Числовое теоретическое преобразование умножения смещено
Я работал над кодом для умножения полиномов с использованием NTT (FFT), и я сделал 2 разных реализации и использовал существующие для проверки, например: https://www.nayuki.io/page/number-theoretic-transform-integer-dft, https://github.com/iblue/ntt…
05 апр '18 в 18:17
3
ответа
Перевод с комплексного БПФ на конечное поле-БПФ
Добрый день! Я пытаюсь разработать алгоритм NTT, основанный на наивной рекурсивной реализации FFT, которую я уже имею. Рассмотрим следующий код (coefficientsдлина, пусть будет m, это точная степень двух): /// <summary> /// Calculates the resul…
21 апр '12 в 16:36
1
ответ
Существует ли самая известная реализация для числового теоретического преобразования на конечном поле 257 (2^8 + 1)?
Я немного новичок, когда дело доходит до реализации БПФ в целом, но я думаю, что у меня есть большинство основных идей. В этом конкретном случае у меня есть реализация теоретико-числового преобразования в конечном поле 257. Это в основном ваш типичн…
30 мар '15 в 03:10
0
ответов
Теоретическое преобразование числа
Я испытываю трудности с реализацией NTT. После прочтения большого количества руководств по БПФ и NTT с http://www.apfloat.org/ntt.html, http://codeforces.com/blog/entry/43499 и некоторых других, я реализовал NTT, используя преимущества теории Ферма.…
22 ноя '16 в 07:59
1
ответ
Возможна ли идея шаблона <int ...> в C++?
Я пытаюсь научиться реализовывать templateв C++. Когда я меняю свой код NTT (Теоретико-числовое преобразование) на код, использующийtemplate, который выглядит так: template <long long mod> struct NTT{ int x = 0; NTT(){ long long p = mod-1; whi…
31 янв '20 в 01:28
0
ответов
Как найти первообразный корень высокой степени (2^16), большое простое число (60 бит) для операции NTT в гомоморфном шифровании?
Мне любопытно, как узнать корень из единицы (n-й или 2n-й) многочлена высокой степени, большого размера в битах в операции NTT (в моем случае: N = 2^16, q = k*N + 1 (60 бит)) для некоторых приложений гомоморфного шифрования. К сожалению, SEAL lib. п…
18 ноя '20 в 05:43
0
ответов
умножение полиномов над конечным полем с использованием отрицательной сверточной свертки и теоретико-числового преобразования
Я пытаюсь выполнить полиномиальное умножение по кольцу Zp[x]/(x^n+1)с использованием теоретико-числового преобразования и отрицательной свернутой свертки. Я использовал код, доступный в https://www.nayuki.io/res/number-theoretic-transform-integer-df…
24 май '21 в 22:44
0
ответов
Попытка распараллелить NTT с потоками cpp
Я впервые задаю вопросы здесь, так что извините, если что-то не так.Я пытаюсь распараллелить NTT, используя потоки cpp, но я здесь просто потерялся. Я основал код на статье, объясняющей CUDA-распараллеливание NTT, и адаптировал его так, чтобы он име…
12 июл '21 в 07:52
0
ответов
Отличие Cooley Tukey-Gentleman Sande от DIT-DIF
Новичок здесь. Я хочу попросить о реализации NTT. Мы знаем, что есть несколько вариантов, таких как Cooley-Tukey, Gentleman-Sande и Stockholm. Кроме того, есть то, что называется прореживанием во времени (DIT) и прореживанием по частоте (DIF). Наско…
25 окт '22 в 10:07
1
ответ
Круговая свертка бинарных векторов (mod 2) с использованием NTT
Пусть x, y будут векторами длины n с элементами 1 или 0. Я хочу эффективно вычислить круговую свертку (x * y) mod 2 Где каждая составляющая результата берется по модулю 2. Я знаю, как это сделать с помощью быстрого преобразования Фурье (умножить пре…
22 дек '22 в 02:04