Two kinds of strong pseudoprimes up to

Let be an odd composite integer. Write with odd. If either mod or mod for some , then we say that is a strong pseudoprime to base , or spsp() for short. Define to be the smallest strong pseudoprime to all the first prime bases. If we know the exact value of , we will have, for integers , a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the are known for . Conjectured values of were given by us in our previous papers (Math. Comp. 72 (2003), 2085-2097; 74 (2005), 1009-1024).

The main purpose of this paper is to give exact values of for ; to give a lower bound of : ; and to give reasons and numerical evidence of K2- and -spsp's to support the following conjecture: for any , where (resp. ) is the smallest K2- (resp. -) strong pseudoprime to all the first prime bases. For this purpose we describe procedures for computing and enumerating the two kinds of spsp's to the first 9 prime bases. The entire calculation took about 4000 hours on a PC Pentium IV/1.8GHz. (Recall that a K2-spsp is an spsp of the form: with primes and ; and that a -spsp is an spsp and a Carmichael number of the form: with each prime factor mod .)

     

Efficient CM-constructions of elliptic curves over finite fields

We present an algorithm that, on input of an integer together with its prime factorization, constructs a finite field and an elliptic curve over for which has order . Although it is unproved that this can be done for all , a heuristic analysis shows that the algorithm has an expected run time that is polynomial in , where is the number of distinct prime factors of . In the cryptographically relevant case where is prime, an expected run time can be achieved. We illustrate the efficiency of the algorithm by constructing elliptic curves with point groups of order and nextprime.

     

Prime decomposition in the anti-cyclotomic extension

For an imaginary quadratic number field and an odd prime number , the anti-cyclotomic -extension of is defined. For primes of , decomposition laws for in the anti-cyclotomic extension are given. We show how these laws can be applied to determine if the Hilbert class field (or part of it) of is -embeddable. For some and , we find explicit polynomials whose roots generate the first step of the anti-cyclotomic extension and show how the prime decomposition laws give nice results on the splitting of these polyniomials modulo . The article contains many numerical examples.

     

Explicit values of multi-dimensional Kloosterman sums for prime powers, II

For any integer fix , and let denote the group of reduced residues modulo . Let , a power of a prime . The hyper-Kloosterman sums of dimension are defined for by

where denotes the multiplicative inverse of modulo .

Salie evaluated in the classical setting for even , and for odd with . Later, Smith provided formulas that simplified the computation of in these cases for . Recently, Cochrane, Liu and Zheng computed upper bounds for in the general case , stopping short of their explicit evaluation. Here I complete the computation they initiated to obtain explicit values for the Kloosterman sums for , relying on basic properties of some simple specialized exponential sums. The treatment here is more elementary than the author's previous determination of these Kloosterman sums using character theory and -adic methods. At the least, it provides an alternative, independent evaluation of the Kloosterman sums.

     

A search for Fibonacci-Wieferich and Wolstenholme primes

A prime is called a Fibonacci-Wieferich prime if , where is the th Fibonacci number. We report that there exist no such primes . A prime is called a Wolstenholme prime if . To date the only known Wolstenholme primes are 16843 and 2124679. We report that there exist no new Wolstenholme primes . Wolstenholme, in 1862, proved that for all primes . It is estimated by a heuristic argument that the ``probability' that is Fibonacci-Wieferich (independently: that is Wolstenholme) is about . We provide some statistical data relevant to occurrences of small values of the Fibonacci-Wieferich quotient modulo .

     

On the embedding problem for representations

Let denote the double cover of corresponding to the element in where transpositions lift to elements of order and the product of two disjoint transpositions to elements of order . Given an elliptic curve , let denote its -torsion points. Under some conditions on elements in correspond to Galois extensions of with Galois group (isomorphic to) . In this work we give an interpretation of the addition law on such fields, and prove that the obstruction for having a Galois extension with gives a homomorphism . As a corollary we can prove (if has conductor divisible by few primes and high rank) the existence of -dimensional representations of the absolute Galois group of attached to and use them in some examples to construct modular forms mapping via the Shimura map to (the modular form of weight attached to) .

     

On the smallest value of the maximal modulus of an algebraic integer

The house of an algebraic integer of degree is the largest modulus of its conjugates. For , we compute the smallest house of degree , say m. As a consequence we improve Matveev's theorem on the lower bound of m We show that, in this range, the conjecture of Schinzel-Zassenhaus is satisfied. The minimal polynomial of any algebraic integer whose house is equal to m is a factor of a bi-, tri- or quadrinomial. The computations use a family of explicit auxiliary functions. These functions depend on generalizations of the integer transfinite diameter of some compact sets in They give better bounds than the classical ones for the coefficients of the minimal polynomial of an algebraic integer whose house is small.

     

Asymptotically fast group operations on Jacobians of general curves

Let be a curve of genus over a field . We describe probabilistic algorithms for addition and inversion of the classes of rational divisors in the Jacobian of . After a precomputation, which is done only once for the curve , the algorithms use only linear algebra in vector spaces of dimension at most , and so take field operations in , using Gaussian elimination. Using fast algorithms for the linear algebra, one can improve this time to . This represents a significant improvement over the previous record of field operations (also after a precomputation) for general curves of genus .

     

Computation of the -part of the ideal class group of certain real abelian fields

