A modification of Shanks' baby-step giant-step algorithm

I describe a modification to Shanks' baby-step giant-step algorithm for computing the order of an element of a group , assuming is finite. My method has the advantage of being able to compute quickly, which Shanks' method fails to do when the order of is infinite, unknown, or much larger than . I describe the algorithm in detail. I also present the results of implementations of my algorithm, as well as those of a similar algorithm developed by Buchmann, Jacobson, and Teske, for calculating the order of various ideal classes of imaginary quadratic orders.

     

Salem numbers of negative trace

We prove that, for all , there are Salem numbers of degree and trace , and that the number of such Salem numbers is . As a consequence, it follows that the number of totally positive algebraic integers of degree and trace is also .

     

On the convergence of certain Gauss-type quadrature formulas for unbounded intervals

We consider the convergence of Gauss-type quadrature formulas for the integral , where is a weight function on the half line . The -point Gauss-type quadrature formulas are constructed such that they are exact in the set of Laurent polynomials }, where is a sequence of integers satisfying and . It is proved that under certain Carleman-type conditions for the weight and when or goes to , then convergence holds for all functions for which is integrable on . Some numerical experiments compare the convergence of these quadrature formulas with the convergence of the classical Gauss quadrature formulas for the half line.

     

Solving polynomials by radicals with roots of unity in minimum depth

Let be an algebraic number field. Let be a root of a polynomial which is solvable by radicals. Let be the splitting field of over . Let be a natural number divisible by the discriminant of the maximal abelian subextension of , as well as the exponent of , the Galois group of over . We show that an optimal nested radical with roots of unity for can be effectively constructed from the derived series of the solvable Galois group of over .

     

Stability of Runge-Kutta methods for quasilinear parabolic problems

We consider a quasilinear parabolic problem

where , , is a family of sectorial operators in a Banach space with fixed domain . This problem is discretized in time by means of a strongly A()-stable, , Runge-Kutta method. We prove that the resulting discretization is stable, under some natural assumptions on the dependence of with respect to . Our results are useful for studying in norms, , many problems arising in applications. Some auxiliary results for time-dependent parabolic problems are also provided.

     

Tables of curves with many points

These tables record results on curves with many points over finite fields. For relatively small genus () and a small power of or we give in two tables the best presently known bounds for , the maximum number of rational points on a smooth absolutely irreducible projective curve of genus over a field of cardinality . In additional tables we list for a given pair the type of construction of the best curve so far, and we give a reference to the literature where such a curve can be found.

     

Computing automorphisms of abelian number fields

Let be an abelian number field of degree . Most algorithms for computing the lattice of subfields of require the computation of all the conjugates of . This is usually achieved by factoring the minimal polynomial of over . In practice, the existing algorithms for factoring polynomials over algebraic number fields can handle only problems of moderate size. In this paper we describe a fast probabilistic algorithm for computing the conjugates of , which is based on -adic techniques. Given and a rational prime which does not divide the discriminant of , the algorithm computes the Frobenius automorphism of in time polynomial in the size of and in the size of . By repeatedly applying the algorithm to randomly chosen primes it is possible to compute all the conjugates of .

     

Nonexistence conditions of a solution for the congruence

We obtain nonexistence conditions of a solution for of the congruence , where , and are integers, and is a prime power. We give nonexistence conditions of the form for , , , , , and of the form for , , , . Furthermore, we complete some tables concerned with Waring's problem in -adic fields that were computed by Hardy and Littlewood.

     

On fundamental domains of arithmetic Fuchsian groups

Let be a totally real algebraic number field and an order in a quaternion algebra over . Assume that the group of units in with reduced norm equal to is embedded into as an arithmetic Fuchsian group. It is shown how Ford's algorithm can be effectively applied in order to determine a fundamental domain of as well as a complete system of generators of .

     

Normal bases via general Gauss periods

Gauss periods have been used successfully as a tool for constructing normal bases in finite fields. Starting from a primitive th root of unity, one obtains under certain conditions a normal basis for over , where is a prime and for some integer . We generalize this construction by allowing arbitrary integers with , and find in many cases smaller values of than is possible with the previously known approach.

     

New Fibonacci and Lucas primes

