DIMACS Workshop on Unusual Applications of Number Theory

Abstracts


Krishnaswami Alladi, alladi@math.ufl.edu, University of Florida

Title: G\"ollnitz's (Big) theorem, reformulations, applications, and extensions

ABSTRACT: In 1967, G\"ollnitz proved the following deep partition theorem: "The number of partitions of an integer $n$ into distinct parts $\equiv 2,4,5 (mod6)$ equals the number of partitions of $n$ in the form $m_1+m_2+...m_{\nu}$ such that $m_\nu\ne 1 or 3$, and $m_i-m_{i+1}\ge 6$ with strict inequality if $m_i\equiv 0,1,3 (mod 6)$". In this talk, the importance of G\"ollnitz's theorem in relation to other fundamental results in the theory of partitions and q-series will be explained using the method of weighted word approach of 1995 due to me, George Andrews, and Basil Gordon, and the many reformulations I subsequently obtained. A problem that was stated by Andrews in 1971, and which had remained unsolved since then, is whether there exist results beyond G\"ollnitz's theorem. Alexander Berkovich and I have recently made a breakthrough on this problem by finding a remarkable key identity in four free parameters which reduces to the key identity in three free parameters that Alladi-Andrews-Gordon found in 1995. The final part of the lecture will deal with this exciting domain that lies beyond the G\"ollnitz theorem.


George Andrews andrews@math.psu.edu, Pennsylvania State University

Title: Positivity questions in partitions and the Friedman-Joichi-Stanton conjecture

In this talk we shall look at positivity questions in partitions, beginning with some classical problem including the Borwein conjectures.

We shall conclude with the the Friedman-Joichi-Stanton conjecture which asserts that for each odd m>2, the number of partitions of n into parts taken from {m,m+1,...,2m-1] is non-decreasing in n for n>1. We will prove the following:

Theorem: The Friedman-Joichi-Stanton conjecture is true whenever m is an odd prime.


Michael Anshel, CCNY-CUNY

Title: Constructing Public Key Cryptosystems Via Combinatorial Group Theory

A Public Key Cryptosystem (PKC) is an algorithmic method for securely sending private information over an insecure channel in which the communicating parties have no common shared secret (e.g. key). At the heart of a PKC is a two-party secure computation referred to as a protocol. The major PKC's and their associated protocols in use today are based on finite abelian groups. They include the Diffie- Hellman (DH), RSA, and Elliptic Curve Cryptosystems (ECC). Combinatorial Group Theory (CGT) is the study of groups by means of generators and defining relators. We discuss several methods for constructing PKC's via CGT evolved over the past decade with my co-workers Iris Anshel and Dorian Goldfeld. The computational security of our protocols are based on the complexity of problems in CGT.We offer a particular instance employing the computational theory of braid groups which to date has survived cryptanalytic attacks.


Eric Bach, bach@cs.wisc.edu, University of Wisconsin

Title: P-Adic Secant Algorithms

Abstract: The standard method for finding roots of polynomials over the p-adic integers is Newton iteration. Although this converges quadratically, it also requires evaluation of the polynomial and its derivative at each step. In ordinary numerical analysis, the secant method allows one to use one function evaluation per step, while still maintaining a reasonable convergence rate. This talk will discuss how these ideas can be extended to p-adic numerical analysis.


Vitaly Bergelson, vitaly@math.ohio-state.edu, Ohio State University

Title: Polynomial ergodic theorems, Ramsey theory and IP-sets

Given an infinite set S in N, an IP-set generated by S is, by definition, the set of finite sums of distinct elements from S. It turns out that many results in ergodic theory which traditionally deal with (semi)group actions, admit refinements involving IP-sets. In this talk we shall discuss the IP-versions of polynomial ergodic theorems, including the recent joint work with Randall McCutcheon on IP-refinement of the polynomial Szemeredi theorem obtained by A. Leibman and the speaker in 96'. Some open problems will also be discussed.


Alexander Berkovich, alexb@math.ufl.edu, University of Florida

Title: Variations on the Borwein Conjecture

Borwein conjecture remains one of the outstanding unsettled problems in mathematics. Borwein conjecture is not an isolated result and, in 1997, Bressoud formulated a variety of conjectures of the similar type. I will discuss my work in progress of proving many classes of the generalized Borwein conjecture.


D.V. Chudnovsky and G.V. Chudnovsky, david@gateway.imas.poly.edu, Polytechnic University

