- Trigonometry in Galois fields
In

mathematics , the theory ofquadratic extension s offinite field s supports analogies withtrigonometry .The main motivation to deal with a finite field trigonometry is the power of the discrete transforms, which play an important role in engineering and mathematics. Significant examples are the well-known discrete trigonometric transforms (DTT), namely the

discrete cosine transform anddiscrete sine transform , which have found many applications in the fields of digital signal andimage processing . In the real DTTs, inevitably, rounding is necessary, because the elements of its transformation matrices are derived from the calculation of sines and cosines. This is the main motivation to define the cosine transform over primefinite fields . In this case, all the calculation is done using integer arithmetic.In order to construct a finite field transform that holds some resemblance with a DTT or with a discrete transform that uses

trigonometric function s as its kernel, like thediscrete Hartley transform , it is firstly necessary to establish the equivalent of the cosine and sine functions over a finite structure.**Trigonometry over a Galois field**The set G("q") of

gaussian integer s over GF("q") plays an important role in the trigonometry over finite fields (hereafter the symbol := denotes "equal by definition").: G("q") := {"a" + "jb", "a", "b" ∈ GF("q")} "q" = "p"

^{"r"},"r" being a positive integer, "p" being an odd prime for which "j"

^{2}= −1 is aquadratic non-residue in GF("q"); it is a field isomorphic to GF("q"^{2}).Trigonometric functions over the elements of a

Galois field can be defined as follows:Let $zeta$ be an element of

multiplicative order "N" in GI("q"), "q" = p^{r}, "p" an odd prime such that "p" $equiv$3 (mod 4). The GI("q")-valued "k"-trigonometric functions of ($angle$$zeta^i$) in GI("q") (by analogy, the trigonometric functions of "k" times the "angle" of the "complex exponential" $zeta$^{i}) are defined as: $cos(anglezeta^i)=(2^\{-1\}mod\{p\})cdot(zeta^\{ik\}+zeta^\{-ik\}),$

: $sin(anglezeta^i)=(1/j)(2^\{-1\}mod\{p\})cdot(zeta^\{ik\}\; -\; zeta^\{-ik\}),$

for "i, k" = 0, 1,...,"N" − 1. We write cos

_{k}($anglezeta$^{"i"}) and sin_{k}($anglezeta$^{"i"}) as cos_{"k"}("i") and sin_{"k"}("i"), respectively. The trigonometric functions above introduced satisfy properties**P1-P12**below, in GI("p").**P1**. Unit circle: $sin\_k^2(i)+cos\_k^2(i)equiv\; 1$.**P2**. Even/Odd: i) $cos\_k(i)equiv\; cos\_k(-i)$. ii) $sin\_k(i)equiv\; -sin\_k(-i).$**P3**. Euler formula: $zeta^\{ki\}\; equiv\; cos\_k(i)+jsin\_k(i).$**P4**. Addition of arcs:i) $cos\_k(i+t)equiv\; cos\_k(i)cos\_k(t)-sin\_k(i)sin\_k(t),$

ii) $sin\_k(i+t)equiv\; sin\_k(i)cos\_k(t)+sin\_k(t)cos\_k(i).$

**P5**. Double arc:i)$cos\_k^2(i)equiv\; (2^\{-1\}mod\{p\})cdot(1+cos\_k(2i)),$

ii)$sin\_k^2(i)equiv\; (2^\{-1\}mod\{p\})cdot(1-cos\_k(2i).$

**P6**. Symmetry:i) $cos\_k(i)equiv\; cos\_i(k),$

ii)$sin\_k(i)equiv\; sin\_i(k).$

**P7**. Complementary symmetry: with $(k+t)=(i+r)=\; N$,i) $cos\_k(i)\; equiv\; cos\_r(t),$

ii) $sin\_k(i)\; equiv\; sin\_r(t).$

**P8**. Periodicity:i)$cos\_k(i+N)\; equiv\; cos\_k(i),$

ii)$sin\_k(i+N)\; equiv\; sin\_k(i).$

**P9**. Complement: with $(i+t)=\; N,$i)$cos\_k(i)\; equiv\; cos\_k(t),$

ii) $sin\_k(i)equiv\; -sin\_k(t).$

