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.

     

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) .

     

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 .

     

Discrete maximum principle for higher-order finite elements in 1D

We formulate a sufficient condition on the mesh under which we prove the discrete maximum principle (DMP) for the one-dimensional Poisson equation with Dirichlet boundary conditions discretized by the -FEM. The DMP holds if a relative length of every element in the mesh is bounded by a value , where is the polynomial degree of the element . The values are calculated for .

     

Two lower order nonconforming rectangular elements for the Reissner-Mindlin plate

In this paper, we propose two lower order nonconforming rectangular elements for the Reissner-Mindlin plate. The first one uses the conforming bilinear element to approximate both components of the rotation, and the modified nonconforming rotated element to approximate the displacement, whereas the second one uses the modified nonconforming rotated element to approximate both the rotation and the displacement. Both elements employ a projection operator to overcome the shear force locking. We prove that both methods converge at optimal rates uniformly in the plate thickness in both the - and -norms, and consequently they are locking free.

     

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.

     

Odd perfect numbers have at least nine distinct prime factors

An odd perfect number, , is shown to have at least nine distinct prime factors. If then must have at least twelve distinct prime divisors. The proof ultimately avoids previous computational results for odd perfect numbers.

     

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.

     

K3 surfaces with Picard number three and canonical vector heights

In this paper we construct the first known explicit family of K3 surfaces defined over the rationals that are proved to have geometric Picard number . This family is dense in one of the components of the moduli space of all polarized K3 surfaces with Picard number at least . We also use an example from this family to fill a gap in an earlier paper by the first author. In that paper, an argument for the nonexistence of canonical vector heights on K3 surfaces of Picard number was given, based on an explicit surface that was not proved to have Picard number . We redo the computations for one of our surfaces and come to the same conclusion.

     

New techniques for bounds on the total number of prime factors of an odd perfect number

Let denote the sum of the positive divisors of . We say that is perfect if . Currently there are no known odd perfect numbers. It is known that if an odd perfect number exists, then it must be of the form , where are distinct primes and . Define the total number of prime factors of as . Sayers showed that . This was later extended by Iannucci and Sorli to show that . This was extended by the author to show that . Using an idea of Carl Pomerance this paper extends these results. The current new bound is .

     

New integer representations as the sum of three cubes

We describe a new algorithm for finding integer solutions to for specific values of . We use this to find representations for values of for which no solution was previously known, including and .

     

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.

     

Elliptic curves with nonsplit mod representations

We calculate explicitly the -invariants of the elliptic curves corresponding to rational points on the modular curve by giving an expression defined over of the -function in terms of the function field generators and of the elliptic curve . As a result we exhibit infinitely many elliptic curves over with nonsplit mod representations.

     

Continuous-time Kreiss resolvent condition on infinite-dimensional spaces

Given the infinitesimal generator of a -semigroup on the Banach space which satisfies the Kreiss resolvent condition, i.e., there exists an such that for all complex with positive real part, we show that for general Banach spaces this condition does not give any information on the growth of the associated -semigroup. For Hilbert spaces the situation is less dramatic. In particular, we show that the semigroup can grow at most like . Furthermore, we show that for every there exists an infinitesimal generator satisfying the Kreiss resolvent condition, but whose semigroup grows at least like . As a consequence, we find that for with the standard Euclidian norm the estimate cannot be replaced by a lower power of or .

     

On geometric interpolation by planar parametric polynomial curves

In this paper the problem of geometric interpolation of planar data by parametric polynomial curves is revisited. The conjecture that a parametric polynomial curve of degree can interpolate given points in is confirmed for under certain natural restrictions. This conclusion also implies the optimal asymptotic approximation order. More generally, the optimal order can be achieved as soon as the interpolating curve exists.

     

A dual finite element complex on the barycentric refinement

Given a two dimensional oriented surface equipped with a simplicial mesh, the standard lowest order finite element spaces provide a complex centered on Raviart-Thomas divergence conforming vector fields. It can be seen as a realization of the simplicial cochain complex. We construct a new complex of finite element spaces on the barycentric refinement of the mesh which can be seen as a realization of the simplicial chain complex on the original (unrefined) mesh, such that the duality is non-degenerate on for each . In particular is a space of -conforming vector fields which is dual to Raviart-Thomas -conforming elements. When interpreted in terms of differential forms, these two complexes provide a finite-dimensional analogue of Hodge duality.

     

Error bounds on complex floating-point multiplication

Given floating-point arithmetic with -digit base- significands in which all arithmetic operations are performed as if calculated to infinite precision and rounded to a nearest representable value, we prove that the product of complex values and can be computed with maximum absolute error . In particular, this provides relative error bounds of and for IEEE 754 single and double precision arithmetic respectively, provided that overflow, underflow, and denormals do not occur.

We also provide the numerical worst cases for IEEE 754 single and double precision arithmetic.

     

Finding -strong pseudoprimes

Let be odd primes and . Put

Then we call the kernel, the triple the signature, and the height of , respectively. We call a -number if it is a Carmichael number with each prime factor . If is a -number and a strong pseudoprime to the bases for , we call a -spsp . Since -numbers have probability of error (the upper bound of that for the Rabin-Miller test), they often serve as the exact values or upper bounds of (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.

In this paper, we first describe an algorithm for finding -spsp(2)'s, to a given limit, with heights bounded. There are in total -spsp's with heights . We then give an overview of the 21978 - spsp(2)'s and tabulate of them, which are -spsp's to the first prime bases up to ; three numbers are spsp's to the first 11 prime bases up to 31. No -spsp's to the first prime bases with heights were found. We conjecture that there exist no -spsp's to the first prime bases with heights and so that

which was found by the author in an earlier paper. We give reasons to support the conjecture. The main idea of our method for finding those -spsp's is that we loop on candidates of signatures and kernels with heights bounded, subject those candidates of -spsp's and their prime factors to Miller's tests, and obtain the desired numbers. At last we speed our algorithm for finding larger -spsp's, say up to , with a given signature to more prime bases. Comparisons of effectiveness with Arnault's and our previous methods for finding -strong pseudoprimes to the first several prime bases are given.