mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-05-31, 10:03   #1
habib106
 
May 2012

22 Posts
Default 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) .

habib106 is offline   Reply With Quote
Old 2012-05-31, 11:51   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2012-05-31, 12:03   #3
axn
 
axn's Avatar
 
Jun 2003

34·5·13 Posts
Default

Googling "Number theoretic transform" might help.

EDIT:- So not a mailing list.

Last fiddled with by axn on 2012-05-31 at 12:04
axn is offline   Reply With Quote
Old 2012-05-31, 17:34   #4
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Quote:
Originally Posted by axn View Post
Googling "Number theoretic transform" might help.

EDIT:- So not a mailing list.
Femaling list?
davieddy is offline   Reply With Quote
Old 2012-05-31, 17:35   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

31·359 Posts
Default

Quote:
Originally Posted by davieddy View Post
Femaling list?
No, a plating list.
xilman is online now   Reply With Quote
Old 2012-05-31, 19:27   #6
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2·3·1,697 Posts
Default

Quote:
Originally Posted by davieddy View Post
Femaling list?
Play nice....
chalsall is online now   Reply With Quote
Old 2012-05-31, 23:19   #7
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

Quote:
Originally Posted by xilman View Post
No, a plating list.
Plate won't do. OP is working with rings.
only_human is offline   Reply With Quote
Old 2012-06-01, 05:39   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

31×359 Posts
Default

Quote:
Originally Posted by only_human View Post
Plate won't do. OP is working with rings.
True. It must be a mailing list then.
xilman is online now   Reply With Quote
Old 2012-06-01, 08:36   #9
habib106
 
May 2012

22 Posts
Default

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

thank for your feedback

but I didn't understand what you mean by mailing list
habib106 is offline   Reply With Quote
Old 2012-06-01, 08:49   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

31·359 Posts
Default

Quote:
Originally Posted by habib106 View Post
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
xilman is online now   Reply With Quote
Old 2012-06-01, 10:18   #11
habib106
 
May 2012

48 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
please if you have any link or website .

habib106 is offline   Reply With Quote
Reply

Thread Tools


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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”