**P10**. $cos\_k(i)$ summation: $sum\_\{k=0\}^\{N-1\}\; cos\_k(i)equiv.$**P11**. $sin\_k(i)$ summation: $sum\_\{k=0\}^\{N-1\}\; sin\_k(i)equiv\; 0.$**P12**. Orthogonality:$sum\_\{k=0\}^\{N-1\}\; [cos\_k(i)sin\_k(t)]\; equiv\; 0.$**Examples**i) With ζ = 3, a primitive element of GF(7), then cos

_{"k"}("i") and sin_{"k"}("i") functions take the following values in GI(7)::::"Table I - Finite field cosine and sine functions over GI(7)."

Figure 1 illustrates the 12 roots of unity in GF(11

^{2). Clearly, G1 is isomorphic to C12, the group of proper rotations of a regular dodecagon. $zeta$=8+j6 is a group generator corresponding to a counter-clockwise rotation of 2π/12 = 30o. Symbols of the same colour indicate elements of same order, which occur in conjugate pairs.}**Polar form**Let "G"

_{"r"}and "G"_{θ}besubgroup s of the multiplicative group of the nonzero elements of GI("p"), of orders ("p" − 1)/2 and 2("p" + 1), respectively. Then all nonzero elements of GI("p") can be written in the form ζ = α·β, where α ∈ "G"_{r}and β ∈ "G"_{θ}.Considering that any element of a

cyclic group can be written as an integral power of agroup generator , it is possible to set "r" = α and ε^{θ}= β, where ε is a generator of $G\_\; heta$. The powers ε^{θ}of this element play the role of "e"^{"j"θ}over the complex field. Thus, the polar representation assumes the desired form, $zeta=r\; cdotepsilon^\; heta$, where "r" plays the role of the modulus of ζ. Therefore, it is necessary to define formally the modulus of an element in a finite field. Considering the nonzero elements of GF("p"), it is a well-known factFact|date=August 2008 that half of them arequadratic residues of "p". The other half, those that do not possess square root, are thequadratic non-residue (in the field of real numbers, the elements are divided into positive and negative numbers, which are, respectively, those that possess and do not possess a square root).The standard modulus operation (

absolute value ) in $mathbb\{R\}$ always gives a positive result.By analogy, the modulus operation in GF("p") is such that it always results in a quadratic residue of "p".

The modulus of an element $ain\; GF(p)$, where "p" = 4"k" + 3, is

:$mathcal\; |a|=\; egin\{cases\}\; a,\; ;\; extrm\{if\}a^\{(p-1)/2\}equiv\; 1\; mod\{p\},\; \backslash \; -a,\; ;\; extrm\{if\}a^\{(p-1)/2\}equiv\; -1\; mod\{p\}.\; end\{cases\}$

The modulus of an element of GF("p") is a quadratic residue of "p".

The modulus of an element a+jb $in$ GI("p"), where "p" = 4"k" + 3, is

:$mid\; a+jbmid\; =left\; |\; sqrt\{mid\; a^2+b^2\; mid\}\; ight\; |.$

In the continuum, such expression reduces to the usual norm of a complex number, since both, a

^{2}+b^{2}and the square root operation, produce only nonnegative numbers.* The group of modulus of GI("p"), denoted by G

_{r}, is the subgroup of order ("p" − 1)/2 of GI("p").

* The group of phases of GI("p"), denoted by G_{$heta$}, is the subgroup of order 2("p" + 1) of GI("p").An expression for the phase $heta$ as a function of a and b can be found by normalising the element $zeta$ (that is, calculating $zeta\; /r\; =\; epsilon^\; heta$), and then solving the

discrete logarithm problem of $zeta$/"r" in the base $epsilon$ over GF("p"). Thus, the conversion rectangular to polar form is possible.The similarity with the trigonometry over the field of real numbers is now evident: the modulus belongs to GF("p") (the modulus is a real number) and is a quadratic residue (a positive number), and the exponential component $epsilon$

^{$heta$}) has modulus one and belongs to GI("p") (e^{$j\; heta$}also has modulus one and belongs to the complex field $mathbb\{C\}$).**The "Z" plane in a Galois field**The complex "Z" plane (

Argand diagram ) in GF("p") can be constructed from the supra-unimodular set of GI("p"):* The supra-unimodular set of GI("p"), denoted G

_{s}, is the set of elements ζ = ("a" + "jb") ∈ GI("p"), such that ("a"^{2}+ "b"^{2}) $equiv$−1 (mod "p").

