Go Back > Great Internet Mersenne Prime Search > Math

Thread Tools
Old 2009-07-10, 00:41   #1
__HRB__'s Avatar
Dec 2008
Boycotting the Soapbox

10110100002 Posts
Default Primitive root question

I thought I could speed up a certain type of transform by considering primitive roots of polynomials (mod x^k+1). My knowledge in this area is limited, so I hope to gain better understanding by looking at simple examples. Please add a mental "(right?)" to everything that follows, and humiliate me by telling me where I've gone wrong.

P(x) = 1 (mod x^2+1) is unity. Fine, but unfortunately,

P(x) = -1 is a 1st root of unity, as (-1)^2 = 1 (mod x^2+1)
P(x) = ix is also a 1st root of unity, because (ix)^2 = -x^2 = 1 (mod x^2+1)

Two first roots? Huh? If I want to do an FFT, which one do I take?

It would be nice if I could use roots of the form wx+0x or 0x+w.

Last question: 2^8+1 is a Fermat prime, so I get 2^8 roots and lots of them have only a couple of bits set, so multiplying a polynomial by a root would be easy. Is there an obvious way to find simple roots like these (if it made sense to do so), that I'm too stupid to see?

EDIT: I'm pretty certain that part 1 has to with principal vs. primitive roots. Intuition tells me that I need to use -1. Rotating the coefficients with wraparound seem to be principal roots, as they sum up to 0.

Last fiddled with by __HRB__ on 2009-07-10 at 01:01
__HRB__ is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Primitive Root of Mersenne Numbers PawnProver44 Miscellaneous Math 7 2016-04-18 23:49
New primitive trinomials akruppa Math 0 2007-09-06 20:23
Primitive Roots Numbers Math 16 2005-09-21 23:41
Is 3 always a primitive root for mersenne primes? juergen Math 12 2005-03-09 08:18
Is 3 always a primitive root for mersenne primes? juergen Programming 9 2005-03-08 03:51

All times are UTC. The time now is 17:04.

Tue Aug 3 17:04:21 UTC 2021 up 11 days, 11:33, 1 user, load averages: 2.80, 2.63, 2.73

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.