Algorithms and Computation in Mathematics – serie

This book is divided into two parts, one theoretical and one focusing on applications, and offers a complete description of the Canonical Gröbner Cover, the most accurate algebraic method for discussing parametric polynomial systems. It also includes applications to the Automatic Deduction of Geometric Theorems, Loci Computation and Envelopes. The theoretical part is a self-contained exposition on the theory of Parametric Gröbner Systems and Bases. It begins with Weispfenning’s introduction of Comprehensive Gröbner Systems (CGS) in 1992, and provides a complete description of the Gröbner Cover (GC), which includes a canonical discussion of a set of parametric polynomial equations developed by Michael Wibmer and the author.  In turn, the application part selects three problems for which the Gröbner Cover offers valuable new perspectives. The automatic deduction of geometric theorems (ADGT) becomes fully automatic and straightforward using GC, representing a major improvement on all previous methods. In terms of loci and envelope computation, GC makes it possible to introduce a taxonomy of the components and automatically compute it. The book also generalizes the definition of the envelope of a family of hypersurfaces, and provides algorithms for its computation, as well as for discussing how to determine the real envelope. All the algorithms described here have also been included in the software library “grobcov.lib” implemented in Singular by the author, and serve as a User Manual for it.

This edited volume presents a fascinating collection of lecture notes focusing on differential equations from two viewpoints: formal calculus (through the theory of Gröbner bases) and geometry (via quiver theory). Gröbner bases serve as effective models for computation in algebras of various types. Although the theory of Gröbner bases was developed in the second half of the 20th century, many works on computational methods in algebra were published well before the introduction of the modern algebraic language. Since then, new algorithms have been developed and the theory itself has greatly expanded. In comparison, diagrammatic methods in representation theory are relatively new, with the quiver varieties only being introduced – with big impact – in the 1990s.Divided into two parts, the book first discusses the theory of Gröbner bases in their commutative and noncommutative contexts, with a focus on algorithmic aspects and applications of Gröbner bases to analysison systems of partial differential equations, effective analysis on rings of differential operators, and homological algebra. It then introduces representations of quivers, quiver varieties and their applications to the moduli spaces of meromorphic connections on the complex projective line.While no particular reader background is assumed, the book is intended for graduate students in mathematics, engineering and related fields, as well as researchers and scholars.

This edited volume presents a fascinating collection of lecture notes focusing on differential equations from two viewpoints: formal calculus (through the theory of Gröbner bases) and geometry (via quiver theory). Gröbner bases serve as effective models for computation in algebras of various types. Although the theory of Gröbner bases was developed in the second half of the 20th century, many works on computational methods in algebra were published well before the introduction of the modern algebraic language. Since then, new algorithms have been developed and the theory itself has greatly expanded. In comparison, diagrammatic methods in representation theory are relatively new, with the quiver varieties only being introduced – with big impact – in the 1990s.Divided into two parts, the book first discusses the theory of Gröbner bases in their commutative and noncommutative contexts, with a focus on algorithmic aspects and applications of Gröbner bases to analysison systems of partial differential equations, effective analysis on rings of differential operators, and homological algebra. It then introduces representations of quivers, quiver varieties and their applications to the moduli spaces of meromorphic connections on the complex projective line.While no particular reader background is assumed, the book is intended for graduate students in mathematics, engineering and related fields, as well as researchers and scholars.

This monograph provides a self-contained presentation of the foundations of finite fields, including a detailed treatment of their algebraic closures. It also covers important advanced topics which are not yet found in textbooks: the primitive normal basis theorem, the existence of primitive elements in affine hyperplanes, and the Niederreiter method for factoring polynomials over finite fields.We give streamlined and/or clearer proofs for many fundamental results and treat some classical material in an innovative manner. In particular, we emphasize the interplay between arithmetical and structural results, and we introduce Berlekamp algebras in a novel way which provides a deeper understanding of Berlekamp's celebrated factorization algorithm.The book provides a thorough grounding in finite field theory for graduate students and researchers in mathematics. In view of its emphasis on applicable and computational aspects, it is also useful for readers working in information and communication engineering, for instance, in signal processing, coding theory, cryptography or computer science.

