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

     

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

     

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.

     

Minimality and other properties of the width- nonadjacent form

Let be an integer and let be the set of integers that includes zero and the odd integers with absolute value less than . Every integer can be represented as a finite sum of the form , with , such that of any consecutive 's at most one is nonzero. Such representations are called width- nonadjacent forms (-NAFs). When these representations use the digits and coincide with the well-known nonadjacent forms. Width- nonadjacent forms are useful in efficiently implementing elliptic curve arithmetic for cryptographic applications. We provide some new results on the -NAF. We show that -NAFs have a minimal number of nonzero digits and we also give a new characterization of the -NAF in terms of a (right-to-left) lexicographical ordering. We also generalize a result on -NAFs and show that any base 2 representation of an integer, with digits in , that has a minimal number of nonzero digits is at most one digit longer than its binary representation.

     

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.

     

Sharply localized pointwise and estimates for finite element methods for quasilinear problems

We establish pointwise and estimates for finite element methods for a class of second-order quasilinear elliptic problems defined on domains in . These estimates are localized in that they indicate that the pointwise dependence of the error on global norms of the solution is of higher order. Our pointwise estimates are similar to and rely on results and analysis techniques of Schatz for linear problems. We also extend estimates of Schatz and Wahlbin for pointwise differences in pointwise errors to quasilinear problems. Finally, we establish estimates for the error in , where is a subdomain. These negative norm estimates are novel for linear as well as for nonlinear problems. Our analysis heavily exploits the fact that Galerkin error relationships for quasilinear problems may be viewed as perturbed linear error relationships, thus allowing easy application of properly formulated results for linear problems.

     

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.

     

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.

     

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.

     

An -local discontinuous Galerkin method for some quasilinear elliptic boundary value problems of nonmonotone type

In this paper, an -local discontinuous Galerkin method is applied to a class of quasilinear elliptic boundary value problems which are of nonmonotone type. On -quasiuniform meshes, using the Brouwer fixed point theorem, it is shown that the discrete problem has a solution, and then using Lipschitz continuity of the discrete solution map, uniqueness is also proved. A priori error estimates in broken norm and norm which are optimal in , suboptimal in are derived. These results are exactly the same as in the case of linear elliptic boundary value problems. Numerical experiments are provided to illustrate the theoretical results.

     

Computing weight modular forms of level

For a prime we describe an algorithm for computing the Brandt matrices giving the action of the Hecke operators on the space of modular forms of weight and level . For we define a special Hecke stable subspace of which contains the space of modular forms with CM by the ring of integers of and we describe the calculation of the corresponding Brandt matrices.

     

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.

     

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 .

     

Real zeros of real odd Dirichlet -functions

Let be a real odd Dirichlet character of modulus , and let be the associated Dirichlet -function. As a consequence of the work of Low and Purdy, it is known that if and , , , then has no positive real zeros. By a simple extension of their ideas and the advantage of thirty years of advances in computational power, we are able to prove that if , then has no positive real zeros.

     

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.

     

Comparison theorems of Kolmogorov type and exact values of -widths on Hardy-Sobolev classes

Let be a strip in complex plane. denotes those -periodic, real-valued functions on which are analytic in the strip and satisfy the condition , . Osipenko and Wilderotter obtained the exact values of the Kolmogorov, linear, Gel'fand, and information -widths of in , , and 2-widths of in , , .

In this paper we continue their work. Firstly, we establish a comparison theorem of Kolmogorov type on , from which we get an inequality of Landau-Kolmogorov type. Secondly, we apply these results to determine the exact values of the Gel'fand -width of in , . Finally, we calculate the exact values of Kolmogorov -width, linear -width, and information -width of in , , .

     

Balanced multi-wavelets in

The notion of -balancing was introduced a few years ago as a condition for the construction of orthonormal scaling function vectors and multi-wavelets to ensure the property of preservation/annihilation of scalar-valued discrete polynomial data of order (or degree ), when decomposed by the corresponding matrix-valued low-pass/high-pass filters. While this condition is indeed precise, to the best of our knowledge only the proof for is known. In addition, the formulation of the -balancing condition for is so prohibitively difficult to satisfy that only a very few examples for and vector dimension 2 have been constructed in the open literature. The objective of this paper is to derive various characterizations of the -balancing condition that include the polynomial preservation property as well as equivalent formulations that facilitate the development of methods for the construction purpose. These results are established in the general multivariate and bi-orthogonal settings for any .

     

High rank elliptic curves with torsion group

We develop an algorithm for bounding the rank of elliptic curves in the family , all of them with torsion group and modular invariant . We use it to look for curves of high rank in this family and present four such curves of rank  and of rank .

     

Hermite interpolation by Pythagorean Hodograph space curves

We solve the problem of Hermite interpolation by Pythagorean Hodograph (PH) space curves. More precisely, for any set of space boundary data (two points with associated first and second derivatives) we construct a four-dimensional family of PH interpolants of degree and introduce a geometrically invariant parameterization of this family. This parameterization is used to identify a particular solution, which has the following properties. First, it preserves planarity, i.e., the interpolant to planar data is a planar PH curve. Second, it has the best possible approximation order 6. Third, it is symmetric in the sense that the interpolant of the ``reversed' set of boundary data is simply the ``reversed' original interpolant. This particular PH interpolant is exploited for designing algorithms for converting (possibly piecewise) analytical curves into a piecewise PH curve of degree which is globally , and for simple rational approximation of pipe surfaces with a piecewise analytical spine curve. The algorithms are presented along with an analysis of their error and approximation order.

     

Solutions of the congruence

To supplement existing data, solutions of are tabulated for primes with and . For , five new solutions 2^{32}$"> are presented. One of these, for , also satisfies the ``reverse' congruence . An effective procedure for searching for such ``double solutions' is described and applied to the range , . Previous to this, congruences are generally considered for any and fixed prime to see where the smallest prime solution occurs.