Papers

Jump to:

The following articles are colour-coded to help you find certain topics:

Arithmetic of thin and Kleinian groups      Arithmetic of Abelian varieties      Cryptography

Research Preprints

  • Traceable random numbers from a nonlocal quantum advantage
    Gautam A. Kavuri, Jasper Palfree, Dileep V. Reddy, Yanbao Zhang, Joshua C. Bienfang, Michael D. Mazurek, Mohammad A. Alhejji, Aliza U. Siddiqui, Joseph M. Cavanagh, Aagam Dalal, Carlos Abellán, Waldimar Amaya, Morgan W. Mitchell, Katherine E. Stange, Paul D. Beale, Luís T.A.N. Brandão, Harold Booth, René Peralta, Sae Woo Nam, Richard P. Mirin, Martin J. Stevens, Emanuel Knill, Lynden K. Shalm.
    40 pages.
    [ arXiv:2411.05247  ]
    show abstract
    The unpredictability of random numbers is fundamental to both digital security and applications that fairly distribute resources. However, existing random number generators have limitations-the generation processes cannot be fully traced, audited, and certified to be unpredictable. The algorithmic steps used in pseudorandom number generators are auditable, but they cannot guarantee that their outputs were a priori unpredictable given knowledge of the initial seed. Device-independent quantum random number generators can ensure that the source of randomness was unknown beforehand, but the steps used to extract the randomness are vulnerable to tampering. Here, for the first time, we demonstrate a fully traceable random number generation protocol based on device-independent techniques. Our protocol extracts randomness from unpredictable non-local quantum correlations, and uses distributed intertwined hash chains to cryptographically trace and verify the extraction process. This protocol is at the heart of a public traceable and certifiable quantum randomness beacon that we have launched. Over the first 40 days of operation, we completed the protocol 7434 out of 7454 attempts — a success rate of 99.7%. Each time the protocol succeeded, the beacon emitted a pulse of 512 bits of traceable randomness. The bits are certified to be uniform with error times actual success probability bounded by 2−64. The generation of certifiable and traceable randomness represents one of the first public services that operates with an entanglement-derived advantage over comparable classical approaches.
  • Sesquilinear pairings on elliptic curves
    17 pages.
    [ arXiv:2405.14167  ]
    show abstract
    We define sesquilinear (conjugate linear) pairings generalizing the Weil and Tate-Lichtenbaum pairings on elliptic curves. Specifically, on elliptic curves with complex multiplication by a ring R, these pairings act R-linearly (or conjugate R-linearly), with values in an R-module..
  • Reciprocity obstructions in semigroup orbits in $\text{SL}(2, \mathbb{Z})$
    With James Rickards.
    27 pages.
    [ arXiv:2401.01860 | github code ]
    show abstract
    We study orbits of semigroups of SL(2,ℤ), and demonstrate reciprocity obstructions: we show that certain such orbits avoid squares, but not as a consequence of such obstructions on the Zariski closure, and not as a consequence of congruence obstructions. This is in analogy to the reciprocity obstructions recently used to disprove the Apollonian local-global conjecture. We give an example of such an orbit which is known exactly, and misses all squares together with an explicit finite list of sporadic values: the corresponding semigroup is not thin, but its Zariski closure does not miss squares. We also demonstrate thin semigroups with reciprocity obstructions, including semigroups associated to continued fractions formed from finite alphabets. Zaremba’s conjecture states that for continued fractions with coefficients chosen from {1,…,5}, every positive integer appears as a denominator. Bourgain and Kontorovich proposed a generalization of Zaremba’s conjecture in the context of semigroups associated to finite alphabets. We disprove their conjecture. In particular, we demonstrate classes of finite continued fraction expansions which never represent rationals with square denominator, but not as a consequence of congruence obstructions, and for which the limit set has Hausdorff dimension exceeding 1/2. An example of such a class is continued fractions of the form [0;a1,a2,…,an,1,1,2], where the ai are chosen from the set {4,8,12,…,128}. The object at the heart of these results is a semigroup Ψ⊆Γ1(4) which preserves Kronecker symbols..