Defined as solutions of linear differential or difference equations with polynomial coefficients, D-finite functions play an important role in various areas of mathematics. This book is a comprehensive introduction to the theory of these functions with a special emphasis on computer algebra algorithms for computing with them: algorithms for detecting relations from given data, for evaluating D-finite functions, for executing closure properties, for obtaining various kinds of “explicit” expressions, for factoring operators, and for definite and indefinite symbolic summation and integration are explained in detail.The book comes “with batteries included” in the sense that it requires no background in computer algebra as the relevant facts from this area are summarized in the beginning. This makes the book accessible to a wide range of readers, from mathematics students who plan to work themselves on D-finite functions to researchers who want to apply the theory to their own work. Hundreds of exercises invite the reader to apply the techniques in the book and explore further aspects of the theory on their own. Solutions to all exercises are given in the appendix.When algorithms for D-finite functions came up in the early 1990s, computer proofs were met with a certain skepticism. Fortunately, these times are over and computer algebra has become a standard tool for many mathematicians. Yet, this powerful machinery is still not as widely known as it deserves. This book helps to spread the word that certain tasks can be safely delegated to a computer algebra system, and also what the limitations of these techniques are.

Defined as solutions of linear differential or difference equations with polynomial coefficients, D-finite functions play an important role in various areas of mathematics. This book is a comprehensive introduction to the theory of these functions with a special emphasis on computer algebra algorithms for computing with them: algorithms for detecting relations from given data, for evaluating D-finite functions, for executing closure properties, for obtaining various kinds of “explicit” expressions, for factoring operators, and for definite and indefinite symbolic summation and integration are explained in detail.The book comes “with batteries included” in the sense that it requires no background in computer algebra as the relevant facts from this area are summarized in the beginning. This makes the book accessible to a wide range of readers, from mathematics students who plan to work themselves on D-finite functions to researchers who want to apply the theory to their own work. Hundreds of exercises invite the reader to apply the techniques in the book and explore further aspects of the theory on their own. Solutions to all exercises are given in the appendix.When algorithms for D-finite functions came up in the early 1990s, computer proofs were met with a certain skepticism. Fortunately, these times are over and computer algebra has become a standard tool for many mathematicians. Yet, this powerful machinery is still not as widely known as it deserves. This book helps to spread the word that certain tasks can be safely delegated to a computer algebra system, and also what the limitations of these techniques are.

Beginning with its origins in the pioneering work of W.T. Tutte in 1947, this monograph systematically traces through some of the impressive developments in matching theory. A graph is matchable if it has a perfect matching. A matching covered graph is a connected graph on at least two vertices in which each edge is covered by some perfect matching. The theory of matching covered graphs, though of relatively recent vintage, has an array of interesting results with elegant proofs, several surprising applications and challenging unsolved problems. The aim of this book is to present the material in a well-organized manner with plenty of examples and illustrations so as to make it accessible to undergraduates, and also to unify the existing theory and point out new avenues to explore so as to make it attractive to graduate students.

Beginning with its origins in the pioneering work of W.T. Tutte in 1947, this monograph systematically traces through some of the impressive developments in matching theory. A graph is matchable if it has a perfect matching. A matching covered graph is a connected graph on at least two vertices in which each edge is covered by some perfect matching. The theory of matching covered graphs, though of relatively recent vintage, has an array of interesting results with elegant proofs, several surprising applications and challenging unsolved problems. The aim of this book is to present the material in a well-organized manner with plenty of examples and illustrations so as to make it accessible to undergraduates, and also to unify the existing theory and point out new avenues to explore so as to make it attractive to graduate students.

This book presents version 1.0 of the new Computer Algebra System OSCAR.Written in Julia, OSCAR builds on and vastly extends four cornerstone systems:ANTIC for number theory, GAP for group and representation theory,  polymake for polyhedral and tropical geometry, and  Singular for commutative algebra and algebraic geometry.It offers powerful computational tools that transcend the boundaries of the individual disciplines involved.It is freely available, open source software. The book is an invitation to use OSCAR.  With discussions of theoretical and algorithmic aspects included, it offers a multitude of explicit code snippets.  These are valuable for interested researchers from graduate students through established experts.