Title: One Bit World

Signal processing binary streams usually represent sequences of numbers having a significant dynamic range (32, 24, 16 or, at least, 8 bits). For many crucial applications the stream of data is inherently one bit (square pulses of a fixed height). We describe continuous (analog) waveforms using one bit representations. This is relevant for A/D and D/A conversion in such diverse applications as audio, power electronics, bar coding, ..., etc.


Paula Cohen, Paula.Cohen@agat.univ-lille1.fr, Universite des Sciences er Technologies de Lille

Title: Non-commutative number theory

Abstract: In this talk we give a survey of the interplay between non-commutative geometry and number theory as developed in recent years, most notably by Alain Connes. We shall cover aspects of Bost and Connes' work on C*-Hecke algebras and of Alain Connes' work on the Riemann Hypothesis.


J. A. Dias da Silva, perdigao@hermite.cii.fc.ul.pt, University of Lisbon

Title: Linear Algebra and Additive Theory

We make an overview on the use of Linear Algebra to solve additive problems. We make a special reference to the Erdos Heilbronn conjecture and to generalizations of Pollard theorem.


Per Enflo, enflo@mcs.kent.edu, Kent State University

Title: On the dynamics of homeomorphisms of n-dimensional manifolds - how well can the future be predicted?

It has been shown (by my student N.Bernardes) that chaotic behavior is not at all typical for homeomorphisms of manifolds. In fact, to stay close to an orbit of a function f forever, we can even allow ourselves to make a small computational error in each step. One has the following THEOREM: For most homeomorphisms f of the unit ball of R^n (in category sense under sup-metric) and most starting points a of orbits (in measure and catgory sense) the following holds: For every positive epsilon there is a positive delta such that if a sequence a^0,a^1,a^2, ... satisfies d(a^0,a) < delta and d(a^m,f(a^m-1)) < delta for all m, then d(a^n,f^n(a)) < epsilon for all n, where f^n means the function f iterated n times. In particular, errors can never accumulate. The proofs of these types of results combine ideas from several branches of mathematics.


Bruce Fleischer, fleischr@us.ibm.com, IBM

Title: Hardware Mathematical Facilities of IBM Mainframe Computers

Until recently, IBM mainframe computers supported only proprietary numerical formats (e.g., "hex" floating point formats). This situation has changed, and current mainframes support both IEEE 754 and IBM formats. The math facilities now available will be presented from a programmer's point of view, including the structure of the fixed-point and floating-point units, available formats and operations, and performance.


Gregory Freiman, grisha@math.tau.ac.il, Tel Aviv University

Title: Applications of the Structure Theory of Set Addition

Let K be a finite set of integers, and let K+K denote the two-fold sumset of K. If the cardinality |K+K| is small compared to |K|, then we can deduce many geometric and structural properties of the set K. These results can be applied to obtain new theorems in combinatorics and integer programming.


John B. Friedlander, frdlndr@ias.edu, University of Toronto

Title: Exponential sums and cryptography

We discuss joint work with Igor Shparlinski and, in part, with several other people concerning bounds for certain exponential sums which prove uniformity of the distribution of some integer sequences motivated by their interest in cryptography.


Shuhong Gao, sgao@math.clemson.edu, Clemson University

Title: Decomposition of polytopes and polynomials

It is well known that a polynomial (over any field) with $n$ variables is associated with a polytope in the $n$-dimensional Euclidean space, called its Newton polytope. When a polynomial factors, its polytope decomposes in the sense of Minkowski into a sum of integral polytopes, a fact observed by Ostrowski in 1921. Motivated by this connection, we study integral convex polytopes and their integral decompositions. We show how to construct indecomposable polytopes, which give simple criteria for absolutely irreducible polynomials including the well known Eisenstein's criterion. We prove that deciding decomposability of integral polygons is NP-complete and present a pseudo-polynomial time algorithm for decomposing polygons. For higher dimensional polytopes, we give a heuristic algorithm which is based upon projections and uses randomization. Applications of our algorithms include absolute irreducibility testing and factorization of polynomials via their Newton polytopes.

This talk is partially based on joint work with Alan Lauder.


Dorian Goldfeld, goldfeld@columbia.edu, Columbia University

Title: Zeta Functions as One-Way Functions with Applications to Cryptography

The theory of zeta functions gives rise to new classes of one-way functions. We explain that these one-way zeta functions can be computed extremely rapidly at low cost and can be used for cryptographic applications.


