## Preprints (rote Reihe) des Fachbereich Mathematik

216

We present a generalization of Proth's theorem for testing certain large integers for primality. The use of Gauß sums leads to a much simpler approach to these primality criteria as compared to the earlier tests. The running time of the algorithms is bounded by a polynomial in the length of the input string. The applicability of our algorithms is linked to certain diophantine approximations of \(l\)-adic roots of unity.

229

223

Let \(a_1, i:=1,\dots,m\), be an i.i.d. sequence taking values in \(\mathbb{R}^n\), whose convex hull is interpreted as a stochastic polyhedron \(P\). For a special class of random variables, which decompose additively relative to their boundary simplices, eg. the volume of \(P\), simple integral representations of its first two moments are given in case of rotationally symmetric distributions in order to facilitate estimations of variances or to quantify large deviations from the mean.

219

A Remark on Primes of the Form \(2^{3n}a + 2^{2n}b+2^nc+1\). Necessary and sufficient conditions for the numbers in the title to be prime are given. The tests are well suited for practical purposes.

220

Hyperidentities
(1992)

The concept of a free algebra plays an essential role in universal algebra and in computer science. Manipulation of terms, calculations and the derivation of identities are performed in free algebras. Word problems, normal forms, system of reductions, unification and finite bases of identities are topics in algebra and logic as well as in computer science. A very fruitful point of view is to consider structural properties of free algebras. A.I. Malcev initiated a thorough research of the congruences of free algebras. Henceforth congruence permutable, congruence distributive and congruence modular varieties are
intensively studied. A lot of Malcev type theorems are connected to the congruence lattice of free algebras. Here we consider free algebras as semigroups of compositions of terms and more specific as clones of terms. The properties of these semigroups and clones are adequately described by hyperidentities. Naturally a lot of theorems of "semigroup" or "clone" type can be derived. This topic of research is still in its beginning and therefore a lot öf concepts and results cannot be presented in a final and polished form. Furthermore a lot of problems and questions are open which are of importance for the further development of the theory of hyperidentities.

232

We show that the different module structures of GF(\(q^m\)) arising from the intermediate fields of GF(\(q^m\))and GF(q) can be studied simultaneously with the help of some basic properties of cyclotomic polynomials. We use this ideas to give a detailed and constructive proof of the most difficult part of a Theorem of D. Blessenohl and K. Johnsen (1986), i.e., the existence of elements v in GF(\(q^m\)) over GF(q) which generate normal bases over any intermediate field of GF(\(q^m\)) and GF(q), provided that m is a prime power. Such elements are called completely free in GF(\(q^m\)) over GF(q). We develop a recursive formula for the number of completely free elements in GF(\(q^m\)) over GF(q) in the case where m is a prime power. Some of the results can be generalized to finite cyclic Galois extensions
over arbitrary fields.