This book presents version 1.0 of the new Computer Algebra System OSCAR.Written in Julia, OSCAR builds on and vastly extends four cornerstone systems:ANTIC for number theory, GAP for group and representation theory,  polymake for polyhedral and tropical geometry, and  Singular for commutative algebra and algebraic geometry.It offers powerful computational tools that transcend the boundaries of the individual disciplines involved.It is freely available, open source software. The book is an invitation to use OSCAR.  With discussions of theoretical and algorithmic aspects included, it offers a multitude of explicit code snippets.  These are valuable for interested researchers from graduate students through established experts.

This text presents a comprehensive and unified treatment of nonlinear filtering theory, with a strong emphasis on its mathematical underpinnings. It is tailored to meet the needs of a diverse readership, including mathematically inclined engineers and scientists at both graduate and post-graduate levels. What sets this book apart from other treatments of the topic is twofold. Firstly, it offers a complete treatment of filtering theory, providing readers with a thorough understanding of the subject. Secondly, it introduces updated methodologies and applications that are crucial in today’s landscape. These include finite-dimensional filters, the Yau-Yau algorithm, direct methods, and the integration of deep learning with filtering problems. The book will be an invaluable resource for researchers and practitioners for years to come.With a rich historical backdrop dating back to Gauss and Wiener, the exposition delves into the fundamental principles underpinning the estimation of stochastic processes amidst noisy observations—a critical tool in various applied domains such as aircraft navigation, solar mapping, and orbit determination, to name just a few. Substantive exercises and examples given in each chapter provide the reader with opportunities to appreciate applications and ample ways to test their understanding of the topics covered. An especially nice feature for those studying the subject independent of a traditional course setting is the inclusion of solutions to exercises at the end of the book.The book is structured into three cohesive parts, each designed to build the reader's understanding of nonlinear filtering theory.  In the first part, foundational concepts from probability theory, stochastic processes, stochastic differential equations, and optimization are introduced, providing readers with the necessary mathematical background. The second part delves into theoretical aspects of filtering theory, covering topics such as the stochastic partial differential equation governing the posterior density function of the state, and the estimation algebra theory of systems with finite-dimensional filters. Moving forward, the third part of the book explores numerical algorithms for solving filtering problems, including the Yau-Yau algorithm, direct methods, classical filtering algorithms like the particle filter, and the intersection of filtering theory with deep learning.

This text presents a comprehensive and unified treatment of nonlinear filtering theory, with a strong emphasis on its mathematical underpinnings. It is tailored to meet the needs of a diverse readership, including mathematically inclined engineers and scientists at both graduate and post-graduate levels. What sets this book apart from other treatments of the topic is twofold. Firstly, it offers a complete treatment of filtering theory, providing readers with a thorough understanding of the subject. Secondly, it introduces updated methodologies and applications that are crucial in today’s landscape. These include finite-dimensional filters, the Yau-Yau algorithm, direct methods, and the integration of deep learning with filtering problems. The book will be an invaluable resource for researchers and practitioners for years to come.With a rich historical backdrop dating back to Gauss and Wiener, the exposition delves into the fundamental principles underpinning the estimation of stochastic processes amidst noisy observations—a critical tool in various applied domains such as aircraft navigation, solar mapping, and orbit determination, to name just a few. Substantive exercises and examples given in each chapter provide the reader with opportunities to appreciate applications and ample ways to test their understanding of the topics covered. An especially nice feature for those studying the subject independent of a traditional course setting is the inclusion of solutions to exercises at the end of the book.The book is structured into three cohesive parts, each designed to build the reader's understanding of nonlinear filtering theory.  In the first part, foundational concepts from probability theory, stochastic processes, stochastic differential equations, and optimization are introduced, providing readers with the necessary mathematical background. The second part delves into theoretical aspects of filtering theory, covering topics such as the stochastic partial differential equation governing the posterior density function of the state, and the estimation algebra theory of systems with finite-dimensional filters. Moving forward, the third part of the book explores numerical algorithms for solving filtering problems, including the Yau-Yau algorithm, direct methods, classical filtering algorithms like the particle filter, and the intersection of filtering theory with deep learning.