To appear

  • Prime and Thickened Prime Components in Apollonian Circle Packings
    With Elena Fuchs, Holley Friedlander, Piper Harris, Catherine Hsu, James Rickards, Katherine Sanden and Damaris Schindler.
    41 pages, to appear in Women in Numbers 6 — Research Directions in Number Theory (Springer AWM Series).
    [arXiv:2401.00177 ]
    show abstract
    Inspired by a question of Sarnak, we introduce the notion of a prime component in an Apollonian circle packing: a maximal tangency-connected subset having all prime curvatures. We also consider thickened prime components, which are augmented by all circles immediately tangent to the prime component. In both cases, we ask about the curvatures which appear. We consider the residue classes attained by the set of curvatures, the number of circles in such components, the number of distinct integers occurring as curvatures, and the number of prime components in a packing. As part of our investigation, we computed and analysed example components up to around curvature $10^{13}$; software is available..

Published

  • Extending class group action attacks via sesquilinear pairings
    With Joseph Macula.
    Advances in Cryptology –ASIACRYPT 2024, Springer LNCS 15486 (2021), 371-395.
    [ eprint:2024/880 | arXiv:2406.10440 | published ]
    show abstract
    We introduce a new tool for the study of isogeny-based cryptography, namely pairings which are sesquilinear (conjugate linear) with respect to the $mathcal{O}$-module structure of an elliptic curve with CM by an imaginary quadratic field $mathcal{O}$. We use these pairings to study the security of problems based on the class group action on collections of oriented ordinary or supersingular elliptic curves. This extends work of cite{attacks} and cite{Level}..
  • The Local-Global Conjecture for Apollonian circle packings is false
    With Summer Haag, Clyde Kertzer and James Rickards.
    Annals of Mathematics, 200 (2024), Issue 2, pp. 749-770
    [ arXiv:2307.02749 | published | github code | github data ]
    show abstract
    In a primitive integral Apollonian circle packing, curvatures that appear must fall into one of six or eight residue classes modulo 24. The Local-Global Conjecture states that every sufficiently large integer in one of these residue classes will appear as a curvature in the packing. We prove that this conjecture is false for many packings, by proving that certain quadratic and quartic families are missed. We then formulate a new conjecture, and give computational evidence in support of it.
    .
  • Orientations and cycles in supersingular isogeny graphs
    With Sarah Arpin, Mingjie Chen, Kristin E. Lauter, Renate Scheidler, and Ha T. N. Tran.
    Proceedings of Women in Number Theory 5 (2024), pp. 25-86.
    [     eprint:2022/562 | arXiv:2205.03976 | published ]
    show abstract
    The paper concerns several theoretical aspects of oriented supersingular l-isogeny volcanoes and their relationship to closed walks in the supersingular l-isogeny graph. Our main result is a bijection between the rims of the union of all oriented supersingular l-isogeny volcanoes over F_p-bar (up to conjugation of the orientations), and isogeny cycles (non-backtracking closed walks which are not powers of smaller walks) of the supersingular l-isogeny graph modulo p. The exact proof and statement of this bijection are made more intricate by special behaviours arising from extra automorphisms and the ramification of p in certain quadratic orders. We use the bijection to count isogeny cycles of given length in the supersingular l-isogeny graph exactly as a sum of class numbers, and also give an explicit upper bound by estimating the class numbers.
  • Factoring using multiplicative relations modulo n: a subexponential algorithm inspired by the index calculus
    Mathematical Cryptology, 3(2), 2–10 (issue for MathCrypt 2023).
    [ published | eprint:2022/1588 | arXiv:2211.06821 | github ]
    show abstract
    We demonstrate that a modification of the classical index calculus algorithm can be used to factor integers. More generally, we reduce the factoring problem to finding an overdetermined system of multiplicative relations in any factor base modulo n, where n is the integer whose factorization is sought. The algorithm has subexponential runtime exp(O( (log n)1/2 (log log n)1/2 )) (or exp(O( (log n)2/3 (log log n)2/3 )) with the addition of a number field sieve), but requires a rational linear algebra phase, which is more intensive than the linear algebra phase of the classical index calculus algorithm. The algorithm is certainly slower than the best known factoring algorithms, but is perhaps somewhat notable for its simplicity and its similarity to the index calculus.
    .
  • Orienteering with one endomorphism
    With Sarah Arpin, Mingjie Chen, Kristin E. Lauter, Renate Scheidler, and Ha T. N. Tran.
    La Matematica     (currently early online access)
    [ published | arXiv:2201.11079 | github ]
    show abstract
    In supersingular isogeny-based cryptography, the path-finding problem reduces to the endomorphism ring problem. Can path-finding be reduced to knowing just one endomorphism? It is known that a small endomorphism enables polynomial-time path-finding and endomorphism ring computation (Love-Boneh [36]). As this paper neared completion, it was shown that the endomorphism ring problem in the presence of one known endomorphism reduces to a vectorization problem (Wesolowski [54]). In this paper, we give explicit classical and quantum algorithms for path-finding to an initial curve using the knowledge of one endomorphism. An endomorphism gives an explicit orientation of a supersingular elliptic curve. We use the theory of oriented supersingular isogeny graphs and algorithms for taking ascending/descending/horizontal steps on such graphs. Although the most general runtimes are subexponential, we show that every supersingular elliptic curve has (potentially large) endomorphisms whose exposure would lead to a classical polynomial-time path-finding algorithm.
  • Algebraic Number Starscapes
    With Edmund Harriss and Steve Trettel.
    Experimental Mathematics, 31:4, 1098-1149
    [ arXiv:2008.07655 | published | accompanying website ]
    show abstract
    We study the geometry of algebraic numbers in the complex plane, and their Diophantine approximation, aided by extensive computer visualization. Motivated by these images, called algebraic starscapes, we describe the geometry of the map from the coefficient space of polynomials to the root space, focussing on the quadratic and cubic cases. The geometry describes and explains notable features of the illustrations, and motivates a geometric-minded recasting of fundamental results in the Diophantine approximation of the complex plane. The images provide a case-study in the symbiosis of illustration and research, and an entry-point to geometry and number theory for a wider audience. The paper is written to provide an accessible introduction to the study of homogeneous geometry and Diophantine approximation.
    We investigate the homogeneous geometry of root and coefficient spaces under the natural PSL(2;C) action, especially in degrees 2 and 3. We rediscover the quadratic and cubic root formulas as isometries, and determine when the map sending certain families of polynomials to their complex roots (our starscape images) are embeddings.
    We consider complex Diophantine approximation by quadratic irrationals, in terms of hyperbolic distance and the discriminant as a measure of arithmetic height. We recover the quadratic case of results of Bugeaud and Evertse, and give some geometric explanation for the dichotomy they discovered (Bugeaud, Y. and Evertse, J.-H., Approximation of complex algebraic numbers by algebraic numbers of bounded degree, Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 8 (2009), no. 2, 333-368). Our statements go a little further in distinguishing approximability in terms of whether the target or approximations lie on rational geodesics.
    The paper comes with accompanying software, and finishes with a wide variety of open problems..
  • Monogenic fields arising from trinomials
    With Ryan Ibarra, Henry Lembeck, Mohammad Ozaslan, and Hanson Smith.
    Involve – A Journal of Mathematics, 15 (2022), No. 2, 299–317.
    [ arXiv:1908.09793 | published ]
    show abstract
    We call a polynomial monogenic if a root θ has the property that Z[θ] is the full ring of integers in Q(θ). Using the Montes algorithm, we find sufficient conditions for xn+ax+b and xn+cxn−1+d to be monogenic (this was first studied by Jakhar, Khanduja, and Sangwan using other methods). Weaker conditions are given for n=5 and n=6. We also show that each of the families xn+bx+b and xn+cxn−1+cd are monogenic infinitely often and give some positive densities in terms of the coefficients.
  • Improved torsion point attacks on SIDH variants
    With Victoria de Quehen, Péter Kutas, Chris Leonardi, Chloe Martindale, Lorenz Panny, and Christophe Petit.
    Advances in Cryptology — CRYPTO 2021, Springer LNCS 12827 (2021), 432-470.
    [ published | arXiv:2005.14681 | IACR eprint 2020/633 | video | code ]
    show abstract
    SIDH is a post-quantum key exchange algorithm based on the presumed difficulty of finding isogenies between supersingular elliptic curves. However, SIDH and related cryptosystems also reveal additional information: the restriction of a secret isogeny to a subgroup of the curve (torsion point information). Petit (2017) was the first to demonstrate that torsion point information could noticeably lower the difficulty of finding secret isogenies. In particular, Petit showed that “overstretched” parameterizations of SIDH could be broken in polynomial time. However, this did not impact the security of any cryptosystems proposed in the literature. The contribution of this paper is twofold: First, we strengthen the techniques of Petit by exploiting additional information coming from a dual and a Frobenius isogeny. This extends the impact of torsion point attacks considerably. In particular, our techniques yield a classical attack that completely breaks the n-party group key exchange of Azarderakhsh et al. (2019) for 6 parties or more, and a quantum attack for 3 parties or more that improves on the best known asymptotic complexity. We also provide a Magma implementation of our attack for 6 parties. We give the full range of parameters for which our attacks apply. Second, we construct SIDH variants designed to be weak against our attacks; this includes backdoor choices of starting curve, as well as backdoor choices of base field prime. We stress that our results do not degrade the security of, or reveal any weakness in the NIST submission SIKE of Jao et al.
  • Algebraic aspects of solving Ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm
    SIAM Journal on Applied Algebra and Geometry, 5(2) (2021): pp. 366–387.
    [ published | arXiv:1902.07140 | IACR eprint 2019/183 | local pdf | code ]
    show abstract
    We provide several reductions of Ring-LWE problems to smaller Ring-LWE problems in the presence of samples of a restricted form (i.e. (a,b) such that a is restricted to a subring, or multiplicative coset of a subfield of one CRT factor). To create and exploit such restricted samples, we propose Ring-BKW, a version of the Blum-Kalai-Wasserman algorithm which respects the ring structure. It has several key advantages based on the ring structure, including smaller tables, reduced or eliminated back-substitution, and a new opportunity for parallelization. We focus on two-power cyclotomic Ring-LWE with parameters proposed for practical use, with the exception that many splitting types are considered. The orthogonality of the lattice for two-power cyclotomics is exploited. In general, higher residue degree is an advantage to attacks.
  • Local-global principles in circle packings
    with Elena Fuchs and Xin Zhang
    Compositio Mathematica, 155:6 (2019): pp. 1118-1170.
    [ arXiv:1707.06708 | published ]
    show abstract
    We generalize work of Bourgain-Kontorovich and Zhang, proving an almost
    local-to-global property for the curvatures of certain circle packings, to a
    large class of Kleinian groups. Specifically, we associate in a natural way an
    infinite family of integral packings of circles to any Kleinian group A < PSL2(K)
    satisfying certain conditions, where K is an
    imaginary quadratic field, and show that the curvatures of the circles in any
    such packing satisfy an almost local-to-global principle. A key ingredient in
    the proof of this is that A possesses a spectral gap property, which
    we prove for any infinite-covolume, geometrically finite, Zariski dense
    Kleinian group in PSL2(OK) containing a Zariski dense
    subgroup of PSL2(Z).
  • The dynamics of super-Apollonian continued fractions
    with Sneha Chaubey, Elena Fuchs and Robert Hines
    Transactions of the American Mathematical Society, 372 (2019), pp. 2287-2334.
    [ arXiv:1703.08616 | published ]
    show abstract
    We examine a pair of dynamical systems on the plane induced by a pair of spanning trees in the Cayley graph of the Super-Apollonian group of Graham, Lagarias, Mallows, Wilks and Yan. The dynamical systems compute Gaussian rational approximations to complex numbers and are ”reflective” versions of the complex continued fractions of A. L. Schmidt. They also describe a reduction algorithm for Lorentz quadruples, in analogy to work of Romik on Pythagorean triples. For these dynamical systems, we produce an invertible extension and an invariant measure, which we conjecture is ergodic. We consider some statistics of the related continued fraction expansions, and we also examine the restriction of these systems to the real line, which gives a reflective version of the usual continued fraction algorithm. Finally, we briefly consider an alternate setup corresponding to a tree of Lorentz quadruples ordered by arithmetic complexity.
  • A family of monogenic S4 quartic fields arising from elliptic curves
    with T. Alden Gassert and Hanson Smith
    Journal of Number Theory, 197 (2019): pp. 361-382.
    [ arXiv:1708.03953 | published ]
    show abstract
    We consider partial torsion fields (fields generated by a root of a division polynomial) for elliptic curves. By analysing the reduction properties of elliptic curves, and applying the Montes Algorithm, we obtain information about the ring of integers. In particular, for the partial 3-torsion fields for a certain one-parameter family of non-CM elliptic curves, we describe a power basis. As a result, we show that the one-parameter family of quartic S4 fields given by T4 − 6T2 − αT − 3 for α ϵ Z such that α ± 8 are squarefree, are monogenic.
  • The Apollonian structure of Bianchi groups
    Transactions of the American Mathematical Society, 370 (2018), pp. 6169-6219.
    [ arXiv:1505.03121 | published ]
    show abstract
    We study the orbit of the extended real line under the Bianchi group PSL_2(OK), where K is an imaginary quadratic field. The orbit SK, called a Schmidt arrangement, is a geometric realisation, as an intricate circle packing, of the arithmetic of K. We define certain natural subgroups whose orbits generalise Apollonian circle packings, and show that SK, considered with orientations, is a disjoint union of all of these K-Apollonian packings. These packings define a new class of thin groups called K-Apollonian groups. We make a conjecture on the curvatures of these packings, generalizing the local-to-global conjecture of Apollonian circle packings.
  • Attacks on the Search RLWE Problem with Small Errors
    with Hao Chen and Kristin Lauter
    SIAM Journal on Applied Algebra and Geometry, 1-1 (2017): pp. 665-682.
    [ IACR eprint 2015/971 | published ]
    show abstract
    We describe a new attack on the Search Ring Learning-With-Errors (RLWE) problem based on the chi-square statistical test, and give examples of RLWE instances in Galois number fields which are vulnerable to our attack. We prove a search-to-decision reduction for Galois fields which applies for any unramified prime modulus q, regardless of the residue degree f of q, and we use this in our attacks. The time complexity of our attack is O(q^{2f}), where f is the residue degree of q in K.We also show an attack on the RLWE problem in general cyclotomic rings (non 2-power cyclotomic rings) which works when the modulus is a ramified prime. We demonstrate the attacks in practice by finding many vulnerable instances and successfully attacking them. We include the code for all attacks.
  • Visualizing the arithmetic of quadratic imaginary fields
    International Mathematics Research Notices 2018:12 (2018), 3908–3938.
    [ arXiv:1410.0417 | published | free access link ]
    show abstract
    We study the orbit of the real line under the Bianchi group PSL_2(OK), where K is an imaginary quadratic field. The orbit, called a Schmidt arrangement, is a geometric realisation, as an intricate circle packing, of the arithmetic of K. This paper presents several examples of this phenomenon. First, we show that the curvatures of the circles are integer multiples of √-Δ and describe the curvatures of tangent circles in terms of the norm form of OK. Second, we show that the circles themselves are in bijection with certain ideal classes in orders of OK, the conductor being a certain multiple of the curvature. This allows us to count circles with class numbers. Third, we show that the arrangement of circles is connected if and only if OK is Euclidean. These results are meant as foundational for a study of a new class of thin groups generalising Apollonian groups, in a companion paper.
  • Security Considerations for Galois Non-dual RLWE Families
    with Hao Chen and Kristin Lauter
    Selected Areas in Cryptography 2016 — SAC 2016, LNCS vol 10532, pp. 443-462.
    [ IACR eprint 2016/193 | published ]
    show abstract
    This paper makes several improvements to the number theoretical attacks on RLWE presented in recent papers of Chen-Lauter-Stange and Elias-Lauter-Ozman-Stange, including presenting an infinite family of Galois number fields vulnerable to attack, a substantial runtime improvement, and an analysis of the security of cyclotomic fields.
  • Index divisibility in dynamical sequences and cyclic orbits modulo p
    with Annie S. Chen and T. Alden Gassert
    New York Journal of Mathematics, 23 (2017), pp. 1045-1063.
    [ arXiv:1608.02177 | published ]
    show abstract
    Let φ(x) =xd+c be an integral polynomial of degree at least 2, and consider the sequence (φn(0))n=0∞, which is the orbit of 0 under iteration by φ. Let Dd,c denote the set of positive integers n for which n divides φn(0). We give a characterization of Dd,c in terms of a directed graph and describe a number of its properties, including its cardinality and the primes contained therein. In particular, we study the question of which primes p have the property that the orbit of 0 is a single p-cycle modulo p. We show that the set of such primes is finite when d is even, and conjecture that it is infinite when d is odd.
  • The sensual Apollonian circle packing
    Expositiones Mathematicae, 34-4 (2016), 364-395.
    [ arXiv:1208.4836 | published ]
    show abstract
    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.
  • RLWE Cryptography for the Number Theorist
    with Yara Elias, Kristin E. Lauter, and Ekin Ozman
    Women in Numbers 3: Research Directions in Number Theory Springer AWM Series, Vol. 3 (2016), 271-290.
    [ IACR eprint 2015/758 | arXiv:1508.01375 | published ]
    show abstract
    In this paper, we survey the status of attacks on the ring and polynomial learning with errors problems (RLWE and PLWE). Recent work on the security of these problems [EHL, ELOS] gives rise to interesting questions about number fields. We extend these attacks and survey related open problems in number theory, including spectral distortion of an algebraic number and its relationship to Mahler measure, the monogenic property for the ring of integers of a number field, and the size of elements of small order modulo q.
  • Integral points on elliptic curves and explicit valuations of division polynomials
    Canadian Journal of Mathematics, 68 (2016), 1120-1158.
    [ arXiv:1108.3051 | published ]
    show abstract
    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.
  • Provably weak instances of Ring-LWE
    with Yara Elias, Kristin E. Lauter, and Ekin Ozman.
    Advances in Cryptology — CRYPTO 2015, Springer LNCS 9215 (2015), 63-92.
    [ arXiv:1502.03708 | published ]
    show abstract
    The ring and polynomial learning with errors problems (Ring-LWE and Poly-LWE) have been proposed as hard problems to form the basis for cryptosystems, and various security reductions to hard lattice problems have been presented. So far these problems have been stated for general (number) rings but have only been closely examined for cyclotomic number rings. In this paper, we state and examine the Ring-LWE problem for general number rings and demonstrate provably weak instances of Ring-LWE. We construct an explicit family of number fields for which we have an efficient attack. We demonstrate the attack in both theory and practice, providing code and running times for the attack. The attack runs in time linear in q, where q is the modulus. Our attack is based on the attack on Poly-LWE which was presented in [Eisenträger-Hallgren-Lauter].
    We extend the attack EHL-attack to apply to a larger class of number fields, and show how it applies to attack Ring-LWE for a heuristically large class of fields. Certain Ring-LWE instances can be transformed into Poly-LWE instances without distorting the error too much, and thus provide the first weak instances of the Ring-LWE problem. We also provide additional examples of fields which are vulnerable to our attacks on Poly-LWE, including power-of-2 cyclotomic fields, presented using the minimal polynomial of ζ2n +/- 1.
  • A duality principle for selection games
    with Lionel Levine and Scott Sheffield
    Proceedings of the American Mathematical Society, 141 (2013), 4349-4356.
    [ arXiv:1110.2712 | published ]
    show abstract
    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.
    [ arXiv:1104.0961 | published | computer scripts ]
    show abstract
    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.
  • Character sums with division polynomials
    with Igor E. Shparlinski
    Canadian Mathematical Bulletin, 55 (2012), 850-857.
    [ arXiv:0912.5246 | published ]
    show abstract
    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.
  • Amicable pairs and aliquot cycles for elliptic curves
    with Joseph H. Silverman.
    Experimental Mathematics, 20-3 (2011), 329-357.
    [ arXiv:0912.1831| published | related website ]
    show abstract
    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.
  • Terms in elliptic divisibility sequences divisible by their indices
    with Joseph H. Silverman
    Acta Arithmetica, 146 (2011), 355-378.
    [ arXiv:1001.5303 | published ]
    show abstract
    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 nets and elliptic curves
    Algebra and Number Theory, 5-2 (2011), 197-229.
    [ arXiv:0710.1316 | published | errata ]
    show abstract
    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.
  • 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.
    [ IACR eprint 2008/099 | arXiv:0803.0728 | published ]
    show abstract
    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.
    [ IACR eprint 2006/392 | published ]
    show abstract
    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.

