20120531, 10:03  #1 
May 2012
2^{2} Posts 
help on FFT in Z/mZ
Hi,
I have just subscribed to this mailinglist even if I am very interested in primes search. I intend to write a program to find prime Mersenne numbers using LucasLehmer test and FFT in Z/mZ (the ring of integers modulo an prime integer m). I need some documentation on how to find a primitive root of unity andFind all nth roots of unity in Z*p (arithmetic is mod p) . 
20120531, 11:51  #2 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Try a = 2, 3, 5, 6, 7, 10, ... (nonpowers) (mod p) and test that for each prime q  p1, a^{([I]p[/I]1)/[I]q[/I]} != 1 (mod p). Then, and only then, is a a primitive root modulo p. To get a primitive nth root r modulo p, where n  p1, use r = a^{([I]p[/I]1)/[I]n[/I]} (mod p).
Last fiddled with by akruppa on 20120531 at 18:35 
20120531, 12:03  #3 
Jun 2003
3^{4}·5·13 Posts 
Googling "Number theoretic transform" might help.
EDIT: So not a mailing list. Last fiddled with by axn on 20120531 at 12:04 
20120531, 17:34  #4 
"Lucan"
Dec 2006
England
2·3·13·83 Posts 

20120531, 17:35  #5 
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
31·359 Posts 

20120531, 19:27  #6 
If I May
"Chris Halsall"
Sep 2002
Barbados
2·3·1,697 Posts 

20120531, 23:19  #7 
"Gang aft agley"
Sep 2002
2·1,877 Posts 

20120601, 05:39  #8 
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
31×359 Posts 

20120601, 08:36  #9 
May 2012
2^{2} Posts 

20120601, 08:49  #10  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
31·359 Posts 
Quote:
"Mail" has several meanings in English. As well as a form of written communication, mail is also a type of armour. Chainmail armour is a network of interlinked metal rings attached to some backing material, traditionally either leather or woollen cloth. Platemail is made from solid sheets of metal, usually held together and onto the wearer by leather straps. A ring, as you doubtless know, is a specific mathematical object. Z/mZ is a ring in this sense. Further wordplay there. Finally (though first in the thread) "mail" and "male" are pronounced the same in English and although femail isn't really an English word it is very often seen. Apologies if this is teaching you stuff you already know but I doubt you're the only person here whose first language is not English. Paul 

20120601, 10:18  #11  
May 2012
4_{8} Posts 
Quote:
Thank you. but how to use mailing list, plating list, OP,... to find all nth roots of unity. please if you have any link or website . 