Sinan Gunturk, cgunturk@math.Princeton.EDU, Princeton University

Title: Number Theoretical Error Estimates in a Quantization Scheme for Bandlimited Signals

Sigma-delta quantization is a way of representing bandlimited signals (functions with compactly supported Fourier transforms) by {0,1} sequences for each sampling density such that convolving these sequences with appropriately chosen filters produces approximations of the original signals. Approximations are refined by increasing the sampling density; this is what makes such a scheme fundamentally different from more conventional quantization schemes, where the sampling density is not varied. We present various examples of how tools from analytic number theory are employed in sharpening the error estimates in sigma-delta systems.


Neil Hindman, NHINDMAN@aol.com, Howard University

Title: Some (usually easy) algebraic proofs of (usually hard) results in Ramsey Theory.

Using the algebra of the Stone-Cech compactification of N we present (based on the old algebraic proof of the Finite Sums Theorem) an easy proof of a Ramsey Theoretic result which has no other known proof and talk about a sort of--, semi--, kind of--, easy proof of a very hard recent result of Bergelson and Leibman.


Joshua Holden, holden@math.duke.edu, Duke University

Title: Online Analysis of Algorithms for Computing Quadratic Irregularity

The concept of regular and irregular primes can be extended to the setting of arbitrary totally real number fields using the values of the zeta function at negative integers as our ``higher Bernoulli numbers''. We are interested in the feasibility of finding these analogues of irregular primes, both as pure theory and also because they are associated with class groups which may be especially suitable for cryptography.

In the case of a real quadratic field, Siegel presented two formulas for calculating these zeta-values: one using entirely elementary methods and one which is derived from the theory of modular forms. Several algorithms have previously been developed based on these formulas. In this talk I will analyze ``online'' versions of these algorithms, namely determining how long we should expect to search before finding, say, the first class group with certain properties related to its size and the order of its elements. This should be particularly useful for cryptographic applications, in which we would be explicitly looking for a class group (or a small number of them) with a hard discrete logarithm problem.


David Ingerman, ingerman@ias.edu, The Institute for Advanced Study

Title: Fermat primes and symmetries of the void

A fundamental theorem in inverse scattering is that restriction of Green function of Laplace-Beltrami operator on a boundary of a ball determines the spectrum of the wave equation inside. The consequent identities are transcendental and in the case of continuous media require the language of trace formulas, cascades of determinants and correlation functions. However, on graphs with metrics valued in towers of quadratic extensions of rational numbers the theorem and identities become obvious once the numbers are written in continued fraction form. The exactness/self-containment of this discrete time-space model is due to a coincidental existence of rotation invariant polygons constructable with straightedge and compass. The continued fraction representations allow constructions of finite difference grids with exponentially fast converging PDE solutions.


Renling Jin, jinr@cofc.edu, The College of Charleston

Title: The use of infinite large integers in the study of finite integers - The applications of nonstandard analysis to upper Banach density problems

Let A be a set of positive integers. For any positive integers a and b, let A(a,b) be the number of elements in A which are greater than a-1 and less than b+1. BD(A), the upper Banach density of A, > r if for every n, there are a and b such that b-a > n and A(a,b)/(b-a+1) > r. BD(A) = s if the supreme of those r's such that BD(A) > r. In the talk, I will introduce two results about upper Banach density, which I obtained recently using nonstandard analysis. The first result says that if BD(A) > 0 and BD(B) > 0, then A+B is piecewise syndetic. This result complements an old result in combinatorial number theory, which says that if BD(A) > 0, then A-A is syndetic. The second result says that BD(A+B+{0,1}) is 1 or greater than or equal to BD(A)+BD(B). This result is parallel to Mann's Theorem in additive number theory. Using these two results as examples, I will discuss how, in general, the ideas from nonstandard analysis can be applied to upper Banach density problems.


Bahman Kalantari, kalantar@cs.rutgers.edu, Rutgers University

Title: New Formulas for Approximation of PI and Other Transcendental Numbers