Older Preprints

  • An arborist’s guide to the rationals
    Under revision, 7 pages.
    [ arXiv:1403.2928 ]
    show abstract
    There are two well-known ways to enumerate the positive rational numbers in an infinite binary tree: the Farey/Stern-Brocot tree and the Calkin-Wilf tree. In this brief note, we describe these two trees as `transpose shadows’ of a tree of matrices (a result due to Backhouse and Ferreira) via a new proof using yet another famous tree of rationals: the topograph of Conway and Fung.
  • General Zelevinsky Algebras
    with Peter Hoffman and Chris Wooff
    Under revision, 23 pages.
    [ pdf ]
    show abstract
    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.

Pedagogical Articles

  • Standards Based Grading in an Introduction to Abstract Mathematics
    To appear in PRIMUS: Problems, Resources and Issues in Mathematics Undergraduate Studies, 27 pages plus appendices.
    [ pdf | published ]
    show abstract
    Standards-based grading, in which grading should be designed to communicate to students their current level of mastery with regards to well-articulated standards, is becoming popular at the K-12 level. As yet, the literature addressing standards-based grading at the university level is scarce. In this paper, I document my attempts to put into practice the principles of standards based grading in a lower-level undergraduate mathematics course which aims to introduce mathematical proof.

Expositional Publications

  • An illustrated introduction to the arithmetic of Apollonian circle packings, continued fractions and other thin orbits
    [ arXiv:comingsoon | current draft ]
    show abstract
    These notes cover and expand upon the material for two summer schools: The first, which was held at CIRM, Marseille, France, July 10-14, 2023, as part of Renormalization and Visualization for packing, billiard and surfaces, was titled Number theory as a door to geometry, dynamics and illustration. The second was held at NSU IMS in Singapore, June 3-7, 2024, as part of Computational Aspects of Thin Groups, and was titled Integral packings and number theory. Both courses were put together by a number theorist for students and researchers in other fields. They cover a web of ideas relating to Apollonian circle packings, integral orbits, thin groups, hyperbolic geometry, continued fractions, and Diophantine approximation. The connection of geometry and dynamics to number theory gives an opportunity to illustrate arithmetic by appealing to our visual intuition.
  • On the importance of illustration in mathematical research
    With Rémi Coulon, Gabriel Dorfsman-Hopkins, Edmund Harriss, Martin Skrodzki, and Glen Whitney
    Notices of the American Mathematical Society, January 2024.
    [ arXiv:2307.04636 | published ]
    show abstract
    Mathematical understanding is built in many ways. Among these, illustration has been a companion and tool for research for as long as research has taken place. We use the term illustration to encompass any way one might bring a mathematical idea into physical form or experience, including hand-made diagrams or models, computer visualization, 3D printing, and virtual reality, among many others. The very process of illustration itself challenges our mathematical understanding and forces us to answer questions we may not have posed otherwise. It can even make mathematics an experimental science, in which immersive exploration of data and representations drive the cycle of problem, conjecture, and proof. Today, modern technology for the first time places the production of highly complicated models within the reach of many individual mathematicians. Here, we sketch the rich history of illustration, highlight important recent examples of its contribution to research, and examine how it can be viewed as a discipline in its own right.
  • The ingenious physical factoring devices of D. N. Lehmer
    Math Horizons, 30:2 (2022), pp. 8-11.
    [ published ]
    show abstract
    A short article about factor stencils and other physical factoring devices.
  • The Farey structure of the Gaussian integers
    Asia Pacific Math Newsletter, (6)2, 2016, pp. 10-14.
    [ published ]
    show abstract
    This is a short four-page general exposition of the analogy between the Gaussian Schmidt arrangement and the Farey fractions, and their connections to hyperbolic geometry.
  • An illustration in number theory (2019 Lecture Sampler)
    Notices of the American Mathematical Society, 66(03), 2019, pp. 411-413.
    [ published ]
    show abstract
    This is an overview of my invited talk at the AMS Joint Central/Western Sectional in March 2019.

Ph.D. Thesis

  • Elliptic nets and elliptic curves
    Ph.D. Thesis, Brown University, 2008, 297 pages including computer code and errors.
    [ pdf | Brown library ]
    show abstract
    The sequence of division polynomials for an elliptic curve satisfies a non-linear recurrence relation. Specialising to a chosen elliptic curve and evaluating at a chosen point gives a recurrence sequence in the field over which curve and point are defined. In the field of rational numbers, Morgan Ward showed in 1948 that all sequences satisfying this particular recurrence relation arise from division polynomials. These are called elliptic divisibility sequences. In this thesis, we define a higher rank generalisation of elliptic divisibility sequences called elliptic nets. To do so, we define rational functions called net polynomials in analogy to division polynomials. For any integer n, we define a collection of such net polynomials in n variables indexed by n-tuples of integers; for n=1, one obtains the division polynomials. This collection satisfies a certain non-linear recurrence relation. Any array satisfying this relation is called an elliptic net. The evaluation of the array of functions at a curve and n-tuple of points gives an elliptic net with values in K. Conversely, any elliptic net over K arises from the net polynomials evaluated at some elliptic curve and tuple of points. In this thesis, we make precise the correspondence between elliptic curves and elliptic nets, over arbitrary fields. We describe the Laurentness properties of elliptic nets, and generalise the `symmetry properties’ observed by Morgan Ward and others. It is shown that the Poincaré biextension of an elliptic curve crossed with itself has a factor system given by the net polynomials. As a consequence, the Tate-Lichtenbaum and Weil pairings for an elliptic curve have a description in terms of elliptic nets. This leads to a new algorithm for computing these pairings by computing terms of elliptic nets. The complexity of this algorithm is examined. Finally, some hard computational problems for elliptic nets are related to the elliptic curve discrete logarithm problem over finite fields, with a view toward cryptographic security.

Unpublish(ed/able) Notes

  • Frobenius and the endomorphism ring of j=1728
    [ pdf ]
    show abstract
    We give the endomorphism ring of the supersingular elliptic curve with j=1728, and show that although the endomorphism ring is invariant under isomorphism of the curve, the placement of Frobenius in that endomorphism ring is not.
  • Quadratic forms, lattices and ideal classes
    [ pdf ]
    show abstract
    A concise treatment of the bijection between imaginary quadratic ideal classes and positive definite integral binary quadratic forms.
  • Formulary for elliptic divisibility sequences and elliptic nets
    [ pdf ]
    show abstract
    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.
  • Notes on the spin homomorphism with Yongqi Feng
    [ pdf ]
    show abstract
    Expositional notes for Apollonian Circle Packings, 23–27 June, 2014, Mittag-Leffler.
  • Notes on Bhargava’s composition laws
    [ pdf ]
    show abstract
    Expositional notes for a seminar.