Under Greenberg's conjecture, we give an efficient method to compute the -part of the ideal class group of certain real abelian fields by using cyclotomic units, Gauss sums and prime numbers. As numerical examples, we compute the -part of the ideal class group of the maximal real subfield of in the range and . In order to explain our method, we show an example whose ideal class group is not cyclic.

     

Constructing representations of higher degrees of finite simple groups and covers

Let be a finite group and an irreducible character of . A simple method for constructing a representation affording can be used whenever has a subgroup such that has a linear constituent with multiplicity 1. In this paper we show that (with a few exceptions) if is a simple group or a covering group of a simple group and is an irreducible character of of degree between 32 and 100, then such a subgroup exists.

     

A counterexample concerning the -projector onto linear spline spaces

For the -orthogonal projection onto spaces of linear splines over simplicial partitions in polyhedral domains in , , we show that in contrast to the one-dimensional case, where independently of the nature of the partition, in higher dimensions the -norm of cannot be bounded uniformly with respect to the partition. This fact is folklore among specialists in finite element methods and approximation theory but seemingly has never been formally proved.

     

The Lucas-Pratt primality tree

In 1876, E. Lucas showed that a quick proof of primality for a prime could be attained through the prime factorization of and a primitive root for . V. Pratt's proof that PRIMES is in NP, done via Lucas's theorem, showed that a certificate of primality for a prime could be obtained in modular multiplications with integers at most . We show that for all constants , the number of modular multiplications necessary to obtain this certificate is greater than for a set of primes with relative asymptotic density 1.

     

On the polynomial representation for the number of partitions with fixed length

In this paper, it is shown that the number of partitions of a nonnegative integer with parts can be described by a set of polynomials of degree in , where denotes the least common multiple of the integers and denotes the quotient of when divided by . In addition, the sets of the polynomials are obtained and shown explicitly for and .

     

Tractability of quasilinear problems II: Second-order elliptic problems

In a previous paper, we developed a general framework for establishing tractability and strong tractability for quasilinear multivariate problems in the worst case setting. One important example of such a problem is the solution of the Helmholtz equation in the -dimensional unit cube, in which depends linearly on , but nonlinearly on . Here, both and  are -variate functions from a reproducing kernel Hilbert space with finite-order weights of order . This means that, although  can be arbitrarily large, and  can be decomposed as sums of functions of at most  variables, with independent of .

In this paper, we apply our previous general results to the Helmholtz equation, subject to either Dirichlet or Neumann homogeneous boundary conditions. We study both the absolute and normalized error criteria. For all four possible combinations of boundary conditions and error criteria, we show that the problem is tractable. That is, the number of evaluations of and  needed to obtain an -approximation is polynomial in  and , with the degree of the polynomial depending linearly on . In addition, we want to know when the problem is strongly tractable, meaning that the dependence is polynomial only in  , independently of . We show that if the sum of the weights defining the weighted reproducing kernel Hilbert space is uniformly bounded in  and the integral of the univariate kernel is positive, then the Helmholtz equation is strongly tractable for three of the four possible combinations of boundary conditions and error criteria, the only exception being the Dirichlet boundary condition under the normalized error criterion.

     

Euclidean minima of totally real number fields: Algorithmic determination

This article deals with the determination of the Euclidean minimum of a totally real number field of degree , using techniques from the geometry of numbers. Our improvements of existing algorithms allow us to compute Euclidean minima for fields of degree to and small discriminants, most of which were previously unknown. Tables are given at the end of this paper.

     

Computing the integer partition function

In this paper we discuss efficient algorithms for computing the values of the partition function and implement these algorithms in order to conduct a numerical study of some conjectures related to the partition function. We present the distribution of for for primes up to and small powers of and .

     

The generalized triangular decomposition

Given a complex matrix , we consider the decomposition , where is upper triangular and and have orthonormal columns. Special instances of this decomposition include the singular value decomposition (SVD) and the Schur decomposition where is an upper triangular matrix with the eigenvalues of on the diagonal. We show that any diagonal for can be achieved that satisfies Weyl's multiplicative majorization conditions:

where is the rank of , is the -th largest singular value of , and is the -th largest (in magnitude) diagonal element of . Given a vector which satisfies Weyl's conditions, we call the decomposition , where is upper triangular with prescribed diagonal , the generalized triangular decomposition (GTD). A direct (nonrecursive) algorithm is developed for computing the GTD. This algorithm starts with the SVD and applies a series of permutations and Givens rotations to obtain the GTD. The numerical stability of the GTD update step is established. The GTD can be used to optimize the power utilization of a communication channel, while taking into account quality of service requirements for subchannels. Another application of the GTD is to inverse eigenvalue problems where the goal is to construct matrices with prescribed eigenvalues and singular values.

     

Uniform error estimates in the finite element method for a singularly perturbed reaction-diffusion problem

Consider the problem with homogeneous Neumann boundary condition in a bounded smooth domain in . The whole range is treated. The Galerkin finite element method is used on a globally quasi-uniform mesh of size ; the mesh is fixed and independent of .

A precise analysis of how the error at each point depends on and is presented. As an application, first order error estimates in , which are uniform with respect to , are given.

     

Continuous interior penalty -finite element methods for advection and advection-diffusion equations

A continuous interior penalty -finite element method that penalizes the jump of the gradient of the discrete solution across mesh interfaces is introduced. Error estimates are obtained for advection and advection-diffusion equations. The analysis relies on three technical results that are of independent interest: an -inverse trace inequality, a local discontinuous to continuous -interpolation result, and -error estimates for continuous -orthogonal projections.