From: Bill Dubuque Date: Tue, 10 Sep 1996 11:05:54 -0400 Subject: GFs, Universal CA, Constructivism, Max Zima Date: Sun, 8 Sep 1996 21:41:51 +0600 From: mcintosh@servidor.dgsca.unam.mx (McIntosh Harold V.-UAP) ... As a serious question - can we expect some real GF arithmetic from our symbol manipulation programs? ... Galois Field computation capabilities are fairly routine for most computer algebra systems, e.g. such are used to factor univariate polynomials in the classical Zassenhaus-Berlekamp algorithm. However, "classical" computer algebra systems like Macsyma, Maple and Mma typically don't easily expose these capabilities at the user level since the languages employed aren't expressive enough to permit construction and computations in diverse algebraic structures. This will probably change shortly, especially considering the widespread applications of finite fields, e.g. to combinatorics, cryptology, algebraic coding theory, pseudorandom number generation and electrical engineering (spread-spectrum communications and DSP). An excellent introduction to finite fields can be found in the books by Lidl and Niederreiter, and that of Shparlinski, see the Math Reviews appended below. Of course there has been work on computer algebra systems that allow you to compute over a wide spectrum of algebraic structures. Not surprisingly, these systems are founded upon ideas borrowed from universal algebra and category theory, e.g. see Axiom. However, even Axiom leaves much to be desired, since many of the ideas incorporated are just at the syntactic sugar level, leaving unresolved some of the deeper semantic issues. This should soon change now that category theory is spreading like wildfire throughout the theoretical computer science community. In the past computer algebra has been stranded starving in the deep abyss separating mathematics and computer science. However, thanks to the recent phenomenal growth of category and topos theory, there is now a revitalization of the constructivist viewpoint and this should breathe new life into computer algebra. ... Having phoneticized this latest posting about ?scottish? mathematicians, i conclude that some phanticizing is going on. ... The original post must surely have been a troll (unless, as recent reports claim, the general intellectual level of the Internet has really sunk much closer to the general level of the population; how else could one explain such a gullible user falling for the name of Maplev as the worlds greatest mathematician!). In any case, my Zilly followup did have some zerious undertonez, especially regarding the blatant commercialism of computer algebra by Wolfram Research via Mma. All of the URLs and references in my Max Zima message are real (yes there really is a Russian mathematician named E.V. Zima who coauthored said article on computer algebra), and I urge all those uncritical of Mma to read Fateman's critical review of Mma. Not to mention the questionable ethical practices of WRI, e.g. refusing to reveal literature references for implemented algorithms (luckily, the major competitors, Macsyma and Maple, do not stoop to such a disgustingly low level). It is truly a shame when such commercialism inhibits the advancement of science. Hopefully, due to the constructive revitalization mentioned above, computer algebra will eventually become a better accepted field in academia and its further development will not be stifled via banishment to the commercial arena. -Bill ------------------------------------------------------------------------------ 95f:11098 11Txx 94A60 94B27 Lidl, Rudolf (5-TAS); Niederreiter, Harald (A-OAW) Introduction to finite fields and their applications. Revision of the 1986 first edition. Cambridge University Press, Cambridge, 1994. xii+416 pp. $44.95. ISBN 0-521-46094-8 ------------------------------------------------------------------------------ The first edition has been reviewed [MR 88c:11073]. >From the preface: "The subject of finite fields has undergone a spectacular development in the last 10 years. Great strides have been made, especially in the computational and algorithmic aspects of finite fields which are important in the rapidly developing areas of computer algebra and symbolic computation. The numerous applications of finite fields to combinatorics, cryptology, algebraic coding theory, pseudorandom number generation and electrical engineering, to name but a few, have provided a steady impetus for further research. Thus, the subject grows inexorably. Nevertheless, we hope that this book will continue to serve its purpose as an introduction for students, since it is devoted mainly to those parts that have a certain quality of timelessness, namely the classical theory and the standard applications of finite fields. "This book has been out of print for some time, but because of the continuing demand we want to make it available again. We have taken this opportunity to revise the book slightly. Historical and bibliographical notes have been added to each chapter, the bibliography has become more detailed, and the misprints in the original edition have of course been corrected." ------------------------------------------------------------------------------ 94j:11122 11Txx 11Y16 68Q25 94B05 Shparlinski, Igor E. (5-MCQR) Computational and algorithmic problems in finite fields. Mathematics and its Applications (Soviet Series), 88. Kluwer Academic Publishers Group, Dordrecht, 1992. xii+240pp. $118.00. ISBN 0-7923-2057-3 ------------------------------------------------------------------------------ This book conceals a wealth of mathematics behind its unassuming title. It is concerned not so much with the existence of various objects over finite fields, but with their implementation, in principle at least, by means of algorithms (deterministic and probabilistic) and with the complexity of the latter. In fact, the main tools are those of number theory and algebraic geometry (often at a deep level) and the results, on the whole, are theoretical in that the estimated bounds tend to be suggestive rather than realistic and often involve undetermined constants whose effect on calculations of a practical size are rather unclear. The book is packed with fascinating results (collated from various sources) and therefore the following list of chapter headings is but a bare indication of its scope: 1. Polynomial factorization; 2. Finding irreducible and primitive polynomials; 3. The distribution of irreducible and primitive polynomials; 4. Bases and computations in finite fields; 5. Coding theory and algebraic curves; 6. Elliptic curves; 7. Recurrent sequences in finite fields and cyclic linear codes; 8. Finite fields and discrete mathematics; 9. Congruences; 10. Some related problems. \{In fact, much of the material in the last two chapters goes beyond the study of finite fields themselves\}. The style of the book is essentially that of a survey of recent literature, which is massive (there are over 1300 items referenced, mostly from the last 10 years) and growing (an addendum written while the book was in press contains 300 more); a large number of papers from the former Soviet Union are included. Many of the ideas and results are merely described but more details of certain aspects that had not appeared previously are given (though the proofs, even of these, are often rather sketchy). Unfortunately, as the reader will quickly discover, there are a number of slips and misprints and even the reference data is not always reliable. Thus it can be viewed as a valuable handbook to the literature but corroboration should be sought from the original source where possible. Since a book of this nature in a rapidly developing field is bound to require supplementation before long in any case, it is a pity some extra months were not spent at the editing stage for checking and polishing. Nevertheless, its coverage is amazing, and it contains much to stimulate further research including a list of unsolved problems. Reviewed by S. D. Cohen ------------------------------------------------------------------------------ 88c:11073 11Txx Lidl, Rudolf (5-TAS); Niederreiter, Harald (A-OAW) Introduction to finite fields and their applications. Cambridge University Press, Cambridge-New York, 1986. viii+407 pp. $29.95. ISBN 0-521-30706-6 ------------------------------------------------------------------------------ This book is a textbook version of the book Finite fields which appeared in 1983 and which was given an extended review [Addison-Wesley, Reading, Mass., 1983; MR 86c:11106]. In the present review we therefore concentrate on the differences between the two. The size has been reduced from 755 to 407 pages by omitting the 160-page bibliography, the notes to each chapter and most of the material on exponential sums, equations, and permutation polynomials. On the other hand, the part about applications has been extended by a new chapter on cryptography and new sections on pseudorandom sequences and Goppa codes. The new parts have the same high standard of presentation as the rest of the book. The book appears to be well suited as a textbook with its clear presentation, with many examples, and a good supply of exercises. Reviewed by Torleiv Klove Cited in: 96a:1114595f:1109888m:11109 ------------------------------------------------------------------------------ 86c:11106 11Txx 05B05 94Bxx Lidl, Rudolf (5-TAS); Niederreiter, Harald (A-OAW) Finite fields. With a foreword by P. M. Cohn. Encyclopedia of Mathematics and its Applications, 20. Addison-Wesley Publishing Co., Reading, Mass., 1983. xx+755 pp. $75.95. ISBN 0-201-13519-1 ------------------------------------------------------------------------------ Cohn's foreword begins: "Most modern algebra texts devote a few pages (but no more) to finite fields". Indeed, sections of under 40 pages in books by A. A. Albert [Fundamental concepts of higher algebra, Univ. Chicago Press, Chicago, Ill., 1958; MR 20 #5190] and E. R. Berlekamp [Algebraic coding theory, McGraw-Hill, New York, 1968; MR 38 #6873] are as full as any. Yet there actually exists a large body of theory at various levels, from several viewpoints and with all kinds of contemporary applications. Hence this first-ever encyclopaedic treatment of finite fields is a timely enterprise. A few preliminary remarks are in order. The expressed editorial policy of this series is the presentation of the factual body of mathematics with these priorities: clarity of exposition, accessibility to the nonspecialist and a thorough bibliography. In achieving these aims in this work, the authors progress, not so much through stages of logical complexity and refinement with motivation of each fresh development, but by presenting, in as detailed and general form as possible using only basic linear and abstract algebra, a coherent, comprehensible account of present knowledge, drawing on and combining the researches of both theorists and applied workers in various areas. As far as the main text itself is concerned, a distinctly algebraic stance is adopted; finite fields and functions over them are viewed as simple algebraic objects and not arithmetically (at various possible levels of sophistication) or in algebraic-geometrical terms (function fields). However, each of the ten chapters is followed by extensive notes which must be regarded as a vital part of the work and indicate sources, sketch the historical perspective and provide a full review of the relevant literature; in particular they colour in a rich background of results and applications, low-brow and profound, number-theoretical and otherwise. There are also a large number of exercises (apparently straightforward, on the whole) which illustrate the theory and indicate many developments of it. We summarize the contents by chapter titles with brief comments. 1. "Algebraic foundations." Basic abstract algebra, especially rings and fields. 2. "Structure of finite fields." Including linear structure (bases, normal bases), primitive elements (roots), representations as splitting fields and as matrices, Wedderburn's theorem. 3. "Polynomials over finite fields." (Fundamental, because every function over a finite field can be represented by a polynomial.) The order of a polynomial, primitive polynomials, construction of irreducible polynomials, special polynomials (linearized, binomials and trinomials). 4. "Factorization of polynomials." A harmonized account of practical algorithms over both small and large fields pioneered by Berlekamp, McEliece and Zassenhaus. The many results of a more theoretical nature are summarized in the notes. 5. "Exponential sums." An excellent discussion of character sums including those of Gauss, Jacobi and Kloosterman in a general context, with a nice use of simple $L$-functions as a tool. With material anticipated from Chapter 6, the highlight is lucid, elementary and complete proofs of Weil's theorems "$\vert \sum\chi(f(x))\vert \le(n-1) q\sp {1/2}$" for polynomial character sums, $\chi$ being an additive or multiplicative character. 6. "Equations over finite fields." General results on numbers of solutions, quadratic and diagonal equations. As a climax the elementary method of Stepanov as formalised by Schmidt (possibly an advance on Schmidt's own account) as far as the number of solutions of $y\sp m=f(x)$ (in full generality) and ${\rm Tr}(f(x))=c$ (with the restriction that $\deg F$ is not divisible by the characteristic). 7. "Permutation polynomials." Criteria for and classes of such polynomials in one or more indeterminates, groups of polynomials. 8. "Linear recurring sequences." Such sequences have been defined over many rings but here we have at some length their theory restricted to finite fields (associated primarily with Zierler and of wide application) after an introductory section on their physical implementation. 9. "Applications of finite fields." A mainly descriptive introduction to applications in coding theory, projective planes and geometries (mostly Desarguesian) and combinatorics (block designs, difference sets, etc.)---all these being inter-related. Finally, linear modular systems, these being the model for switching systems and a large number of physical devices. 10. "Tables." Useful tables of indices (logarithms) and exponentials (to a specific primitive element as base) for small finite fields. Extensive lists of irreducible polynomials, including at least one primitive polynomial for each field of order $<10\sp 9$ and characteristic $<50$. The Bibliography, occupying 160 pages, is wide-ranging in its scope and reveals many items likely to be unfamiliar, appearing in, for example, old, inaccessible, Russian or engineering journals. Much more well known will be the 140 contributions, on a host of themes, associated with the name of L. Carlitz . Finally, there is a useful Author index in addition to a list of symbols and the normal Subject index. While, at places, the discussion is somewhat expansive, generally the authors have organized their material in a most painstaking and efficient manner with well-selected examples. This care has beneficial consequences for the whole, too many to enumerate here. Consistent with this is an apparent (and commendable) absence of errors and misprints. The limiting nature of the tools available is perhaps sometimes a handicap. (We point to Section 4 of Chapter 7 on exceptional polynomials as a small example.) The selection and balance of the subject matter itself is satisfactory although, of course, detailed choice is a matter of taste. For example, it may be that the chapter on linear sequences is too long while some of the other applications and the links between them could have been explored further and still other topics (cryptography?) introduced. The bibliography is remarkably full as regards the basic theory of finite fields. Naturally, in applications in which it might be said that the occurrence of finite fields is merely incidental (such as matrix groups) only introductory references are provided, but clearly the authors have sought to provide as many references as is practicable in which finite field properties are employed in a distinctive way. (The reviewer is aware of a few more such candidates, for example, in function-field theory, non-Desarguesian geometry and coding theory.) All in all, the authors have performed a truly valuable service in the manner in which they have digested and classified the literature for us. Undoubtedly, this volume (though expensive) must become the handbook for finite fields. It should prove to be time- and energy-saving for the nonspecialist to consult as the need arises and could also be the starting point for the theorist to unify and develop areas of which he was perhaps previously unaware. Reviewed by S. D. Cohen Cited in: 96f:11099 95j:1200194d:11097 92j:11019 91h:94022 91g:11146 91e:11034 90m:11031 90i:12004 89m:1111789h:11079b 89e:11077 89e:11076 88h:11091 88e:11121 88c:11073 88b:11086 87g:13007