2
$\begingroup$

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^\circ = \frac{\pi}{2}$. These are the fourth roots of unity $x = \cos{\frac{2k\pi}{4}}$ and $y = \sin{\frac{2k\pi}{4}}$ or alternatively: $z = \cos{\frac{k\pi}{2}} + i\sin{\frac{k\pi}{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^\circ = \frac{2\pi}{12}$, we need a quadratic extension of the integers so that we have quadratic (algebraic) integers of the form $a + b\sqrt 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^\circ = \frac{2\pi}{24}$ multiples, we must extend our field again, forming a tower of quadratic extensions with numbers of the form $(a + b\sqrt 3) + (c + d\sqrt 3)\sqrt 2$. Numbers of this form allow us to represent the $24^{th}$ roots of unity.

How does this work in a finite field? Can I choose a finite field such that I can exactly represent the $n^{th}$ 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 $\sqrt{5 + \sqrt 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 $\frac{\pi}{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.

$\endgroup$
  • $\begingroup$ In will help us when you say exactly what is hard to understand in the Wikipedia article. In particular so that we won't repeat what is already there. Also try to check out the original references. $\endgroup$ – Martin Brandenburg Mar 19 '13 at 14:17
  • $\begingroup$ I have updated the post and checked the original references. $\endgroup$ – hatch22 Mar 19 '13 at 14:48
  • 2
    $\begingroup$ The field $\mathbb{Z}_7[i]$ of 49 elements has 24th roots of unity. For example $1+i$. In characteristic 5 you need to go to a sextic extension to find those. Having primitive roots of unity of order 24 forbids characteristic three (in addition to char two that you already made an exception of). You can find 24th roots of unity also in prime fields such as $\mathbb{Z}_{73}$. $\endgroup$ – Jyrki Lahtonen Mar 19 '13 at 14:56
  • 1
    $\begingroup$ The link to "the Wikipedia article" (the third link in your text) is broken, and wikipedia does not seem to contain an article about trigonometry in finite fields (maybe: not any more?). The closest I found in wikipedia is this section of a different article: en.wikipedia.org/wiki/… $\endgroup$ – Torsten Schoeneberg Jul 17 '18 at 1:02
  • 1
    $\begingroup$ @Torsten Thanks for the heads up. It looks like the article I originally linked to has been deleted or merged. The link you provided in your comment is the closest match I've been able to find as well. I've updated the link in the question. $\endgroup$ – hatch22 Jul 17 '18 at 18:05
2
$\begingroup$

$\def\C{\mathbb{C}} \def\F{\mathbb{F}} \def\R{\mathbb{R}} \def\Z{\mathbb{Z}} \newcommand\de{^\circ} \renewcommand\i[2]{{#1}{\rm i}{#2}} $

We have \begin{align*} \sin x=\frac{e^{ix}-e^{-ix}}{2i}\\ \cos x=\frac{e^{ix}+e^{-ix}}{2}\\ \end{align*} We may take both the domain and codomain of trigonometric functions as $\R$. We seek equivalent functions where the domain and codomain are finite and not necessarily equal.

Here I discuss cases where the codomain is a field $F$ of dimension 1 or 2, and the domain $A$ is $\Z_{n}$ where $n=|F|-1$. For example, $F=\F_p$ and $\Z_{p-1}$, or $F=\F_p[i]$ and $\Z_{p^2-1}$.

What in a field should correspond to $e^{ix}$

What goes wrong if we pick some value $u\in F$, and try using $u^x$ for $e^x$?

In any field $F$ of $n>3$ elements, not every non-zero element --- not even every element apart from 0, 1 and $-1$ --- generates the multiplicative group. For example, if $F=\Z_{73}$, the elements in $F$ corresponding to $\pm i\in\C$ (that is, those whose squares are $-1$) are 27 and 46. Where $g$ generates $F^\times$, $g^{27}$ has order only 8 and $g^{46}$ has order 36.

Thus using a field element $a\in F$ in an expression $g^a$ just because of some property of $a^2$ is unreliable.

So forget $i$ in exponents. $g\in F$ corresponds in $\C$ not to $e$ but to $e^i$. Where $a\in F$ corresponds to $x\in\C$, $e^{ix}\in \C$ corresponds in $F$ not to $g^{ai}$ but to $g^a$. (That $i$ is in $A$, and so, strictly speaking, is not $i$ but rather that element of $A$ that corresponds to $i\in\C$.)

We need $i$, so we just find an $i$ where $i^2=-1$, which entails $-1$ being a square mod $p$. $\F_2$ would not hold much interest, and trigonometry fails in fields of characteristic 2 anyway (see this MSE thread). Thus for $F$ we take a field of order $4k+1$. If $F=\F_p$, $p=4k+1$. However, $F=\F_p[i]$ can also work, provided $p=4k+3$.

Define sin and cos by \begin{align*} \sin a&=hi(g^{-a}-g^a)\\ \cos a&=h(g^a+g^{-a})\\ \end{align*} where $2h=1$ and $i^2+1=0$. (If $F=\Z_p[i]$, then that notation determines which of $-1$'s two square roots is notated $i$. If $F=\F_p$ then there are two choices for $i$, an issue I discuss later.)

$g^{-a}$ is just syntactic sugar for ${g'}^a$ or $(g^a)'$ where $'$ denotes multiplicative inverse or reciprocal. We may also interpret $g^{-a}$ as $g^{o-a}$ where $o$ is the multiplicative order of $g$.

Then the elementary trigonometric identities work, e.g. \begin{align*} \sin^2 a+\cos^2 a&=h^2[i^2(g^{-a}-g^a)^2+(g^a+g^{-a})^2]\\ &=h^2[i^2g^{-2a}-2i^2+i^2g^{2a}+g^{2a}+2+g^{-2a}]\\ &=h^2[(i^2+1)(g^{2a}+g^{-2a})-2i^2+2]\\ &=h^2[2-2i^2]\\ &=h^2[4-2(i^2+1)]\\ &=4h^2\\ &=1\\ \sin a\cos b+\cos a\sin b&=h^2i[(g^{-a}-g^a)(g^b+g^{-b})+(g^a+g^{-a})(g^{-b}-g^b)]\\ &=h^2i[2g^{-a-b}-2g^{a+b}]\\ &=hi[g^{-a-b}-g^{a+b}]\\ &=\sin(a+b)\\ \cos a\cos b-\sin a\sin b&=h^2[(g^a+g^{-a})(g^b+g^{-b})-i^2(g^{-a}-g^a)(g^{-b}-g^b)]\\ &=h^2[g^{a+b}+g^{a-b}+g^{b-a}+g^{-a-b}-i^2g^{-a-b}+i^2g^{b-a}+i^2g^{a-b}-i^2g^{a+b}]\\ &=h^2[(1-i^2)(g^{a+b}+g^{-a-b})+(1+i^2)(g^{a-b}+g^{b-a})]\\ &=h^2(1-i^2)(g^{a+b}+g^{-a-b})\\ &=h(g^{a+b}+g^{-a-b})\\ &=\cos(a+b) \end{align*} as $h(1-i^2)=h(2-(i^2+1))=2h=1$.

Thus we have such identities as: \begin{align*} \sin^2 a+\cos^2 a&=1\\ \sin(a\pm b)&=\sin a\cos b\pm\cos a\sin b\\ \sin2a&=2\sin a\cos a\\ \cos(a\pm b)&=\cos a\cos b\mp\sin a\sin b\\ \cos2a&=\cos^2a-\sin^2a=1-2\sin^2a=2\cos^2a-1\\ \end{align*}

Earlier work

The OQ cites a Wikipedia article "Trigonometry in a galois [i.e. finite] field", but unfortunately that article no longer exists. However, Wikipedia has an article on rational trigonometry, and I did locate a pertinent paper by Campello[2].

Campello and his co-authors use "GF(q)" for $\F_q$ ($q=p^r$, $p$ prime) and "G(q)" for $\F_q[i]$. They define trigonometry in the latter.

Rational trigonometry is a way of doing geometry and trigonometry in finite sets. It was developed by Norman Wildberger. Instead of distance $d$ it uses "quadrance" which corresponds to $d^2$, and instead of an angle $\theta$ it uses "spread" which corresponds to $\sin^2\theta$.

Getting sin's sign correct

A mistake which is all too easy to make is to implement $a\mapsto-\sin a$ instead of $a\mapsto\sin a$. For the sin function to be correct, it must satisfy $\sin \frac{n}4=1$ (as $\sin90\de=1$). If $F=\Z_{p}$, this can be arranged by taking $g^{n/4}$ as $i$.

If $12\mid n$, an alternative check is possible: $2 \sin \frac{n}{12}=p+1$ (as $\sin30\de=\frac12$). For example, in $Z_{11}[i]$, $\sin 10$ should be 6, not 5.

Whether the sin formula yields $\sin a$ or $-\sin a$ depends on the generator $g$ and (unless $F$ is defined by explicitly adjoining $i$) the choice of square root of $-1$ for $i$. Where $a=\frac{n}4$, $g$ is right if $g^a=i$ and wrong when $g^a=-i=i'=\overline{i}$.

Write $\i{x}{y}$ for $x+yi$. Now $(\overline{g})^a=\overline{g^a}$ so where two generators are each other's conjugates, one is right and one is wrong. $\overline{\i{x}{y}}=\i{x}{(p-y)}$. And $(g')^a=(g^a)'$, so the same is true if they are each other's reciprocals.

Some examples.

For $F=\Z_{73}$, $g=5, i=27$ and $g=11, i=46$.

For $F=Z_{11}[i]$, $\frac{n}4=\frac{p^2-1}4=30$, $\i{4}{1}, \i{5}{4}, \i{3}{9}=\overline{\i{3}{2}}, \i{7}{10}=(\i{3}{2})', \i{5}{9}=\overline{\i{5}{2}}, \i{7}{6}=(\i{5}{2})'$.

[2]: Campello de Souza, R.M. et al. Trigonometry in a Finite field and a New Hartley Transform. ISIT 16-21 August 1998, p.293.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.