Top

2008 | Book

Read chapter Read first chapter

Algorithmic Number Theory

8th International Symposium, ANTS-VIII Banff, Canada, May 17-22, 2008 Proceedings

Editors: Alfred J. van der Poorten, Andreas Stein

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

About this book

This book constitutes the refereed proceedings of the 8th International Algorithmic Number Theory Symposium, ANTS 2008, held in Banff, Canada, in May 2008. The 28 revised full papers presented together with 2 invited papers were carefully reviewed and selected for inclusion in the book. The papers are organized in topical sections on elliptic curves cryptology and generalizations, arithmetic of elliptic curves, integer factorization, K3 surfaces, number fields, point counting, arithmetic of function fields, modular forms, cryptography, and number theory.

Frontmatter

Invited Papers

Running Time Predictions for Factoring Algorithms

Abstract

In 1994, Carl Pomerance proposed the following problem:

Select integers a₁,a₂,...,a_J at random from the interval [1,x], stopping when some (non-empty) subsequence, { a_i: i ∈ I} where I ⊆ { 1,2,...,J}, has a square product (that is $\prod_{i\in I} a_i\in \mathbb Z^2$). What can we say about the possible stopping times, J?

A 1985 algorithm of Schroeppel can be used to show that this process stops after selecting (1 + ε)J ₀(x) integers a _j with probability 1 − o(1) (where the function J ₀(x) is given explicitly in (1) below. Schroeppel’s algorithm actually finds the square product, and this has subsequently been adopted, with relatively minor modifications, by all factorers. In 1994 Pomerance showed that, with probability 1 − o(1), the process will run through at least $J_0(x)^{1-o(1)}$ integers a _j, and asked for a more precise estimate of the stopping time. We conjecture that there is a “sharp threshold” for this stopping time, that is, with probability 1 − o(1) one will first obtain a square product when (precisely) $\{e^{-\gamma}+o(1)\} J_0(x)$ integers have been selected. Herein we will give a heuristic to justify our belief in this sharp transition.

Ernie Croot, Andrew Granville, Robin Pemantle, Prasad Tetali

A New Look at an Old Equation

Abstract

The general binary quadratic Diophantine equation

$$ ax^2 + bxy + cy^2 + dx + ey + f = 0 $$

was first solved by Lagrange over 200 years ago. Since that time little improvement has been made to Lagrange’s technique. In this paper we show how to reduce this problem to that of determining whether or not an ideal of a certain quadratic order is principal and if so exhibiting a generator of that ideal. In the difficult case of the discriminant $\ensuremath{\Delta}$ of this order being positive, we develop a Las Vegas algorithm for solving the principal ideal problem that executes in expected time bounded by $O(\ensuremath{\Delta}^{1/6 + \epsilon})$, whereas the complexity of Lagrange’s (unconditional) technique for solving this problem is $O(\ensuremath{\Delta}^{1/2 + \epsilon})$.

R. E. Sawilla, A. K. Silvester, H. C. Williams

Elliptic Curves Cryptology and Generalizations

Abelian Varieties with Prescribed Embedding Degree

Abstract

We present an algorithm that, on input of a CM-field K, an integer k ≥ 1, and a prime $r\equiv1\bmod k$, constructs a q-Weil number $\pi\in\O_K$ corresponding to an ordinary, simple abelian variety A over the field

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_3/MediaObjects/978-3-540-79456-1_3_IEq3_HTML.png

of q elements that has an

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_3/MediaObjects/978-3-540-79456-1_3_IEq4_HTML.png

-rational point of order r and embedding degree k with respect to r. We then discuss how CM-methods over K can be used to explicitly construct A.

David Freeman, Peter Stevenhagen, Marco Streng

Almost Prime Orders of CM Elliptic Curves Modulo p

Abstract

Given an elliptic curve over $\mathbb Q$ with complex multiplication by ${\mathcal O}_K$, the ring of integers of the quadratic imaginary field K, we analyze the integer d _E =gcd$\{|E(\mathbb F_p)|:p$ splits in ${\mathcal O}_K\}$, where $|E(\mathbb F_p)|$ is the size of the group of rational $\mathbb F_p$ points, and prove that it can be bigger than the common factor that comes from the torsion of the curve. Then, we prove that #{p ≤ x, p splits in ${{\mathcal O}_K}:{\frac {1}{d_E}}|{\it E}({\mathbb F}_{p})|=P_2\}\gg {\it x}/(\log x)^2$ hence extending the results in [16]. This is the best known result in the direction of the Koblitz conjecture about the primality of $|E(\mathbb F_p)|$.

Jorge Jiménez Urroz

Efficiently Computable Distortion Maps for Supersingular Curves

Abstract

Efficiently computable distortion maps are useful in cryptography. Galbraith-Pujolàs-Ritzenthaler-Smith [6] considered them for supersingular curves of genus 2. They showed that there exists a distortion map in a specific set of efficiently computable endomorphisms for every pair of nontrivial divisors under some unproven assumptions for two types of curves. In this paper, we prove that this result holds using a different method without these assumptions for both curves with r > 5 and r > 19 respectively, where r is the prime order of the divisors. In other words, we solve an open problem in [6]. Moreover, we successfully generalize this result to the case C : Y² = X^2g + 1 + 1 over ${\mathbb F}_p$ for anyg s.t. 2g + 1 is prime. In addition, we provide explicit bases of Jac_C[r] with a new property that seems interesting from the cryptographic viewpoint.

Katsuyuki Takashima

On Prime-Order Elliptic Curves with Embedding Degrees k = 3, 4, and 6

Abstract

We further analyze the solutions to the Diophantine equations from which prime-order elliptic curves of embedding degrees k = 3,4 or 6 (MNT curves) may be obtained. We give an explicit algorithm to generate such curves. We derive a heuristic lower bound for the number E(z) of MNT curves with k = 6 and discriminant D ≤ z, and compare this lower bound with experimental data.

Koray Karabina, Edlyn Teske

Arithmetic of Elliptic Curves

Computing in Component Groups of Elliptic Curves

Abstract

Let K be a p-adic local field and E an elliptic curve defined over K. The component group of E is the group E(K)/E ⁰(K), where E ⁰(K) denotes the subgroup of points of good reduction; this is known to be finite, cyclic if E has multiplicative reduction, and of order at most 4 if E has additive reduction. We show how to compute explicitly an isomorphism

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_7/MediaObjects/978-3-540-79456-1_7_IEq1_HTML.png

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_7/MediaObjects/978-3-540-79456-1_7_IEq2_HTML.png

J. E. Cremona

Some Improvements to 4-Descent on an Elliptic Curve

Abstract

The theory of 4-descent on elliptic curves has been developed in the PhD theses of Siksek [18], Womack [21] and Stamminger [20]. Prompted by our use of 4-descent in the search for generators of large height on elliptic curves of rank at least 2, we explain how to cut down the number of class group and unit group calculations required, by using the group law on the 4-Selmer group.

Tom Fisher

Computing a Lower Bound for the Canonical Height on Elliptic Curves over Totally Real Number Fields

Abstract

Computing a lower bound for the canonical height is a crucial step in determining a Mordell–Weil basis of an elliptic curve. This paper presents a new algorithm for computing such lower bound, which can be applied to any elliptic curves over totally real number fields. The algorithm is illustrated via some examples.

Thotsaphon Thongjunthug

Faster Multiplication in GF(2)[x]

Abstract

In this paper, we discuss an implementation of various algorithms for multiplying polynomials in

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_10/MediaObjects/978-3-540-79456-1_10_IEq1_HTML.png

: variants of the window methods, Karatsuba’s, Toom-Cook’s, Schönhage’s and Cantor’s algorithms. For most of them, we propose improvements that lead to practical speedups.

Richard P. Brent, Pierrick Gaudry, Emmanuel Thomé, Paul Zimmermann

Integer Factorization

Predicting the Sieving Effort for the Number Field Sieve

Abstract

We present a new method for predicting the sieving effort for the number field sieve (NFS) in practice. This method takes relations from a short sieving test as input and simulates relations according to this test. After removing singletons, we decide how many relations we need for the factorization according to the simulation and this gives a good estimate for the real sieving. Experiments show that our estimate is within 2 % of the real data.

Willemien Ekkelkamp

Improved Stage 2 to P ± 1 Factoring Algorithms

Abstract

Some implementations of stage 2 of the P–1 method of factorization use convolutions. We describe a space-efficient implementation, allowing convolution lengths around 2²³ and stage 2 limit around 10¹⁶ while attempting to factor 230-digit numbers on modern PC’s. We describe arithmetic algorithms on reciprocal polynomials. We present adjustments for the P+1 algorithm. We list some new findings.

Peter L. Montgomery, Alexander Kruppa

K3 Surfaces

Shimura Curve Computations Via K3 Surfaces of Néron–Severi Rank at Least 19

Abstract

In [E1] we introduced several computational challenges concerning Shimura curves, and some techniques to partly address them. The challenges are: obtain explicit equations for Shimura curves and natural maps between them; determine a Schwarzian equation on each curve (a.k.a. Picard-Fuchs equation, a linear second-order differential equation with a basis of solutions whose ratio inverts the quotient map from the upper half-plane to the curve); and locate CM (complex multiplication) points on the curves. We identified some curves, maps, and Schwarzian equations using the maps’ ramification behavior; located some CM points as images of fixed points of involutions; and conjecturally computed others by numerically solving the Schwarzian equations.

Noam D. Elkies

K3 Surfaces of Picard Rank One and Degree Two

Abstract

We construct explicit examples of K3 surfaces over

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_14/MediaObjects/978-3-540-79456-1_14_IEq1_HTML.png

which are of degree 2 and geometric Picard rank 1. We construct, particularly, examples of the form $w^2 = \det M$ where M is a (3 ×3)-matrix of ternary quadratic forms.

Andreas-Stephan Elsenhans, Jörg Jahnel

Number Fields

Number Fields Ramified at One Prime

Abstract

For G a finite group and p a prime, a G-p field is a Galois number field K with $\mbox{Gal}(K/{\bf Q}) \cong G$ and $\mbox{disc}(K) = \pm p^{a}$ for some a. We study the existence of G-p fields for fixed G and varying p.

John W. Jones, David P. Roberts

An Explicit Construction of Initial Perfect Quadratic Forms over Some Families of Totally Real Number Fields

Abstract

In this paper we construct initial perfect quadratic forms over certain families of totally real number fields

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_16/MediaObjects/978-3-540-79456-1_16_IEq1_HTML.png

. We assume that the number field

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_16/MediaObjects/978-3-540-79456-1_16_IEq2_HTML.png

is either the maximal totally real subfield of a cyclotomic field

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_16/MediaObjects/978-3-540-79456-1_16_IEq3_HTML.png

, where ${3 \not |\, n}$ is the product of distinct odd primes p ₁,..., p _k, or

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_16/MediaObjects/978-3-540-79456-1_16_IEq5_HTML.png

, where m ₁,...,m _k are pairwise relatively prime, square-free positive integers with all or all but one congruent to 1 modulo 4. These perfect forms can be used to find all perfect quadratic forms of given rank (up to equivalence and proportion) over the field

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_16/MediaObjects/978-3-540-79456-1_16_IEq6_HTML.png

by applying the generalization of Voronoi’s algorithm.

Alar Leibak

Functorial Properties of Stark Units in Multiquadratic Extensions

Abstract

The goal of this paper is to present computations investigating the “functorial” properties of Stark units, that is, how specific roots of Stark units from certain subfields of a top field are placed with respect to the top field and how these roots relate to the Stark unit in the top field. This type of question is of particular relevance to gaining a better understanding of the somewhat mysterious “abelian condition” in Stark’s Conjecture.

Jonathan W. Sands, Brett A. Tangedal

Enumeration of Totally Real Number Fields of Bounded Root Discriminant

Abstract

We enumerate all totally real number fields F with root discriminant δ _F ≤ 14. There are 1229 such fields, each with degree

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_18/MediaObjects/978-3-540-79456-1_18_IEq1_HTML.png

John Voight

Point Counting

Computing Hilbert Class Polynomials

Abstract

We present and analyze two algorithms for computing the Hilbert class polynomial H _D. The first is a p-adic lifting algorithm for inert primes p in the order of discriminant D < 0. The second is an improved Chinese remainder algorithm which uses the class group action on CM-curves over finite fields. Our run time analysis gives tighter bounds for the complexity of all known algorithms for computing H _D, and we show that all methods have comparable run times.

Juliana Belding, Reinier Bröker, Andreas Enge, Kristin Lauter

Computing Zeta Functions in Families of C a,b Curves Using Deformation

Abstract

We apply deformation theory to compute zeta functions in a family of C _a,b curves over a finite field of small characteristic. The method combines Denef and Vercauteren’s extension of Kedlaya’s algorithm to C _a,b curves with Hubrechts’ recent work on point counting on hyperelliptic curves using deformation. As a result, it is now possible to generate C _a,b curves suitable for use in cryptography in a matter of minutes.

Wouter Castryck, Hendrik Hubrechts, Frederik Vercauteren

Computing L-Series of Hyperelliptic Curves

Abstract

We discuss the computation of coefficients of the L-series associated to a hyperelliptic curve over ℚ of genus at most 3, using point counting, generic group algorithms, and p-adic methods.

Kiran S. Kedlaya, Andrew V. Sutherland

Point Counting on Singular Hypersurfaces

Abstract

Let q = p ^r be a prime power. Let

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_22/MediaObjects/978-3-540-79456-1_22_IEq1_HTML.png

be a homogenous polynomial of degree d. Let

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_22/MediaObjects/978-3-540-79456-1_22_IEq2_HTML.png

be the hypersurface defined by

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_22/MediaObjects/978-3-540-79456-1_22_IEq3_HTML.png

. A natural question to ask is how to determine

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_22/MediaObjects/978-3-540-79456-1_22_IEq4_HTML.png

Recently, several algorithms were presented that calculate

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_22/MediaObjects/978-3-540-79456-1_22_IEq5_HTML.png

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_22/MediaObjects/978-3-540-79456-1_22_IEq6_HTML.png

is a smooth hypersurface. We would like to investigate whether these algorithms extend to singular hypersurfaces.

Remke Kloosterman

Arithmetic of Function Fields

Efficient Hyperelliptic Arithmetic Using Balanced Representation for Divisors

Abstract

We discuss arithmetic in the Jacobian of a hyperelliptic curve C of genus g. The traditional approach is to fix a point P _∞ ∈ C and represent divisor classes in the form E − d(P _∞) where E is effective and 0 ≤ d ≤ g. We propose a different representation which is balanced at infinity. The resulting arithmetic is more efficient than previous approaches when there are 2 points at infinity.

Steven D. Galbraith, Michael Harrison, David J. Mireles Morales

Tabulation of Cubic Function Fields with Imaginary and Unusual Hessian

Abstract

We give a general method for tabulating all cubic function fields over

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_24/MediaObjects/978-3-540-79456-1_24_IEq1_HTML.png

whose discriminant D has odd degree, or even degree such that the leading coefficient of − 3D is a non-square in

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_24/MediaObjects/978-3-540-79456-1_24_IEq2_HTML.png

, up to a given bound on $|D| = q^{\deg(D)}$. The main theoretical ingredient is a generalization of a theorem of Davenport and Heilbronn to cubic function fields. We present numerical data for cubic function fields over

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_24/MediaObjects/978-3-540-79456-1_24_IEq4_HTML.png

and over

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_24/MediaObjects/978-3-540-79456-1_24_IEq5_HTML.png

with $\deg(D) \leq 7$ and $\deg(D)$ odd in both cases.

Pieter Rozenhart, Renate Scheidler

Modular Forms

Computing Hilbert Modular Forms over Fields with Nontrivial Class Group

Abstract

We exhibit an algorithm for the computation of Hilbert modular forms over an arbitrary totally real number field of even degree, extending results of the first author. We present some new instances of the conjectural Eichler-Shimura construction for totally real number fields over the fields ${\mathbb{Q}}(\sqrt{10})$ and ${\mathbb{Q}}(\sqrt{85})$ and their Hilbert class fields, and in particular some new examples of modular abelian varieties with everywhere good reduction over those fields.

Lassina Dembélé, Steve Donnelly

Hecke Operators and Hilbert Modular Forms

Abstract

Let F be a real quadratic field with ring of integers ${\mathcal O}$ and with class number 1. Let Γ be a congruence subgroup of ${\mathrm{GL}}_{2} ({\mathcal O})$. We describe a technique to compute the action of the Hecke operators on the cohomology $H^{3} (\Gamma; {\mathbb C})$. For F real quadratic this cohomology group contains the cuspidal cohomology corresponding to cuspidal Hilbert modular forms of parallel weight 2. Hence this technique gives a way to compute the Hecke action on these Hilbert modular forms.

Paul E. Gunnells, Dan Yasaki

Cryptography

A Birthday Paradox for Markov Chains, with an Optimal Bound for Collision in the Pollard Rho Algorithm for Discrete Logarithm

Abstract

We show a Birthday Paradox for self-intersections of Markov chains with uniform stationary distribution. As an application, we analyze Pollard’s Rho algorithm for finding the discrete logarithm in a cyclic group G and find that, if the partition in the algorithm is given by a random oracle, then with high probability a collision occurs in $\Theta(\sqrt{|G|})$ steps. This is the first proof of the correct bound which does not assume that every step of the algorithm produces an i.i.d. sample from G.

Jeong Han Kim, Ravi Montenegro, Yuval Peres, Prasad Tetali

An Improved Multi-set Algorithm for the Dense Subset Sum Problem

Abstract

Given sets L ₁, ..., L _k of elements from

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_28/MediaObjects/978-3-540-79456-1_28_IEq1_HTML.png

, the k-set birthday problem is to find an element from each list such that their sum is 0 modulo m. We give a new analysis of the algorithm in [16], proving that it returns a solution with high probability. By the work of Lyubashevsky [10], we get as an immediate corollary an improved algorithm for the random modular subset sum problem. Assuming the modulus $m = 2^{n^{\epsilon}}$ for

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_28/MediaObjects/978-3-540-79456-1_28_IEq3_HTML.png

, this problem is now solvable using time and space

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-79456-1_28/MediaObjects/978-3-540-79456-1_28_Equa_HTML.png

Andrew Shallue

Number Theory

On the Diophantine Equation x 2 + 2 α 5 β 13 γ = y n

Abstract

In this paper, we find all the solutions of the Diophantine equation x ² + 2^α 5^β 13^γ = y ⁿ in nonnegative integers x, y,α, β, γ, n ≥ 3 with x and y coprime. In fact, for n = 3, 4, 6, 8, 12, we transform the above equation into several elliptic equations written in cubic or quartic models for which we determine all their {2, 5, 13}-integer points. For n ≥ 5, we apply a method that uses primitive divisors of Lucas sequences. Again we are able to obtain several elliptic equations written in cubic models for which we find all their {2, 5, 13}-integer points. All the computations are done with MAGMA [12].

Edray Goins, Florian Luca, Alain Togbé

Non-vanishing of Dirichlet L-functions at the Central Point

Abstract

This paper deals with the matter of the non-vanishing of Dirichlet L-functions at the central point for all primitive characters χ. More precisely, S. Chowla conjectured that $L(\frac{1}{2},\chi)\not =0$, but this remains still unproved. We first give an efficient algorithm to compute the order n _χ of zero of L(s,χ) at $s=\frac{1}{2}$. This enables us to efficiently compute n _χ for L-functions with very large conductor near 10¹⁶. Then, we prove that $L(\frac{1}{2},\chi)\not =0$ for all real characters χ of modulus less than 10¹⁰. Finally we give some estimates for n _χ and the lowest zero of L(s,χ) on the critical line in terms of the conductor q.

Sami Omar

Backmatter

Title: Algorithmic Number Theory
Editors: Alfred J. van der Poorten
Andreas Stein
Publisher: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-79456-1
Print ISBN: 978-3-540-79455-4
DOI: https://doi.org/10.1007/978-3-540-79456-1

Springer Professional

About this book

Table of Contents

Frontmatter

Invited Papers

Running Time Predictions for Factoring Algorithms

A New Look at an Old Equation

Elliptic Curves Cryptology and Generalizations

Abelian Varieties with Prescribed Embedding Degree

Almost Prime Orders of CM Elliptic Curves Modulo p

Efficiently Computable Distortion Maps for Supersingular Curves

On Prime-Order Elliptic Curves with Embedding Degrees k = 3, 4, and 6

Arithmetic of Elliptic Curves

Computing in Component Groups of Elliptic Curves

Some Improvements to 4-Descent on an Elliptic Curve

Computing a Lower Bound for the Canonical Height on Elliptic Curves over Totally Real Number Fields

Faster Multiplication in GF(2)[x]

Integer Factorization

Predicting the Sieving Effort for the Number Field Sieve

Improved Stage 2 to P ± 1 Factoring Algorithms

K3 Surfaces

Shimura Curve Computations Via K3 Surfaces of Néron–Severi Rank at Least 19

K3 Surfaces of Picard Rank One and Degree Two

Number Fields

Number Fields Ramified at One Prime

An Explicit Construction of Initial Perfect Quadratic Forms over Some Families of Totally Real Number Fields

Functorial Properties of Stark Units in Multiquadratic Extensions

Enumeration of Totally Real Number Fields of Bounded Root Discriminant

Point Counting

Computing Hilbert Class Polynomials

Computing Zeta Functions in Families of C a,b Curves Using Deformation

Computing L-Series of Hyperelliptic Curves

Point Counting on Singular Hypersurfaces

Arithmetic of Function Fields

Efficient Hyperelliptic Arithmetic Using Balanced Representation for Divisors

Tabulation of Cubic Function Fields with Imaginary and Unusual Hessian

Modular Forms

Computing Hilbert Modular Forms over Fields with Nontrivial Class Group

Hecke Operators and Hilbert Modular Forms

Cryptography

A Birthday Paradox for Markov Chains, with an Optimal Bound for Collision in the Pollard Rho Algorithm for Discrete Logarithm

An Improved Multi-set Algorithm for the Dense Subset Sum Problem

Number Theory

On the Diophantine Equation x 2 + 2 α 5 β 13 γ = y n

Non-vanishing of Dirichlet L-functions at the Central Point

Backmatter

Premium Partner