help on FFT in Z/mZ
 

[SIZE=3][FONT=Calibri]Hi,[/FONT][/SIZE]
[COLOR=black][FONT=Arial]I have just subscribed to this mailing-list even if I am very interested in
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). [/FONT][/COLOR]
[COLOR=black][FONT=Arial] [/FONT][/COLOR]
[COLOR=black][FONT=Arial]I need some documentation on how to find a primitive root of unity and[/FONT][/COLOR][COLOR=black][FONT=Symbol] [/FONT][/COLOR][COLOR=black][FONT=Arial][SIZE=3]Find all n-th roots of unity in Z*p (arithmetic is mod p) .[/SIZE][/FONT][/COLOR]
[COLOR=black][FONT=Arial][SIZE=3][/SIZE][/FONT][/COLOR]
[COLOR=black][FONT=Arial][SIZE=3][/SIZE][/FONT][/COLOR]

Try [I]a[/I] = 2, 3, 5, 6, 7, 10, ... (non-powers) (mod [I]p[/I]) and test that for each prime [I]q[/I] | [I]p[/I]-1, [I]a[/I][SUP]([I]p[/I]-1)/[I]q[/I][/SUP] != 1 (mod [I]p[/I]). Then, and only then, is [I]a[/I] a primitive root modulo [I]p[/I]. To get a primitive [I]n[/I]-th root [I]r[/I] modulo [I]p[/I], where [I]n[/I] | [I]p[/I]-1, use [I]r[/I] = [I]a[/I][SUP]([I]p[/I]-1)/[I]n[/I][/SUP] (mod [I]p[/I]).

Googling "Number theoretic transform" might help.

EDIT:- So not a mailing list.

[QUOTE=axn;300825]Googling "Number theoretic transform" might help.

EDIT:- So not a mailing list.[/QUOTE]
Femaling list?

[QUOTE=davieddy;300850]Femaling list?[/QUOTE]No, a plating list.

[QUOTE=davieddy;300850]Femaling list?[/QUOTE]

Play nice....

[QUOTE=xilman;300851]No, a plating list.[/QUOTE]Plate won't do. OP is working with rings.

[QUOTE=only_human;300892]Plate won't do. OP is working with rings.[/QUOTE]True. It must be a mailing list then.

[QUOTE=xilman;300918]True. It must be a mailing list then.[/QUOTE]


thank for your feedback

[URL="http://www.google.co.ma/search?q=but+I+didn%27t+understand+what+you+mean&hl=fr&gbv=2&gs_l=hp.3...1868.15862.0.16096.4.4.0.0.0.0.171.358.3j1.4.0...0.0.Cjry6p6poZQ&nfpr=1&spell=1&sa=X"][B][I][COLOR=#1111cc]but I didn't understand what you mean[/COLOR][/I][/B][/URL] by mailing list

[QUOTE=habib106;300931]thank for your feedback

[URL="http://www.google.co.ma/search?q=but+I+didn%27t+understand+what+you+mean&hl=fr&gbv=2&gs_l=hp.3...1868.15862.0.16096.4.4.0.0.0.0.171.358.3j1.4.0...0.0.Cjry6p6poZQ&nfpr=1&spell=1&sa=X"][B][I][COLOR=#1111cc]but I didn't understand what you mean[/COLOR][/I][/B][/URL] by mailing list[/QUOTE]Sorry, some erudite wordplay which many non-native speakers would have difficulty decoding.

"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

[QUOTE=xilman;300932]Sorry, some erudite wordplay which many non-native speakers would have difficulty decoding.

"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[/QUOTE]


Thank you.

but how to use [COLOR=#000000]mailing list, [COLOR=#000000]plating list, OP,...[/COLOR][/COLOR] to find [COLOR=#000000]all n-th roots of unity. [/COLOR]
[COLOR=#000000]please if you have any link or [B]website[/B] .[/COLOR]
[COLOR=#000000][/COLOR]
[COLOR=#000000][/COLOR]