mersenneforum.org > Math help on FFT in Z/mZ
 Register FAQ Search Today's Posts Mark Forums Read

 2012-05-31, 10:03 #1 habib106   May 2012 22 Posts help on FFT in Z/mZ Hi, 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). I need some documentation on how to find a primitive root of unity andFind all n-th roots of unity in Z*p (arithmetic is mod p) .
 2012-05-31, 11:51 #2 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Try a = 2, 3, 5, 6, 7, 10, ... (non-powers) (mod p) and test that for each prime q | p-1, 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 n-th root r modulo p, where n | p-1, use r = a([I]p[/I]-1)/[I]n[/I] (mod p). Last fiddled with by akruppa on 2012-05-31 at 18:35
 2012-05-31, 12:03 #3 axn     Jun 2003 34·5·13 Posts Googling "Number theoretic transform" might help. EDIT:- So not a mailing list. Last fiddled with by axn on 2012-05-31 at 12:04
2012-05-31, 17:34   #4
davieddy

"Lucan"
Dec 2006
England

2·3·13·83 Posts

Quote:
 Originally Posted by axn Googling "Number theoretic transform" might help. EDIT:- So not a mailing list.
Femaling list?

2012-05-31, 17:35   #5
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

31·359 Posts

Quote:
 Originally Posted by davieddy Femaling list?
No, a plating list.

2012-05-31, 19:27   #6
chalsall
If I May

"Chris Halsall"
Sep 2002

2·3·1,697 Posts

Quote:
 Originally Posted by davieddy Femaling list?
Play nice....

2012-05-31, 23:19   #7
only_human

"Gang aft agley"
Sep 2002

2·1,877 Posts

Quote:
 Originally Posted by xilman No, a plating list.
Plate won't do. OP is working with rings.

2012-06-01, 05:39   #8
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

31×359 Posts

Quote:
 Originally Posted by only_human Plate won't do. OP is working with rings.
True. It must be a mailing list then.

2012-06-01, 08:36   #9
habib106

May 2012

22 Posts

Quote:
 Originally Posted by xilman True. It must be a mailing list then.

but I didn't understand what you mean by mailing list

2012-06-01, 08:49   #10
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

31·359 Posts

Quote:
 Originally Posted by habib106 thank for your feedback but I didn't understand what you mean by mailing list
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

2012-06-01, 10:18   #11
habib106

May 2012

48 Posts

Quote:
 Originally Posted by xilman 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

Thank you.

but how to use mailing list, plating list, OP,... to find all n-th roots of unity.

All times are UTC. The time now is 19:09.

Wed Jan 19 19:09:58 UTC 2022 up 180 days, 13:38, 1 user, load averages: 1.46, 1.58, 1.51