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 has the property that its nonzero elements, called units, form a multiplicative group . In particular, all units have a unique multiplicative inverse in , i.e. a unit such that . This endows with the structure of a finite field.

Furthermore, is a cyclic group, i.e. consists of the successive powers of a generator g called a primitive root mod p (such a g may not be unique, but it always exists). For instance, for , is generated by , whose successive powers mod 7 are: [see Apostol (1976 ), Chapter 10].

The basis of Rader's algorithm is to bring to light a hidden regularity in the matrix by permuting the basis vectors and of as follows: where g is a primitive root mod p.

With respect to these new bases, the matrix representing will have the following elements: Thus the `core' of matrix , of size , formed by the elements with two nonzero indices, has a so-called skew-circulant structure because element depends only on . Simplification may now occur because multiplication by is closely related to a cyclic convolution. Introducing the notation we may write the relation in the permuted bases as where Z is defined by , .

Thus may be obtained by cyclic convolution of C and Z, which may for instance be calculated by where × denotes the component-wise multiplication of vectors. Since p is odd, is always divisible by 2 and may even be highly composite. In that case, factoring by means of the Cooley–Tukey or Good methods leads to an algorithm of complexity p log p rather than for . An added bonus is that, because , the elements of 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.