International
Tables for
Crystallography
Volume B
Reciprocal space
Edited by U. Shmueli

International Tables for Crystallography (2010). Vol. B, ch. 1.3, pp. 55-56   | 1 | 2 |

Section 1.3.3.2.3.1. N an odd prime

G. Bricognea

aGlobal Phasing Ltd, Sheraton House, Suites 14–16, Castle Park, Cambridge CB3 0AX, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France

1.3.3.2.3.1. N an odd prime

| top | pdf |

The ring [{\bb Z} / p {\bb Z} = \{0,1,2,\ldots,p - 1\}] has the property that its [p - 1] nonzero elements, called units, form a multiplicative group [U(p)]. In particular, all units [r \in U(p)] have a unique multiplicative inverse in [{\bb Z} / p {\bb Z}], i.e. a unit [s \in U(p)] such that [rs \equiv 1\hbox { mod } p]. This endows [{\bb Z} / p {\bb Z}] with the structure of a finite field.

Furthermore, [U(p)] is a cyclic group, i.e. consists of the successive powers [g^{m}\hbox{ mod } p] of a generator g called a primitive root mod p (such a g may not be unique, but it always exists). For instance, for [p = 7], [U(7) = \{1,2,3,4,5,6\}] is generated by [g = 3], whose successive powers mod 7 are:[g^{0} = 1, \quad g^{1} = 3, \quad g^{2} = 2, \quad g^{3} = 6, \quad g^{4} = 4, \quad g^{5} = 5][see Apostol (1976[link]), Chapter 10].

The basis of Rader's algorithm is to bring to light a hidden regularity in the matrix [F(p)] by permuting the basis vectors [{\bf u}_{k}] and [{\bf v}_{k^{*}}] of [L({\bb Z} / p {\bb Z})] as follows:[\eqalign{{\bf u}'_{0} &= {\bf u}_{0} \cr {\bf u}'_{m} &= {\bf u}_{k} {\hbox to 12pt{}}\hbox{with } k = g^{m}, {\hbox to 15pt{}} m = 1, \ldots, p - 1\hbox{\semi} \cr {\bf v}'_{0} &= {\bf v}_{0} \cr {\bf v}'_{m^{*}} &= {\bf v}_{k^{*}} \quad \hbox{with } k^{*} = g^{m^{*}}, \quad m^{*} = 1, \ldots, p - 1\hbox{\semi}}]where g is a primitive root mod p.

With respect to these new bases, the matrix representing [\bar{F}(p)] will have the following elements:[\eqalign{\hbox{element } (0,0) &= 1 \cr \hbox{element } (0, m + 1) &= 1 \quad \hbox{for all } m = 0, \ldots p - 2, \cr \hbox{element } (m^{*} + 1,0) &= 1 \quad \hbox{for all } m^{*} = 0, \ldots, p - 2, \cr \hbox{element } (m^{*} + 1, m + 1) &= e \left({k^{*}k \over p}\right) \cr &= e(g^{(m^{*} + m)/p}) \cr &\qquad \quad \hbox{for all } m^{*} = 0, \ldots, p - 2.}]Thus the `core' [\bar{C}(p)] of matrix [\bar{F}(p)], of size [(p - 1) \times (p - 1)], formed by the elements with two nonzero indices, has a so-called skew-circulant structure because element [(m^{*}, m)] depends only on [m^{*} + m]. Simplification may now occur because multiplication by [\bar{C}(p)] is closely related to a cyclic convolution. Introducing the notation [C(m) = e(g^{m/p})] we may write the relation [{\bf Y}^{*} = \bar{F}(p){\bf Y}] in the permuted bases as[\eqalign{Y^{*} (0) &= {\textstyle\sum\limits_{k}} Y(k) \cr Y^{*} (m^{*} + 1) &= Y(0) + {\textstyle\sum\limits_{m = 0}^{p - 2}} C(m^{*} + m) Y(m + 1) \cr &= Y(0) + {\textstyle\sum\limits_{m = 0}^{p - 2}} C(m^{*} - m) Z(m) \cr &= Y(0) + ({\bf C} * {\bf Z}) (m^{*}), \quad m^{*} = 0, \ldots, p - 2,}]where Z is defined by [Z(m) = Y(p - m - 2)], [m = 0, \ldots, p - 2].

Thus [{\bf Y}^{*}] may be obtained by cyclic convolution of C and Z, which may for instance be calculated by[{\bf C} * {\bf Z} = F(p - 1) [\bar{F}(p - 1) [{\bf C}] \times \bar{F} (p - 1) [{\bf Z}]],]where × denotes the component-wise multiplication of vectors. Since p is odd, [p - 1] is always divisible by 2 and may even be highly composite. In that case, factoring [\bar{F} (p - 1)] by means of the Cooley–Tukey or Good methods leads to an algorithm of complexity p log p rather than [p^{2}] for [\bar{F}(p)]. An added bonus is that, because [g^{(p-1) / 2} = -1], the elements of [\bar{F} (p - 1) [{\bf C}]] can be shown to be either purely real or purely imaginary, which halves the number of real multiplications involved.

References

Apostol, T. M. (1976). Introduction to Analytic Number Theory. New York: Springer-Verlag.








































to end of page
to top of page