mersenneforum.org > Math Primitive root question
 Register FAQ Search Today's Posts Mark Forums Read

 2009-07-10, 00:41 #1 __HRB__     Dec 2008 Boycotting the Soapbox 10110100002 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

 Similar Threads Thread Thread Starter Forum Replies Last Post PawnProver44 Miscellaneous Math 7 2016-04-18 23:49 akruppa Math 0 2007-09-06 20:23 Numbers Math 16 2005-09-21 23:41 juergen Math 12 2005-03-09 08:18 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