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