BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Katherine E. Stange

Katherine E. Stange appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.NTmath.AGCryptography and Securitymath.COComputer Science and Game Theorymath.MGmath.DGmath.DSmath.GR

Catalog footprint

What is connected

19works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

19 published item(s)

preprint2022arXiv

Algebraic Number Starscapes

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 $\operatorname{PSL}(2;\mathbb{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.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Monogenic fields arising from trinomials

We call a polynomial monogenic if a root $θ$ has the property that $\mathbb{Z}[θ]$ is the full ring of integers in $\mathbb{Q}(θ)$. Consider the two families of trinomials $x^n + ax + b$ and $x^n + cx^{n-1} + d$. For any $n>2$, we show that these families are monogenic infinitely often and give some positive densities in terms of the coefficients. When $n=5$ or 6 and when a certain factor of the discriminant is square-free, we use the Montes algorithm to establish necessary and sufficient conditions for monogeneity, illuminating more general criteria given by Jakhar, Khanduja, and Sangwan using other methods. Along the way we remark on the equivalence of certain aspects of the Montes algorithm and Dedekind's index criterion.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Algebraic aspects of solving Ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm

We provide a reduction of the Ring-LWE problem to Ring-LWE problems in subrings, in the presence of samples of a restricted form (i.e. $(a,b)$ such that $a$ is restricted to a multiplicative coset of the subring). To create and exploit such restricted samples, we propose Ring-BKW, a version of the Blum-Kalai-Wasserman algorithm which respects the ring structure. Off-the-shelf BKW dimension reduction (including coded-BKW and sieving) can be used for the reduction phase. Its primary advantage is that there is no need for back-substitution, and the solving/hypothesis-testing phase can be parallelized. We also present a method to exploit symmetry to reduce table sizes, samples needed, and runtime during the reduction phase. The results apply to two-power cyclotomic Ring-LWE with parameters proposed for practical use (including all splitting types).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Arithmetic properties of the Frobenius traces defined by a rational abelian variety (with two appendices by J-P. Serre)

Let $A$ be an abelian variety over $\mathbb{Q}$ of dimension $g$ such that the image of its associated absolute Galois representation $ρ_A$ is open in $\operatorname{GSp}_{2g}(\hat{\mathbb{Z}})$. We investigate the arithmetic of the traces $a_{1, p}$ of the Frobenius at $p$ in $\operatorname{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})$ under $ρ_A$, modulo varying primes $p$. In particular, we obtain upper bounds for the counting function $\#\{p \leq x: a_{1, p} = t\}$ and we prove an Erdös-Kac type theorem for the number of prime factors of $a_{1, p}$. We also formulate a conjecture about the asymptotic behaviour of $\#\{p \leq x: a_{1, p} = t\}$, which generalizes a well-known conjecture of S. Lang and H. Trotter from 1976 about elliptic curves.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Index Divisibility in Dynamical Sequences and Cyclic Orbits Modulo $p$

Let $ϕ(x) = x^d + c$ be an integral polynomial of degree at least 2, and consider the sequence $(ϕ^n(0))_{n=0}^\infty$, which is the orbit of $0$ under iteration by $ϕ$. Let $D_{d,c}$ denote the set of positive integers $n$ for which $n \mid ϕ^n(0)$. We give a characterization of $D_{d,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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Provably weak instances of Ring-LWE

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 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 $ζ_{2^n} \pm 1$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Ring-LWE Cryptography for the Number Theorist

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 [Eisenträger-Hallgren-Lauter, Elias-Lauter-Ozman-Stange] 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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Apollonian structure of Bianchi groups

We study the orbit of $\widehat{\mathbb{R}}$ under the Möbius action of the Bianchi group $\operatorname{PSL}_2(\mathcal{O}_K)$ on $\widehat{\mathbb{C}}$, where $\mathcal{O}_K$ is the ring of integers of an imaginary quadratic field $K$. The orbit $\mathcal{S}_K$, called a Schmidt arrangement, is a geometric realisation, as an intricate circle packing, of the arithmetic of $K$. We give a simple geometric characterisation of certain subsets of $\mathcal{S}_K$ generalizing Apollonian circle packings, and show that $\mathcal{S}_K$, considered with orientations, is a disjoint union of all primitive integral such $K$-Apollonian packings. These packings are described by a new class of thin groups of arithmetic interest called $K$-Apollonian groups. We make a conjecture on the curvatures of these packings, generalizing the local-to-global conjecture for Apollonian circle packings.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Integral points on elliptic curves and explicit valuations of division polynomials

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 Neron 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 h(P)/h(E) for integer points having two large integral multiples.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The sensual Apollonian circle packing

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A duality principle for selection games

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Algebraic divisibility sequences over function fields

We study the existence of primes and of primitive divisors in classical divisibility sequences defined over function fields. Under various hypotheses, we prove that Lucas sequences and elliptic divisibility sequences over function fields defined over number fields contain infinitely many irreducible elements. We also prove that an elliptic divisibility sequence over a function field has only finitely many terms lacking a primitive divisor.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Character sums with division polynomials

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 $q^{1/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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

How to make the most of a shared meal: plan the last bite first

If you are sharing a meal with a companion, how best to make sure you get your favourite mouthfuls? 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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Elliptic nets and elliptic curves

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 P_1, ..., P_n 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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Terms in elliptic divisibility sequences divisible by their indices

Let D = (D_n)_{n\ge1} be an elliptic divisibility sequence. We study the set S(D) of indices n satisfying n | D_n. 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 D_n, 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.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Amicable pairs and aliquot cycles for elliptic curves

An amicable pair for an elliptic curve E/Q is a pair of primes (p,q) of good reduction for E satisfying #E(F_p) = q and #E(F_q) = 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(F_P) is prime. This is especially intricate for the family of curves with j = 0.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

The elliptic curve discrete logarithm problem and equivalent hard problems for elliptic divisibility sequences

We define three hard problems in 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-Rück and Shipsey EDS attacks on the elliptic curve discrete logarithm problem in the cases where these apply.

0 citations0 reviewsNo code linkedOpen access