Extending previous searches for prime Fibonacci and Lucas numbers, all probable prime Fibonacci numbers have been determined for and all probable prime Lucas numbers have been determined for . A rigorous proof of primality is given for and for numbers with , , , , , , , , the prime having 3020 digits. Primitive parts and of composite numbers and have also been tested for probable primality. Actual primality has been established for many of them, including 22 with more than 1000 digits. In a Supplement to the paper, factorizations of numbers and are given for as far as they have been completed, adding information to existing factor tables covering .

     

On the modular curves

Let denote an elliptic curve over and the modular curve classifying the elliptic curves over such that the representations of in the 7-torsion points of and of are symplectically isomorphic. In case is given by a Weierstraß equation such that the invariant is a square, we exhibit here nontrivial points of . From this we deduce an infinite family of curves for which has at least four nontrivial points.

     

The Postage Stamp Problem: An algorithm to determine the

Given an integral ``stamp" basis with and a positive integer , we define the -range as

. For given and , the extremal basis has the largest possible extremal -range

We give an algorithm to determine the -range. We prove some properties of the -range formula, and we conjecture its form for the extremal -range. We consider parameter bases , where the basis elements are given functions of . For we conjecture the extremal parameter bases for .

     

Random Fibonacci sequences and the number

For the familiar Fibonacci sequence (defined by , and for ), increases exponentially with at a rate given by the golden ratio . But for a simple modification with both additions and subtractions - the random Fibonacci sequences defined by , and for , , where each sign is independent and either or - with probability - it is not even obvious if should increase with . Our main result is that

with probability . Finding the number involves the theory of random matrix products, Stern-Brocot division of the real line, a fractal measure, a computer calculation, and a rounding error analysis to validate the computer calculation.

     

On the discrete logarithm in the divisor class group of curves

Let be a curve which is defined over a finite field of characteristic . We show that one can evaluate the discrete logarithm in by operations in . This generalizes a result of Semaev for elliptic curves to curves of arbitrary genus.

     

The third largest prime divisor of an odd perfect number exceeds one hundred

Let denote the sum of positive divisors of the natural number . Such a number is said to be perfect if . It is well known that a number is even and perfect if and only if it has the form where is prime.

It is unknown whether or not odd perfect numbers exist, although many conditions necessary for their existence have been found. For example, Cohen and Hagis have shown that the largest prime divisor of an odd perfect number must exceed , and Iannucci showed that the second largest must exceed . In this paper, we prove that the third largest prime divisor of an odd perfect number must exceed 100.

     

Computation of relative class numbers of CM-fields by using Hecke -functions

We develop an efficient technique for computing values at of Hecke -functions. We apply this technique to the computation of relative class numbers of non-abelian CM-fields which are abelian extensions of some totally real subfield . We note that the smaller the degree of the more efficient our technique is. In particular, our technique is very efficient whenever instead of simply choosing (the maximal totally real subfield of ) we can choose real quadratic. We finally give examples of computations of relative class numbers of several dihedral CM-fields of large degrees and of several quaternion octic CM-fields with large discriminants.

     

The number of primes is finite

For a positive integer let and let . The number of primes of the form is finite, because if , then is divisible by . The heuristic argument is given by which there exists a prime such that for all large ; a computer check however shows that this prime has to be greater than . The conjecture that the numbers are squarefree is not true because .

     

On factor refinement in number fields

Let be an order of an algebraic number field. It was shown by Ge that given a factorization of an -ideal into a product of -ideals it is possible to compute in polynomial time an overorder of and a gcd-free refinement of the input factorization; i.e., a factorization of into a power product of -ideals such that the bases of that power product are all invertible and pairwise coprime and the extensions of the factors of the input factorization are products of the bases of the output factorization. In this paper we prove that the order is the smallest overorder of in which such a gcd-free refinement of the input factorization exists. We also introduce a partial ordering on the gcd-free factorizations and prove that the factorization which is computed by Ge's algorithm is the smallest gcd-free refinement of the input factorization with respect to this partial ordering.

     

Analysis of PSLQ, an integer relation finding algorithm

Let be either the real, complex, or quaternion number system and let be the corresponding integers. Let be a vector in . The vector has an integer relation if there exists a vector , , such that . In this paper we define the parameterized integer relation construction algorithm PSLQ, where the parameter can be freely chosen in a certain interval. Beginning with an arbitrary vector , iterations of PSLQ will produce lower bounds on the norm of any possible relation for . Thus PSLQ can be used to prove that there are no relations for of norm less than a given size. Let be the smallest norm of any relation for . For the real and complex case and each fixed parameter in a certain interval, we prove that PSLQ constructs a relation in less than iterations.