Symbolic asymptotics has recently undergone considerable theoretical development, especially in areas where power series are no longer an appropriate tool. Implementation is beginning to follow.The present book, written by one of the leading specialists in the area, is currently the only one to treat this part of symbolic asymptotics. It contains a good deal of interesting material in a new, developing field of mathematics at the intersection of algebra, analysis and computing, presented in a lively and readable way. The associated areas of zero equivalence and Hardy fields are also covered.The book is intended to be accessible to anyone with a good general background in mathematics, but it nonetheless gets right to the cutting edge of active research. Some results appear here for the first time, while others have hitherto only been given in preprints. Due to its clear presentation, this book is interesting for a broad audience of mathematicians and theoretical computer scientists.

From the reviews: "... Many parts of the book can be read by anyone with a basic abstract algebra course... it was one of the author's intentions to equip students who are interested in computational problems with the necessary algebraic background in pure mathematics and to encourage them to do further research in commutative algebra and algebraic geometry. But researchers will also benefit from this exposition. They will find an up-to-date description of the related research ... The reviewer recommends the book to anybody who is interested in commutative algebra and algebraic geometry and its computational aspects." Math. Reviews 2002"... a sophisticated notebook, with plenty of suggestions, examples and cross references ... It is a welcome new and deep exploration into commutative algebra and its relations with algebraic geometry. It is full of results, from simple tricks to more elaborate constructions, all having in common a computational and constructive nature..." Jahresberichte der DMV 1999

Symbolic Integration I is destined to become the standard reference work in the field. Manuel Bronstein is a leading expert on this topic and his book is the first to treat the subject both comprehensively and in sufficient detail - incorporating new results along the way. The book addresses mathematicians and computer scientists interested in symbolic computation, developers and programmers of computer algebra systems as well as users of symbolic integration methods. Many algorithms are given in pseudocode ready for immediate implementation, making the book equally suitable as a textbook for lecture courses on symbolic integration.This second edition offers a new chapter on parallel integration, a number of other improvements and a couple of additional exercises. From the reviews of the first edition: "... The writing is excellent, and the author provides a clear and coherent treatment of the problem of symbolic integration of transcendental functions…" F. Winkler, Computing Reviews 1997

Ergodic theory is hard to study because it is based on measure theory, which is a technically difficult subject to master for ordinary students, especially for physics majors. Many of the examples are introduced from a different perspective than in other books and theoretical ideas can be gradually absorbed while doing computer experiments. Theoretically less prepared students can appreciate the deep theorems by doing various simulations. The computer experiments are simple but they have close ties with theoretical implications. Even the researchers in the field can benefit by checking their conjectures, which might have been regarded as unrealistic to be programmed easily, against numerical output using some of the ideas in the book. One last remark: The last chapter explains the relation between entropy and data compression, which belongs to information theory and not to ergodic theory. It will help students to gain an understanding of the digital technology that has shaped the modern information society.

The subject of this book is the solution of polynomial equations, that is, s- tems of (generally) non-linear algebraic equations. This study is at the heart of several areas of mathematics and its applications. It has provided the - tivation for advances in di?erent branches of mathematics such as algebra, geometry, topology, and numerical analysis. In recent years, an explosive - velopment of algorithms and software has made it possible to solve many problems which had been intractable up to then and greatly expanded the areas of applications to include robotics, machine vision, signal processing, structural molecular biology, computer-aided design and geometric modelling, as well as certain areas of statistics, optimization and game theory, and b- logical networks. At the same time, symbolic computation has proved to be an invaluable tool for experimentation and conjecture in pure mathematics. As a consequence, the interest in e?ective algebraic geometry and computer algebrahasextendedwellbeyonditsoriginalconstituencyofpureandapplied mathematicians and computer scientists, to encompass many other scientists and engineers. While the core of the subject remains algebraic geometry, it also calls upon many other aspects of mathematics and theoretical computer science, ranging from numerical methods, di?erential equations and number theory to discrete geometry, combinatorics and complexity theory. Thegoalofthisbookistoprovideageneralintroduction tomodernma- ematical aspects in computing with multivariate polynomials and in solving algebraic systems.