* The structures,*>, is a cyclic group of order 2("p" + 1), called the supra-unimodular group of GI("p"). The elements ζ = "a" + "jb" of the supra-unimodular group "G"

_{"s"}satisfy ("a"^{2}+ "b"^{2})^{2}$equiv$1 (mod "p") and all have modulus 1. "G"_{"s"}is precisely the group of phases $G\_\; heta$.* If "p" is a

Mersenne prime ("p" = 2^{"n"}− 1, "n" > 2), the elements ζ = "a" + "jb" such that "a"^{2}+ "b"^{2}$equiv$−1 (mod "p") are the generators of G_{s}.**Examples*** Let "p" = 31, a Mersenne prime, and ζ = 6 + "j"16. Then $r=|sqrt\{(|6^2+16^2|)\}|equiv|sqrt$

**Trajectories over the Galois Z plane in GF("p")**When calculating the order of a given element, the intermediate results generate a trajectory on the Galois Z plane, called the order trajectory. In particular, If $zeta$ has order "N", the trajectory goes through "N" distinct points on the Z plane, moving in a pattern that depends on "N". Specifically, the order trajectory touches on every circle of the Galois Z plane (there are ||G

_{r}|| of them), in order of increasing modulus, always returning to the unit circle. If it starts on a given radius, say R, it will visit, counter-clockwise, every radius of the form R+"k.r", where "r"=("p"^{2}-1)/"N" and "k"=0,1,2,.....,"N" − 1. Given a prime "p"$equiv$3 (mod 4), there are a (finite) number of ("p" − 1)/2 distinctcircles over the Galois Z plane GI("p"), and the number of distinct finite fieldellipse s is ("p" − 1).("p" − 3)/4.* Table V lists some elements ζ ∈ GI(7) and their orders "N". Figures 3-5 show the order trajectories generated by ζ.

:: "Table V - Some elements and their orders in GI(7)."

**References*** [1] R. M. Campello de Souza, H. M. de Oliveira and A. N. Kauffman, "Trigonometry in Finite Fields and a New Hartley Transform," "Proceedings of the 1998 International Symposium on Information Theory", p. 293, Cambridge, MA, Aug. 1998.

* [2] M. M. Campello de Souza, H. M. de Oliveira, R. M. Campello de Souza and M. M. Vasconcelos, "The Discrete Cosine Transform over Prime Finite Fields," "Lecture Notes in Computer Science", LNCS 3124, pp. 482–487, Springer Verlag, 2004.

* [3] R. M. Campello de Souza, H. M. de Oliveira and D. Silva, "The Z Transform over Finite Fields," "International Telecommunications Symposium", Natal, Brazil, 2002.

* [4] http://www2.ee.ufpe.br/codec/FFtools.htm

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Trigonometry**— Trig redirects here. For other uses, see Trig (disambiguation). The Canadarm2 robotic manipulator on the International Space Station is operated by controlling the angles of its joints. Calculating the final position of the astronaut at the end… … Wikipedia**List of trigonometry topics**— This is a list of trigonometry topics, by Wikipedia page.*Angle *Angle excess *Brahmagupta interpolation formula *Chebyshev polynomials *Conway triangle notation *De Moivre s formula *Dirichlet kernel *Euler s formula *Exact trigonometric… … Wikipedia**Finite field**— In abstract algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains only finitely many elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and… … Wikipedia**Trigonometric functions**— Cosine redirects here. For the similarity measure, see Cosine similarity. Trigonometry History Usage Functions Generalized Inverse functions … Wikipedia**List of mathematics articles (T)**— NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie … Wikipedia**mathematics**— /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… … Universalium**Number theory**— A Lehmer sieve an analog computer once used for finding primes and solving simple diophantine equations. Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers (the… … Wikipedia**List of important publications in mathematics**— One of the oldest surviving fragments of Euclid s Elements, found at Oxyrhynchus and dated to circa AD 100. The diagram accompanies Book II, Proposition 5.[1] This is a list of important publications in mathematics, organized by field. Some… … Wikipedia**History of mathematics**— A proof from Euclid s Elements, widely considered the most influential textbook of all time.[1] … Wikipedia**Mathematics**— Maths and Math redirect here. For other uses see Mathematics (disambiguation) and Math (disambiguation). Euclid, Greek mathematician, 3r … Wikipedia