We derive many new formulas for approximation of pi. The formulas make use of a sequence of iteration functions called the Basic Family; a nontrivial determinantal generalization of Taylor's theorem; other ingredients; as well as several new results presented in the present paper. In one scheme, one evaluates members of the Basic Family, for an appropriately selected function, all at the same input. This scheme generates almost a fixed and pre-selected number of digits in each successive evaluation. The computation amounts to the evaluation of a recursive formula and is equivalent to the computation of special Toeplitz matrix determinants. The approximations of pi obtained via this scheme are within simple algebraic extensions of the rational field. In a second scheme, the fixed-point iteration is applied to any fixed member of the Basic Family, while selecting an appropriate function. In this scheme we prove high-order of convergence from the initial point. We report on some preliminary computational results obtained via Maple. Analogous formulas can be used to approximate other transcendental numbers. For instance, we also give a formula for approximation of e.


J. C. Lagarias, jcl@research.att.com, AT&T Labs-Research

Title: Spectral sets, tilings and exponential polynomials

A compact set S in R^n of positive measure is a spectral set if its space of square summable functions has an orthogonal basis of exponentials. It is conjectured that a set S is a spectral set if and only if it tiles R^n by translations. This talk describes results for sets of the form S= [0, 1]^n + A, where A is a finite set of integers. The connection to number theory arises through criteria relating to the zeros of multivariable exponential polynomials, and to sums of roots of unity adding to zero, in the one-dimensional case.


Kristin Lauter, klauter@microsoft.com, Microsoft

Title: The number of rational points on genus 3 curves over finite fields

Curves over finite fields have interesting applications in both cryptography and error-correcting codes. I will briefly describe these applications and then speak about my recent work on determining the maximum number of rational points possible on genus 3 curves over finite fields.

The maximum number of rational points possible on a genus 1 curve over a finite field of $q$ elements is known due to the Weil bound and Honda-Tate theory. The maximum is within 1 of the Weil bound for all $q$. In 1983, Serre determined the maximum for curves of genus 2. He showed that, for all $q$, the maximum for genus 2 is within 3 of the refined Weil bound. Serre asked if there is a similar bound for genus 3 or larger. This talk will present the result that for genus 3 and all $q$, either the maximum or the minimum is within 3 of the refined Weil bound. The proof is accomplished via an analysis of possible zeta functions combined with arguments on glueing of abelian varieties.


Alexander Leibman, leibman@math-ohio-state.edu, Ohio State University

Title: Ergodic Ramsey Theory and nilpotent groups

Furstenberg's approach to combinatorial theorems of van der Waerden and Szemeredi type is based on studying recurrence properties of several commuting operators. It turns out that the "abelian" multiple recurrence theorems are generalizable to the case where the operators involved generate a nilpotent group. This gives combinatorial applications in nilpotent setup and leads to new interesting problems.


Jim Lepowsky, lepowsky@math.rutgers.edu, Rutgers University

Title: Vertex operator algebras and the zeta function

Recently, connections have been found between the values of the Riemann zeta function at the negative integers and the basic principles of vertex operator algebra theory, allowing us to interpret and generalize certain work of S. Bloch involving zeta values and differential operators. Formal calculus and the "Jacobi identity" for vertex operator algebras play central roles. The talk will include an introduction to this point of view. This work is presented in the preprints math.QA/9909178 and math.QA/9909183.


Elon Lindenstrauss, elon@ias.edu, The Institute for Advanced Study

Title: Some relations between theorems of Freiman and Rusza in additive number theory and ergodic theory

Freiman and Rusza considered the question of what sets in some commutative groups such as Z^d can satisfy the doubling property

|A-A| < C|A|            (C fixed, |A| large).

In my talk I will consider a simple example of a f.g. solvable group with exponential growth, and show that only rather degenerate sets may satisfy the analogous property of

|A^-1 A| < C|A|.

I will also show how this example can be used to illuminate some theorems in the ergodic theory of amenable groups. All relevant definition will be explained in my talk.


Barry McCoy, mccoy@insti.physics.sunysb.edu, SUNY - Stony Brook

Title: Roger--Ramanujan identities in physics

Rogers--Ramanujan identities and their polynomial generalizations have been found to occur in conformal field theory and in statistical mechanics where they can be interpreted in terms of generalizations of the Pauli exclusion principle satisfied by free electrons. We present some of the new families of identities which have arisen from these branches of physics.


Victor S. Miller, victor@idaccr.org, IDA

Title: Elliptic Curves and their use in Cryptography

The security of many cryptographic protocols depends on the difficulty of solving the so-called ``discrete logarithm'' problem, in the multiplicative group of a finite field. Although, in the general case, there are no polynomial time algorithms for this problem, constant improvements are being made -- with the result that the use of these protocols require much larger key sizes, for a given level of security, than may be convenient.

