정수 링에서 FFT를 사용하는 곱셈

Question

정수 링에서 FFT를 사용하는 숫자의 임의의 BASE로 긴 정수를 곱해야합니다. 피연산자의 길이는 항상 이고 일부 코드는 k이고, 컨벌루션 벡터의 구성 요소는 2n이므로 2n'th 기본 단위가 필요합니다.

저는 효율성 문제에 특별히 관심이 없기 때문에 Strassen & Schönhage의 알고리즘을 사용하고 싶지 않습니다. 기본 회선을 계산하고 일부는 전달하고 그 외에는 아무 것도 없습니다. 그것은 많은 수학자 간단한 보인다하더라도

은, 대수에 대한 이해는 정말 나쁜, 그래서 나는 많은 질문이 있습니다

정수 반지의 FFT를 수행 사이의 중요한 차이 또는 뉘앙스은 무엇

1. 이 2^n + 1 모듈로를 (아마 composite) 그리고 정수 FIELDS modulo some primime p?
   
   2^n == -1 (mod 2^n+1)이므로 2은 (2n)th과 같은 반지의 화합 근원이기 때문에 부탁드립니다. 반대로 정수 필드는 원시 원시를 찾아야합니다.
   
   그러나 FFT에 이러한 양식의 링을 사용하지 못하게하는 다른 뉘앙스가있을 수 있습니다.

2. 정수 링을 선택한 경우이 필드에 2^n 번째 단일 화음의 존재 조건은 무엇입니까? 작은 질서의 통일
   
   다른 모든 2^k 번째 뿌리는 바로,이 루트를 제곱하여 얻을 수 있을까? .. 반지의 모듈로 곱셈에 부과하는 필수 어떤 제한

3. 를? 어쩌면 길이가 어쩌면 숫자 기지에 있을지도 모르겠다. 아마도 곱셈에 사용 된 숫자 유형에서도 가능할 것이다.
   
   컨볼루션 계수가 모듈러스 연산에 의해 감소되는 경우 약간의 정보 손실이있을 것으로 생각됩니다. 사실이고 왜 그런가요? 내가 이것을 피할 수있는 일반적인 조건은 무엇입니까?
   
   

4. 단지 동적리스트를 기본 형식의 모든 가능성이있다 (즉 long) FFT 벡터들은 제품과 컨벌루션 벡터 충분? 또는 계수를 BigInteger으로 변환해야합니까? (실제로해야 할 때 "사례"는 무엇입니까?)

이러한 질문에 대한 일반적인 대답이 너무 오래 걸릴 경우 다음 조건에서 답을 얻으면 특히 만족할 것입니다. 나는 필드 Z_70383776563201에 2^30까지 순서의 일치의 기본 뿌리의 테이블을 발견했습니다

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

을 그래서 정밀도 어떤 길이 2^29의 숫자를 곱 연합의 2^30 번째 루트를 사용하는 경우/알고리즘/효율성 뉘앙스 고려해야합니까? ...

미리 감사드립니다. 나는 최선의 해결책에 대해 현상금을 수여 할 예정입니다 - 몇 가지 예를 들어 도와주십시오.

Answer 1

먼저 신원에 대한 산술적 인 설명 : 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의 배열을 사용하려면 기본적으로 큰 정수 라이브러리를 다시 작성해야합니다.

Answer 2

생각에는 우리는 두 개의 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]에 대한 문제는 너무 커서 O (1) 시간에 w * a_i를 수행 할 수 없습니다.