在整數環中使用FFT進行相乘

我需要使用整數環中的FFT將長整數與任意數字的BASE相乘。對於某些k，操作數總是長度爲n = 2^k，並且卷積矢量具有2n組件，因此我需要一個2n'th統一的原始根。在整數環中使用FFT進行相乘

我並不特別關心效率問題，所以我不想使用Strassen &Schönhage的算法 - 只是計算基本卷積，然後是一些運算，這沒什麼別的。

雖然看上去簡單，許多數學家，我代數的瞭解實在是太差了，所以我有很多的問題：

什麼是整數環執行FFT有着本質的區別或細微差別模2^n + 1 （也許是複合），並以整數FIELDS爲模p？

我問這個，是因爲2是(2n)th這個環的統一原始根，因爲2^n == -1 (mod 2^n+1)。相比之下，整數字段將要求我搜索這樣一個原始根。

但也許有其他細微差別，這將阻止我使用這種形式的環用於FFT。
如果我選擇了整數環，那麼在此字段中存在2^n單位根的充分條件是什麼？

所有其他2^k較小秩序的統一個根可以用平方這根獲得，對吧？..
由環模的乘法強加什麼必要限制嗎？也許在它們的長度上，也許在數字基礎上，甚至可能在用於乘法的數字類型上。

我懷疑如果通過模運算減少卷積的係數，可能會有一些信息丟失。這是真的，爲什麼？..什麼是一般條件，可以讓我避免這種情況？
是否有隻是原始類型的動態列表的任何可能性（即long）將足以滿足FFT矢量，它們的產物和卷積矢量？或者我應該將這些係數轉換爲BigInteger以防萬一（當我真的應該做什麼時「情況」）？

如果這些問題的一般答案花費太長時間，我會特別滿意的答案在下列條件下。我在外地Z_70383776563201發現，爲了統一的原根的表達2^30：

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

所以，如果我使用統一的2^30次方根繁殖長度2^29的號碼，什麼是精密/算法/效率細微差別我應該考慮什麼？..

非常感謝你提前！我要獎賞最好的答案 - 請考慮幫助一些例子。

來源

2012-04-20 wh1t3cat1k

嘗試這裏更多的理論數值分析的問題：http://scicomp.stackexchange.com/ – tskuzzy 2012-04-20 09:58:59

這是一個非常先進的問題 - 我可能是幾個人誰擁有實際動手經驗，在這方面的一個能夠回答它。但是它太大而無法在SO上得到回答。這將需要頁面和頁面的文字+圖... – Mysticial 2012-04-20 10:14:24

我明白了......但是沒有證據的基本事實會佔用這麼多頁面嗎？也許，爲了證明，我可以在你的幫助下找到方向。另外，在特別關注我的問題結束時，我還特別加以限制。我還欠他一些啤酒，他甚至可以以非常深的方式回答這個問題。 – wh1t3cat1k 2012-04-20 10:34:08

首先，你的身份的算術線索：70383776563201 = 1 + 65550 * 2^30。而那個長數字是主要的。有關How the FFT constants were found頁面上的模數有很多見解。

這裏有一個你應該知道的羣論的事實。整數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數組，你基本上是重寫你的大整數庫。

來源

2012-11-08 20:36:17 eh9

假設我們需要計算兩個n位整數乘法

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

現在， w = 2, x =[w^0,w^1,...w^{m-1}] (mod p)。

的問題，對於每個x [我]，這將是太大，我們不能做寬*在O（1）時間A_I。

來源

2016-01-22 18:05:04 Kevin

在整數環中使用FFT進行相乘

回答

相關問題