The fascinating theory of error-correcting codes is a rather new addition to the list of mathematical disciplines. It grew out of the need to communicate information electronically, and is currently no more than 60 years old. - ing an applied discipline by de?nition, a surprisingly large number of pure mathematical areas tie into Coding Theory. If one were to name just the most important connections, one would start of course with Linear Algebra, then list Algebra and Combinatorics, and further mention Number Theory and - ometry as well as Algebraic Geometry. Being a thorough introduction to the ?eld, this book starts from the very beginning, which is the channel model of communication in the presence of noise. From there, we develop the fundamental concepts of error-correcting codes, like the Hamming metric and the maximum likelihood decoding pr- ciple. After discussing dual codes and simple decoding procedures, this book takes an unusual turn. The standard approach would be to move on from there and introduce either more theory or present standard constructions of codes. The approach taken here is different.

A new starting-point and a new method are requisite, to insure a complete [classi?cation of the Steiner triple systems of order 15]. This method was furnished, and its tedious and di?cult execution und- taken, by Mr. Cole. F. N. Cole, L. D. Cummings, and H. S. White (1917) [129] The history of classifying combinatorial objects is as old as the history of the objects themselves. In the mid-19th century, Kirkman, Steiner, and others became the fathers of modern combinatorics, and their work – on various objects, including (what became later known as) Steiner triple systems – led to several classi?cation results. Almost a century earlier, in 1782, Euler [180] published some results on classifying small Latin squares, but for the ?rst few steps in this direction one should actually go at least as far back as ancient Greece and the proof that there are exactly ?ve Platonic solids. One of the most remarkable achievements in the early, pre-computer era is the classi?cation of the Steiner triple systems of order 15, quoted above. An onerous task that, today, no sensible person would attempt by hand calcu- tion. Because, with the exception of occasional parameters for which com- natorial arguments are e?ective (often to prove nonexistence or uniqueness), classi?cation in general is about algorithms and computation.

This book provides a quick access to computational tools for algebraic geometry, the mathematical discipline which handles solution sets of polynomial equations. Originating from a number of intense one week schools taught by the authors, the text is designed so as to provide a step by step introduction which enables the reader to get started with his own computational experiments right away. The authors present the basic concepts and ideas in a compact way.

One of the most remarkable and beautiful theorems in coding theory is Gleason's 1970 theorem about the weight enumerators of self-dual codes and their connections with invariant theory. In the past 35 years there have been hundreds of papers written about generalizations and applications of this theorem to different types of codes. This self-contained book develops a new theory which is powerful enough to include all the earlier generalizations.It is also in part an encyclopedia that gives a very extensive list of the different types of self-dual codes and their properties, including tables of the best codes that are presently known. Besides self-dual codes, the book also discusses two closely-related subjects, lattices and modular forms, and quantum error-correcting codes.This book, written by the leading experts in the subject, has no equivalent in the literature and will be of great interest to mathematicians, communication theorists, computer scientists and physicists.

The algorithmic problems of real algebraic geometry such as real root counting, deciding the existence of solutions of systems of polynomial equations and inequalities, finding global maxima or deciding whether two points belong in the same connected component of a semi-algebraic set appear frequently in many areas of science and engineering. In this textbook the main ideas and techniques presented form a coherent and rich body of knowledge.Mathematicians will find relevant information about the algorithmic aspects. Researchers in computer science and engineering will find the required mathematical background.Being self-contained the book is accessible to graduate students and even, for invaluable parts of it, to undergraduate students.This second edition contains several recent results, on discriminants of symmetric matrices, real root isolation, global optimization, quantitative results on semi-algebraic sets and the first single exponential algorithm computing their first Betti number.