An abstraction of these protocols shows that they have analogues in any group. The challenge presents itself: find some other groups for which there are no good attacks on the discrete logarithm, and for which the group operations are sufficiently economical. In 1985, the author suggested that the groups arising as the group of points on an elliptic curve over a finite field might fill the bill.

In this talk the cryptographic protocol will be described and the possible attacks using the "index calculus" (the method so effective against the multiplicative group) will be analyzed. Finally more recent work will be discussed.


John Milnor, jack@math.sunysb.edu, State University of New York - Stony Brook

Title: From Manifolds to Number Theory

Personal reminiscences of the problems in homotopy theory during the 50's and 60's which led to an interest in number theoretic questions about Bernoulli numbers, quadratic forms, and algebraic K-theory.


Carlos Julio Moreno, carlos@newton.baruch.cuny.edu, City University of New York

Title: The Value of the Gauss Sum

The well known determination of the sign of the quadratic Gauss sum provides a proof of the classical quadratic reciprocity law. We investigate the analogous question for the local root numbers of quadratic characters and determine, following earlier work of Dwork together with the explicit local reciprocity law, the main parameters in the Dwork-Lamprecht theory of values of Gauss sums. (Joint work with A. Wan).


Gretchen Ostheimer, gostheim@emerald.tufts.edu, Hofstra University

Title: Practical Algorithms for Infinite Matrix Groups

Over the last few decades considerable progress has been made in the development of practical algorithms for studying finite groups. Computer algebra programs such as GAP and MAGMA provide a rich set of primitives for investigating such groups. These programs have proved useful to mathematicians (both inside and outside of group theory) in solving problems that have eluded more traditional approaches. My own work is concerned with extending these capabilities to infinite groups.

In this talk I will describe an application of elementary algebraic number theory to the study of abelian matrix groups. Let X be a finite set of nxn matrices with integer entries and determinant 1 or -1. Let G be the group of matrices generated by X under multiplication. Assume that G is abelian, i.e. that the matrices of X commute. I will describe practical algorithms for studying the structure of G and for deciding whether a given nxn matrix is an element of G. These algorithms rely on algorithms from computational number theory developed by Buchmann and Pohst (1989).

This work was done under the direction of Charles C. Sims as part of my PhD thesis (1996) in mathematics at Rutgers University. Similar algorithms were developed independently by Babai, Beals, Cai, Ivanyos and Luks (1996).


Janos Pach, pach@cims.nyu.edu, NYU

Title: The discrete moment curve

