#
First International Symposium, ANTS-I Ithaca, NY, USA, May 6–9, 1994 Proceedings

*n*, let

*w(n)*denote the least witness for

*n*; that is, the least positive number

*w*for which

*n*is not a strong pseudoprime to the base

*w*. It is widely conjectured, but not proved, that

*w(n)*> 3 for infinitely many

*n*. We show the stronger result that

*w(n)*> (log

*n*)

^{1/(3 log log log n)}for infinitely many

*n*. We also show that there are finite sets of odd composites which...

*N*

^{ k }-th division points on an

*n*-dimensional simple Abelian variety with Complex Multiplication. Two new examples are discussed.

*m*of an elliptic curve over a finite field is the computation of

*m*modulo small primes

*l*. Elkies and Atkin have designed practical improvements to the basic algorithm, that make use of “good” primes

*l*. We show how to use powers of good primes in an efficient way. This is done by computing isogenies between curves over the ground field....

_{p}, where

*p*is a 375-digit prime.

*f(x)*can be written as a composition of functions

*g(h(x))*in a nontrivial way—is an important primitive in symbolic computation systems. The problem of univariate polynomial decomposition was shown to have an efficient solution by Kozen and Landau [9]. Dickerson [5] and von zur Gathen [13] gave algorithms for certain multivariate cases. Zippel [15] showed...

*p*

^{n}). An heuristic analysis shows that there exists a

*c*ε ℜ

_{>0}such that the function field sieve computes discrete logarithms within random time:

*L*

_{ p}...

**Q**, concentrating on the curves

*E*

_{ d }:

*Dy*

^{2}=

*x*

^{3}−

*x*arising in the “congruent number” problem. We begin by briefly reviewing the cyclotomic construction of units in real quadratic number fields, which is analogous in many ways to the Heegner-point approach...

*N*can be parametrized by modular functions for the congruence subgroup Γ

_{0}(

*N*) of the modular group Γ =

*PSL*(2, ℤ). Equivalently, there is a non-constant map ϕ from the modular curve

*X*

_{0}

*(N)*to

*E*. We present here a method of computing the degree of such a map ϕ for arbitrary

*N*. Our method, which works for...

*L*be a

*k*-dimensional lattice in IR

^{m}with basis

*B*= (

*b*

_{1},...,

*b*

_{k}). Let

*A*= (

*a*

_{1},...,

*a*

_{k}) be a rational approximation to

*B*. Assume that

*A*has rank

*k*and a lattice basis reduction algorithm applied to the columns of

*A*yields a transformation

*T*= (

*t*

_{1},...,

*t*

_{k}) ε GL(

*k*, ℤ) such that

*A*

__t__

_{i}≤

*s*

_{ i }...