The appearance of this volume celebrates the ?rst decade of Magma, a new computeralgebrasystemlaunchedattheFirstMagmaConferenceonCom- tational Algebra held at Queen Mary and West?eld College, London, August 1993. This book introduces the reader to the role Magma plays in advanced mathematical research. Each paper examines how the computer can be used to gain insight into either a single problem or a small group of closely related problems. The intention is to present su?cient detail so that a reader can (a), gain insight into the mathematical questions that are the origin of the problems,and(b),developanunderstandingastohowsuchcomputations are speci?edinMagma.Itishopedthatthereaderwillcometoarealisationofthe important rolethatcomputational algebracanplayinmathematical research. Readers not primarily interested in using Magma will easily acquire the skills needed to undertake basic programming in Magma, while experienced Magma users can learn both mathematics and advanced computational methods in areas related to their own. The core of the volume comprises 14 papers. The authors were invited to submit articles on designated topics and these articles were then reviewed by referees. Although by no means exhaustive, the topics range over a consid- ablepartofMagma’scoverageofalgorithmicalgebra:fromnumbertheoryand algebraicgeometry,viarepresentationtheoryandcomputationalgrouptheory to some branches of discrete mathematics and graph theory. The papers are preceded by an outline of the Magma project, a brief summary of the papers and some instructions on reading the Magma code. A basic introduction to the Magma language is given in an appendix. Theeditorsexpresstheirgratitudetothecontributorstothisvolume,both for the work put into producing the papers and for theirpatience.

From the reviews:"... Despite the appearance [...] in a series titled Algorithms and Computation of Mathematics, computation occupies only a small part of the monograph. It is best described as a useful reference for one's personal collection and a text for a full-year course given to graduate or even senior undergraduate students. [...] the book under review is worth purchasing for the library and possibly even for one's own collection. The author's interest in the history and development of this area is evident, and we have pleasant glimpses of progress over the last three centuries [...] the reader gains a synopsis of and guide to the literature ..." E.Barbeau, SIAM Review 47:3, 2005."This is an exposition of polynomial theory and results, both classical and modern. [...] the volume is packed with results and proofs that are well organised thematically [...] What is unusual is to have a text that embraces and intermingles both analytic and algebraic aspects of the theory…" S.D.Cohen, Math.Reviews 2005

Systems of polynomial equations arise throughout mathematics, science, and engineering. Algebraic geometry provides powerful theoretical techniques for studying the qualitative and quantitative features of their solution sets. Re­ cently developed algorithms have made theoretical aspects of the subject accessible to a broad range of mathematicians and scientists. The algorith­ mic approach to the subject has two principal aims: developing new tools for research within mathematics, and providing new tools for modeling and solv­ ing problems that arise in the sciences and engineering. A healthy synergy emerges, as new theorems yield new algorithms and emerging applications lead to new theoretical questions. This book presents algorithmic tools for algebraic geometry and experi­ mental applications of them. It also introduces a software system in which the tools have been implemented and with which the experiments can be carried out. Macaulay 2 is a computer algebra system devoted to supporting research in algebraic geometry, commutative algebra, and their applications. The reader of this book will encounter Macaulay 2 in the context of concrete applications and practical computations in algebraic geometry. The expositions of the algorithmic tools presented here are designed to serve as a useful guide for those wishing to bring such tools to bear on their own problems. A wide range of mathematical scientists should find these expositions valuable. This includes both the users of other programs similar to Macaulay 2 (for example, Singular and CoCoA) and those who are not interested in explicit machine computations at all.