Given a prime $p$, we call the set of all points $(1,i,i^2,\ldots,i^{d-1})$ modulo $p$ the $d$-dimensional {\em moment curve} $(0\le i < p)$. There are many famous open problems in combinatorial geometry (e.g., Heilbronn's problem) which are in one way or another related to this set. We will discuss two such problems. The first one is related to graph drawing: what is the size of the smallest grid that can accommodate a non-crossing straight-line drawing of a given graph? The second is a variant of the Littlewood-Offord problem: at most how many sums formed by a set of vectors in ``general position'' can coincide. Some of the results represent joint work with G. Harcos, G. Tardos, T. Thiele, and G. T\'oth.


Charles Radin, radin@fireant.ma.utexas.edu, University of Texas

Title: Relations in SO(3) supported by geodetic angles

We consider the subgroups of SO(3) generated by a pair of rotations of fixed but arbitrary finite order, and analyze the relations in such a group as a function of the angle separating the axes of rotation. The two main ingredients in the analysis are the algebraic properties of the separating angle and the symmetries of the Platonic solids.


Sinai Robins, srobins@euclid.math.temple.edu, Temple University

Title: The linear diophantine problem of Frobenius

Given positive integers a_1, ... a_n whose gcd is 1, it is well-known that there a smallest positive integer N (called the Frobenius number f(a_1, ... a_n) ) such that every integer greater than or equal to N is representable as a non-negative integer linear combination of the a_i's. Here we give new bounds for f(a_1, ... a_n). We do so by first giving an exact formula (in terms of higher dimensional Dedekind sums) for the exact number of non-negative solutions (x_1, ... , x_n) to a_1 x_1 + ... + a_n x_n = N for any positive integer N, using the theory of lattice point enumeration in rational polytopes.


Siddhartha Sahi, sahi@math.rutgers.edu, Rutgers University

Title: Some properties of Askey-Wilson polynomials

Abstract: The Askey scheme of orthogonal polynomials (in one variable) organizes the various known families of orthogonal polynomials in a hierarchy, indicating the various interrelationships between these polynomials. Sitting atop this hierarchy are the Askey-Wilson polynomials which depend on 5 parameters. All the other polynomials in the Askey scheme (e.g. Legendre polynomials, Hermite polynomials, Jacobi polynomials etc.) can be obtained by various specializations of these parameters.

We show that Askey-Wilson polynomials are closely related to the following algebra:

Generators: R, S, T, U
Relations: R ~ r, S ~ s, T ~ t, U ~ u, RSTU=v

Here r,s,t,u,v are 5 parameters and Y ~ y means a quadratic relation of the form (Y-y)(Y+1)=0


Jeffrey Shallit, shallit@graceland.uwaterloo.ca, University of Waterloo, Canada

Title: Formal Languages and Number Theory

In this talk, I will present some interesting connections between formal languages and number theory. Examples include

  1. Allouche's proof that the set of primitive words cannot be an unambiguous context-free language;
  2. Proofs of transcendence in finite characteristic;
  3. Recent results on the relative succinctness of context-free grammars and deterministic finite automata for unary regular languages.


Joseph Silverman, jhs@ntru.com, NTRU Cryptosystems, Inc.

Title: Lattices, Cryptography, and the NTRU Public Key Cryptosystem

The problem of finding extremely short vectors in high dimensional lattices is a very hard mathematical problem. Since manipulation of vectors via linear algebra is fast, this makes the shortest vector problem (SVP) a natural candidate for public key cryptography. A number of cryptosystems have been proposed that are based implicitly or explicitly on this problem and on the related closest vector problem (CVP). However, these systems have proven to be either insecure (when using lattices of small dimension) or impractical (when using lattices of large dimension) because their key sizes grow quadratically with the dimension of the lattice. In this talk I will discuss lattices, lattice problems, lattices in public key cryptography, and the NTRU public key cryptosystem. The NTRU PKCS, first presented at Crypto '96, is based on the short vector problem and has keys that grow essentially linearly in the dimension. This makes NTRU highly efficient and practical using lattices of sufficiently high dimension (on the order of 500 to 1000) to be also highly secure. In particular, NTRU encrypts and decrypts blocks one to two orders of magnitude faster than RSA and ECC at equivalent security levels. As time permits, I will also describe a related lattice-based authentication and signature scheme called PASS.


Francis Edward Su, su@math.hmc.edu, Harvey Mudd College and Cornell University

Title: Random Walks with Badly Approximable Numbers

A random walk on the circle generated by an irrational rotation exhibits convergence behavior related to the diophantine properties of the irrational. In joint work with Doug Hensley, we analyze the rate of convergence of a random walk on the circle generated by $d$ rotations, and establish sharp rates that show that badly approximable $d$-tuples in $R^d$ give rise to walks with the fastest convergence. For the case $d=2$ we exhibit what we believe are the optimal pair of generators, and show that it is near optimal.


Audrey Terras, ir152@sdcc3.ucsd.edu, Math. Dept., University of California - San Diego

Title: Finite Quantum Chaos

Physicists have long studied spectra of Schroedinger operators and random matrices, thanks to the implications for quantum mechanics. Analogously number theorists and geometers have investigated the statistics of spectra of Laplacians on Riemannian manifolds associated to arithmetic groups. This has been termed "arithmetic quantum chaos" by Sarnak. Equivalently one studies the zeros of Selberg zeta functions. Parallels with the statistics of the zeros of the Riemann zeta function have been evident for some time. Here we survey what may be called "finite quantum chaos" - namely the statistics of spectra of Laplacians of Cayley graphs of finite matrix groups. In the process we find many connections with the continuous theory and with special functions. The results can also be formulated in terms of Ihara zeta functions of graphs.


Malcolm Williamson, mwill@cts.com Center for Communications Research

Title: Public Key Cryptography: History and Open Questions

There are two well-known public key algorithms, RSA and D-H. These have each been discovered twice (once in the security community and once in the academic community). It is surprising that in the 25 years since their discovery there have been so few other algorithms found. The best methods known for breaking each of the algorithms show very marked similarities and yet the algorithms really are distinct and there is no obvious duality between them. In the last decade both algorithms have come into widespread use in commerce, banking and the military, but we still do not have mathematical proofs of their security.