Elliptic Curves and Algebraic Divisibility Sequences
Integral points on elliptic curves and explicit valuations of division polynomials |
|
-
Submitted, 37 pages.
- Assuming Lang's conjectured lower bound on the heights of non-torsion points on an elliptic curve, we show that there exists an absolute constant C such that for any elliptic curve E/Q and non-torsion point P in E(Q), there is at most one integral multiple [n]P such that n > C. The proof is a modification of a proof of Ingram giving an unconditional but not uniform bound. The new ingredient is a collection of explicit formulae for the sequence of valuations of the division polynomials. For P of non-singular reduction, such sequences are already well described in most cases, but for P of singular reduction, we are led to define a new class of sequences called elliptic troublemaker sequences, which measure the failure of the Néron local height to be quadratic. As a corollary in the spirit of a conjecture of Lang and Hall, we obtain a uniform upper bound on the height of integral points having two large integral multiples, in terms of the height of the curve.
Algebraic divisibility sequences over function fields |
|
Elliptic nets and elliptic curves |
|
-
Algebra and Number Theory, 5-2 (2011), 197-229.
- An elliptic divisibility sequence is an integer recurrence sequence
associated to an elliptic curve over the rationals together with a rational
point on that curve. In this paper we present a higher-dimensional analogue
over arbitrary base fields. Suppose E is an elliptic curve over a field K, and
P1, ..., Pn are points on E defined over K. To this information we associate
an n-dimensional array of values in K satisfying a nonlinear recurrence
relation. Arrays satisfying this relation are called elliptic nets. We
demonstrate an explicit bijection between the set of elliptic nets and the set
of elliptic curves with specified points. We also obtain
Laurentness/integrality results for elliptic nets.
Amicable pairs and aliquot cycles for elliptic curves |
|
-
With Joseph H. Silverman.
Experimental Mathematics, 20-3 (2011), 329-357.
- An amicable pair for an elliptic curve E/Q is a pair of primes (p,q) of good reduction for E satisfying #E(Fp) = q and #E(Fq) = p. In this paper we study elliptic amicable pairs and analogously defined longer elliptic aliquot cycles. We show that there exist elliptic curves with arbitrarily long aliqout cycles, but that CM elliptic curves (with j not 0) have no aliqout cycles of length greater than two. We give conjectural formulas for the frequency of amicable pairs. For CM curves, the derivation of precise conjectural formulas involves a detailed analysis of the values of the Grossencharacter evaluated at a prime ideal P in End(E) having the property that #E(Fp) is prime. This is especially intricate for the family of curves with j = 0.
Character sums with division polynomials |
|
-
With Igor E. Shparlinski.
To appear in Canadian Mathematical Bulletin, 8 pages.
- We obtain nontrivial estimates of quadratic character sums of division polynomials ψn(P), n=1,2, ..., evaluated at a given point P on an elliptic curve over a finite field of q elements. Our bounds are nontrivial if the order of P is at least q1/2 + ε for some fixed ε > 0. This work is motivated by an open question about statistical indistinguishability of some cryptographically relevant sequences which has recently been brought up by K. Lauter and the second author.
Terms in elliptic divisibility sequences divisible by their indices |
|
-
With Joseph H. Silverman.
Acta Arithmetica, 146 (2011), 355-378.
- Let D = (Dn)n ≥ 1 be an elliptic divisibility sequence. We study the set S(D) of indices n satisfying n | Dn. In particular, given an index n in S(D), we explain how to construct elements nd in S(D), where d is either a prime divisor of Dn, or d is the product of the primes in an aliquot cycle for D. We also give bounds for the exceptional indices that are not constructed in this way.
Elliptic Curve Cryptography
Pairings on hyperelliptic curves |
|
The elliptic curve discrete logarithm problem and equivalent hard problems for elliptic divisibility sequences |
|
-
With Kristin E. Lauter.
Selected Areas in Cryptography 2008, Springer LNCS, 5381 (2009), 309-327.
- We define three hard problems in terms of the theory of elliptic
divisibility sequences (EDS Association, EDS Residue and EDS
Discrete Log), each of which is solvable in sub-exponential time if and
only if the elliptic curve discrete logarithm problem is solvable in
sub-exponential time. We also relate the problem of EDS
Association to the Tate pairing and the MOV, Frey-Ruck and Shipsey EDS
attacks on the elliptic curve discrete logarithm problem in the cases
where these apply.
The Tate pairing via elliptic nets |
|
-
Pairing-Based Cryptography -- PAIRING 2007, Springer LNCS, 4575 (2007), 329-348.
- We derive a new algorithm for computing the Tate
pairing on an elliptic curve over a finite field. The algorithm uses a
generalisation of elliptic divisibility sequences known as elliptic
nets, which are maps from Zn to a ring that satisfy a certain
recurrence relation. We explain how an elliptic net is associated to an
elliptic curve and reflects its group structure. Then we give a formula
for the Tate pairing in terms of values of the net. Using the
recurrence relation we can calculate these values in linear time.
Software
the Tate pairing is the bottleneck to efficient pairing-based
cryptography. The new algorithm has time complexity comparable to
Miller's algorithm, and is likely to yield to further optimisation.
Apollonian Circle Packings
The sensual Apollonian circle packing |
|
-
Preprint.
-
The curvatures of the circles in integral Apollonian circle packings, named for Apollonius of Perga (262-190 BC), form an infinite collection of integers whose Diophantine properties have recently seen a surge in interest. Here, we give a new description of Apollonian circle packings built upon the study of the collection of bases of Z[i]2, inspired by, and intimately related to, the `sensual quadratic form' of Conway.
Game Theory
A duality principle for selection games |
|
-
With Lionel Levine and Scott Sheffield.
To appear in Proceedings of the American Mathematical Society, 8 pages.
-
A dinner table seats k guests and holds n discrete morsels of food. Guests select morsels in turn until all are consumed. Each guest has a ranking of the morsels according to how much he would enjoy eating them; these rankings are commonly known.
A gallant knight always prefers one food division over another if it provides strictly more enjoyable collections of food to one or more other players (without giving a less enjoyable collection to any other player) even if it makes his own collection less enjoyable. A boorish lout always selects the morsel that gives him the most enjoyment on the current turn, regardless of future consumption by himself and others.
We show the way the food is divided when all guests are gallant knights is the same as when all guests are boorish louts but turn order is reversed. This implies and generalizes a classical result of Kohler and Chandrasekaran (1971) about two players strategically maximizing their own enjoyments. We also treat the case that the table contains a mixture of boorish louts and gallant knights.
Our main result can also be formulated in terms of games in which selections are made by groups. In this formulation, the surprising fact is that a group can always find a selection that is simultaneously optimal for each member of the group.
How to make the most of a shared meal: plan the last bite first |
|
-
With Lionel Levine.
American Mathematical Monthly, 119-7 (2012), 550-565.
- If you are sharing a meal with a companion, how best to make sure you get your favourite fork-fulls? Ethiopian Dinner is a game in which two players take turns eating morsels from a common plate. Each morsel comes with a pair of utility values measuring its tastiness to the two players. Kohler and Chandrasekaharan discovered a good strategy -- a subgame perfect equilibrium, to be exact -- for this game. We give a new visual proof of their result. The players arrive at the equilibrium by figuring out their last move first and working backward. We conclude that it's never too early to start thinking about dessert.
Commutative Algebra
General Zelevinsky Algebras |
|
-
With Peter Hoffman and Chris Wooff.
Under revision, 23 pages.
- Here we show that a fairly general notion of `Hopf algebra with positivity and self-adjointness' admits a decomposition into a tensor product of `atomic' such objects. Then, for an infinite family of base rings, we classify the atomic objects. This generalizes both a theorem of Zelevinsky, which he applied to linear representations of various families of groups, and an analogous theorem of Bean and Hoffman, which had applications to projective representations of symmetric and alternating groups (and more generally to some covering groups of monomial groups). The sequence of examples for which the classification is complete starts with these two earlier results. The remaining terms of the sequence will apply to representations of covers of certain wreath product groups.
Unpublished Notes
Formulary for elliptic divisibility sequences and elliptic nets |
|
-
Just the formulas. No warranty is expressed or implied. May cause side effects. Not to be taken internally. Remove label before using. Not to be used as a flotation device. May contain nuts. Please report any errors you may find.