From the reviews of the 1st edition:"This book provides a comprehensive and detailed account of different topics in algorithmic 3-dimensional topology, culminating with the recognition procedure for Haken manifolds and including the up-to-date results in computer enumeration of 3-manifolds. Originating from lecture notes of various courses given by the author over a decade, the book is intended to combine the pedagogical approach of a graduate textbook (without exercises) with the completeness and reliability of a research monograph…All the material, with few exceptions, is presented from the peculiar point of view of special polyhedra and special spines of 3-manifolds. This choice contributes to keep the level of the exposition really elementary. In conclusion, the reviewer subscribes to the quotation from the back cover: "the book fills a gap in the existing literature and will become a standard reference for algorithmic 3-dimensional topology both for graduate students and researchers". Zentralblatt für Mathematik 2004For this 2nd edition, new results, new proofs, and commentaries for a better orientation of the reader have been added. In particular, in Chapter 7 several new sections concerning applications of the computer program "3-Manifold Recognizer" have been included.

This book deals with algorithmic problems concerning binary quadratic forms 2 2 f(X,Y)= aX +bXY +cY with integer coe?cients a, b, c, the mathem- ical theories that permit the solution of these problems, and applications to cryptography. A considerable part of the theory is developed for forms with real coe?cients and it is shown that forms with integer coe?cients appear in a natural way. Much of the progress of number theory has been stimulated by the study of concrete computational problems. Deep theories were developed from the classic time of Euler and Gauss onwards to this day that made the solutions ofmanyof theseproblemspossible.Algorithmicsolutionsandtheirproperties became an object of study in their own right. Thisbookintertwinestheexpositionofoneveryclassicalstrandofnumber theory with the presentation and analysis of algorithms both classical and modern which solve its motivating problems. This algorithmic approach will lead the reader, we hope, not only to an understanding of theory and solution methods, but also to an appreciation of the e?ciency with which solutions can be reached. The computer age has led to a marked advancement of algorithmic - search. On the one hand, computers make it feasible to solve very hard pr- lems such as the solution of Pell equations with large coe?cients. On the other, the application of number theory in public-key cryptography increased the urgency for establishing the complexity of several computational pr- lems: many a computer system stays only secure as long as these problems remain intractable.

This book is intended as a text for a course on cryptography with emphasis on algebraic methods. It is written so as to be accessible to graduate or advanced undergraduate students, as well as to scientists in other fields. The first three chapters form a self-contained introduction to basic concepts and techniques. Here my approach is intuitive and informal. For example, the treatment of computational complexity in Chapter 2, while lacking formalistic rigor, emphasizes the aspects of the subject that are most important in cryptography. Chapters 4-6 and the Appendix contain material that for the most part has not previously appeared in textbook form. A novel feature is the inclusion of three types of cryptography - "hidden monomial" systems, combinatorial-algebraic sys­ tems, and hyperelliptic systems - that are at an early stage of development. It is too soon to know which, if any, of these cryptosystems will ultimately be of practical use. But in the rapidly growing field of cryptography it is worthwhile to continually explore new one-way constructions coming from different areas of mathematics. Perhaps some of the readers will contribute to the research that still needs to be done. This book is designed not as a comprehensive reference work, but rather as a selective textbook. The many exercises (with answers at the back of the book) make it suitable for use in a math or computer science course or in a program of independent study.

In the years 1994, 1995, two EIDMA mini courses on Computer Algebra were given at the Eindhoven University of Technology by, apart from ourselves, various invited lecturers. (EIDMA is the Research School 'Euler Institute for Discrete Mathematics and its Applications'.) The idea of the courses was to acquaint young mathematicians with algorithms and software for mathemat­ ical research and to enable them to incorporate algorithms in their research. A collection of lecture notes was used at these courses. When discussing these courses in comparison with other kinds of courses one might give in a week's time, Joachim Neubüser referred to our courses as 'tapas'. This denomination underlined that the courses consisted of appe­ tizers for various parts of algorithmic algebra; indeed, we covered such spicy topics as the link between Gröbner bases and integer programming, and the detection of algebraic solutions to differential equations. As a collection, the not es turned out to have some appeal of their own, which is the main reason why the idea came up of transforming them into book form. We feIt however, that the book should be distinguishable from a standard text book on computer algebra in that it retains its appetizing flavour by presenting a variety of topics at an accessible level with a view to recent developments.