In this message, I assume FFT are complex FFT and are used to quickly
square numbers.
Let N=bp*B^p+...+b2*B^2+b1*B+b0.
You can store the digits b0, b1 ... bp in the real part of a complex signal
s1 and then apply a FFT on s1. Thus, the cost to square N is :
n*log2(n)+n+n*log2(n) with n=2*p.
I try to make an integer DWT (I already write a NTT that works) .
I use the prime number : 3221225473=3*2^30+1 ; the primitive root is 5 ;
the order of 2 is 3*2^28.
Are there Nth roots of two for each prime of the form p=k*2^N+1 ?
How can we quickly find a Nth root of two ?
Yan Naessens
MPSI
With a FFT, we get values va[0..n-1] and vb[0..n-1] in the frequency domain
of 2 numbers A and B that we can add, substract or multiply.
For example, let vc[i]=va[i]*vb[i] for i=0 to n-1, if we do an IFFT with
the values vc[i], we get C=IFFT(vc[0..n-1])=A*B.
Can we divide or compute remainders
If a term of the Lucas-Lehmer serie equals 0 modulo Mx, then if it is the
last term Mx is prime else Mx is not prime (because next terms will be -2 ;
4 ; 4 ; 4...). In both cases, we needn't compute next terms.
Checking if a term of the Lucas-Lehmer serie equals 0 can be done, for
example,
I might have found a way of speeding up NTT that are usually slower than FFT.
Firts, as some people may not know Number Theoritic Transfoms ( NTT ) , I
am going to remember few ideas about them. NTT are also called FFT modulo a
prime. Instead of using complex numbers, NTT compute wxith integer
I have just subscribed to this mailing-list even if I am very interested in
both programming and primes search
I intend to write a program to find prime Mersenne numbers using
Lucas-Lehmer test and FFT in Z/mZ (the ring of integers modulo an prime
integer m) The language I use for this purpose
