2009-07-10, 00:41 | #1 |
Dec 2008
Boycotting the Soapbox
1011010000_{2} Posts |
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) and 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 |
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 |