Умножение с использованием БПФ в кольцах целых чисел

Мне нужно умножить длинные целые числа на произвольную ОСНОВУ цифр, используя БПФ в целочисленных кольцах. Операнды всегда имеют длину n = 2^k для некоторых k, а вектор свертки имеет 2n компонентов, поэтому мне нужен 2n'th примитивный корень из единицы.

Меня не особенно интересуют вопросы эффективности, поэтому я не хочу использовать алгоритм Штрассена и Шёнхаге — просто вычисляю базовую свертка, затем некоторые переносы, и больше ничего.

Несмотря на то, что многим математикам это кажется простым, я очень плохо понимаю алгебру, поэтому у меня много вопросов:

  1. Каковы существенные различия или нюансы между выполнением БПФ в целочисленных кольцах по модулю 2^n + 1 (возможно, составных) и в целочисленных ПОЛЯХ по модулю некоторого простого числа p?

    Я спрашиваю это, потому что 2 является (2n)th примитивным корнем из единицы в таком кольце, потому что 2^n == -1 (mod 2^n+1). Напротив, целочисленное поле потребовало бы от меня поиска такого примитивного корня.

    Но, возможно, есть и другие нюансы, которые помешают мне использовать кольца такой формы для БПФ.

  2. Если я выбрал целочисленные кольца, то каковы достаточные условия для существования 2^n-го корня из единицы в этом поле?

    Все остальные 2^k-го корня из единицы меньшего порядка можно было бы получить возведением этого корня в квадрат, верно?..

  3. Какие существенные ограничения накладываются на умножение по модулю кольца? Может быть, по их длине, может быть, по числовой основе, может быть, даже по числовым типам, используемым для умножения.

    Я подозреваю, что может быть некоторая потеря информации, если коэффициенты свертки уменьшаются операцией по модулю. Так ли это и почему?.. Какие общие условия позволят мне этого избежать?

  4. Есть ли вероятность того, что для векторов БПФ, их произведения и вектора свертки будет достаточно просто динамических списков примитивного типа (т.е. long)? Или мне на всякий случай преобразовать коэффициенты в BigInteger (а какой "случай", когда действительно надо)?

Если общий ответ на эти вопросы занимает слишком много времени, я был бы особенно удовлетворен ответом при следующих условиях. Я нашел таблицу первообразных корней единичного порядка до 2^30 в поле Z_70383776563201:

http://people.cis.ksu.edu/~rhowell/calculator/roots.html

Итак, если я использую 2^30th корень из единицы для умножения чисел длины 2^29, какие нюансы точности/алгоритма/эффективности я должен учитывать?..

Огромное спасибо заранее! Я собираюсь присудить награду за лучший ответ - пожалуйста, рассмотрите возможность помочь с некоторыми примерами.


math multiplication fft arbitrary-precision
person wh1t3cat1k    schedule 20.04.2012    source источник
comment
Попробуйте здесь, чтобы получить дополнительные вопросы по теоретическому численному анализу: scicomp.stackexchange.com   -  person tskuzzy    schedule 20.04.2012
comment
Это очень сложный вопрос, и я, вероятно, один из немногих людей, имеющих реальный практический опыт в этой области, чтобы ответить на него. Но он слишком велик, чтобы на него можно было ответить на SO. Потребуются страницы и страницы текста + диаграммы...   -  person Mysticial    schedule 20.04.2012
comment
Понятно... Но неужели основные факты без доказательств займут столько страниц? Может быть, для доказательств, я мог бы найти направления с вашей помощью. Кроме того, я поставил специальное ограничение в конце вопроса, который меня особенно волнует. Я должен немного пива тому, кто ответил бы на это даже не особенно глубоко.   -  person wh1t3cat1k    schedule 20.04.2012

Ответы (2)


arrow_upward
2
arrow_downward

Во-первых, арифметическая подсказка о вашей личности: 70383776563201 = 1 + 65550 * 2^30. И это длинное число является простым. На странице Как были найдены константы БПФ< /а>.

Вот факт из теории групп, который вы должны знать. Мультипликативная группа целых чисел по модулю N является произведением циклических групп, порядки которых определяются простыми множителями числа N. Когда N простое число, существует один цикл. Однако порядки элементов в такой циклической группе связаны с простыми множителями N - 1. 70383776563201 - 1 = 2^31 * 3^1 * 5^2 * 11 * 13, а показатели указывают возможные порядки элементов.

(1) Вам не обязательно нужен примитивный корень, вам нужен тот, чей порядок по крайней мере достаточно велик. Существуют некоторые вероятностные алгоритмы нахождения элементов «высокого» порядка. Они используются в криптографии для обеспечения надежных параметров для ключевых материалов. В частности, для чисел вида 2^n+1 им уделялось много внимания, и вы можете посмотреть результаты.

(2) Достаточное (и необходимое) условие для элемента порядка 2^n иллюстрируется примером модуля. Условие состоит в том, что некоторый простой множитель p модуля должен обладать тем свойством, что 2^n | p - 1.

(3) Потеря информации происходит только в том случае, если элементы не являются мультипликативно обратимыми, чего нельзя сказать о циклической мультипликативной группе простого модуля. Если вы работаете в модульном кольце с составным модулем, некоторые элементы не так обратимы.

(4) Если вы хотите использовать массивы long, вам придется переписать свою библиотеку больших целых чисел.

person eh9    schedule 08.11.2012

arrow_upward
1
arrow_downward

Предположим, нам нужно вычислить два n-битных целочисленных умножения, где

n = 2^30;
m = 2*n; p = 2^{n} + 1

Итак, w = 2, x =[w^0,w^1,...w^{m-1}] (mod p).

Проблема в том, что для каждого x[i] он будет слишком большим, и мы не сможем выполнить w*a_i за время O(1).

person Kevin    schedule 22.01.2016