Mersenne: FFT length
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. But, you can also store the digits b0, b1 ... bp in both real and imaginary parts of a complex signal s2 and then apply a FFT on s2. Thus, the cost to square N become : n/2*log2(n/2)+n/2+n/2*log2(n/2)=n*log2(n)-n/2. Furthermore, the Discrete Fourier Transform allows to divide the FFt length by two and perform the mod operation. Is it possible to combine these two techniques so as to divide the FFT length by four ? _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: roots of two
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 Lycée Fauriel Saint-Etienne _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: operations allowed with values in the frequency domain
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 of values in the frequency domain ? For example, let vc[i]=va[i] / vb[i] for i=0 to n-1, would we get C=IFFT(vc[0..n-1])=A / B ? _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Stop computations before the last term of the Lucas-Lehmer serie
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, during the inverse transform or during the substraction. So, this test is cheap and it would not slow down the program. However, it would be interesting if and only if a term of the Lucas-Lehmer serie can be 0 before the last term. What do you think about this idea ? _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: NTT faster than FFT ?
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 modulo a prime p. Thus, all operations are done modulo p ( that is to say, in the ring of integers modulo p) . There are restrictions for the choice of p : - the length l of then NTT must divide (p-1) ; - the radix b must be lower than p ; - p must be prime and (p-1)highly composite. With 32 bit integers , a common choice is : p=13*2^28+1 ; b=2^28. So, the number M represented by an array t[0..(l-1)] of l elements is : M=t[0]+t[1]*b+...+t[l-1]*b^(l-1)=t[0]+t[1]*2^28+...+t[l-1]*(2^28)^(l-1) . Usually, we do several NTT modulo different primes and then use the Chinese Remainder Theorem to get t[0] ;...; t[i] ;...; t[l-1] modulo p, because the terms in the central loop of the transform can exceed the largest integer that fits in a word machine (for instance, 2^32-1) . That's one of the reasons why NTT are slower than FTT. Why don't we compute these terms modulo p at each step of the central loop ? Consequently, it would be useless to do several NTT and the Chinese Remainder Theorem would not be required. Even if I am wrong, the speed of NTT can be improved by using 64 bit integers ( shorter NTT length ) supported by both new processors and new C compilers, and by using Intel MMX instructions. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: FFT modulo a prime
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 is Caml-Light, but I also know C and Pascal languages I represent big numbers with arrays I choose m=7*2^26+1 Thus, I have 26 free bits per element of arrays, so I decide to represent my big numbers in binary using the 26 first bits of each elements of arrays I have a problem with the multiplication (the square) When I do the IFFT, to get back 'the coefficients of the polynom' that represents the number I have to square, I may get a 'coefficient' between 2^26 and 7*2^26+1 since all operations are modulo m What do I have to do with the 26th,27th and 28th bits ? PS:I have already read the FAQ ; I just want to make a FFT to multiply numbers without taking the result mod a Mersenne number _ Unsubscribe list info -- http://wwwndatechcom/mersenne/signuphtm Mersenne Prime FAQ -- http://wwwtasamcom/~lrwiman/FAQ-mers
