This is a follow-up to this question. I'm interested in doing trigonometry in finite fields on a computer. I do not understand precisely how trigonometric functions are supposed to work in a finite (Galois) field. I've read the Wikipedia article but I'm having trouble understanding what sorts of angles and numbers are representable in finite fields.
Here is what I do understand:
Starting with the 2D Cartesian plane with coordinates x, y, we can represent discrete angles that are multiples of 90∘=π2. These are the fourth roots of unity x=cos2kπ4 and y=sin2kπ4 or alternatively:
z=coskπ2+isinkπ2, where k is a positive integer less than 4. These numbers can be represented solely with the integers. If we want to add discrete angles that are multiples of 30∘=2π12, we need a quadratic extension of the integers so that we have quadratic (algebraic) integers of the form a+b√3. This allows us to represent the twelfth roots of unity as x and y coordinates. If we wish to double the number of angles to 15∘=2π24 multiples, we must extend our field again, forming a tower of quadratic extensions with numbers of the form (a+b√3)+(c+d√3)√2. Numbers of this form allow us to represent the 24th roots of unity.
How does this work in a finite field? Can I choose a finite field such that I can exactly represent the nth roots of unity in a manner analogous to the above? I'm particularly interested in constructable numbers, which feature only quadratic extensions (and multiquadratic extensions like √5+√5). In particular this means that n is restricted to having factors of 2 and Fermat primes. I restricted myself to powers of 2 and Fermat prime 3 in my example above. Both 12 and 24 have factors of only 2 and 3.
- Edit -
To try to clarify what I'm struggling with. I do not see how to find or use a finite field that has been extended twice or more (e.g. angles of π12 as described above), as the relationship to the complex plane in a finite field setting seems to blur as the tower of extensions grows.
This is a new subject for me, so I'd really appreciate an example or two to go along with any explanations.
No comments:
Post a Comment