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.

     

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

     

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.

     

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

     

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 .

     

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 .

     

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

     

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.

     

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.

     

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.

     

Sharp estimates for finite element approximations to elliptic problems with Neumann boundary data of low regularity

Consider a second order homogeneous elliptic problem with smooth coefficients, , on a smooth domain, , but with Neumann boundary data of low regularity. Interior maximum norm error estimates are given for finite element approximations to this problem. When the Neumann data is not in , these local estimates are not of optimal order but are nevertheless shown to be sharp. A method for ameliorating this sub-optimality by preliminary smoothing of the boundary data is given. Numerical examples illustrate the findings.

     

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 .

     

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.

     

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 .

     

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.

     

On univoque Pisot numbers

We study Pisot numbers which are univoque, i.e., such that there exists only one representation of as , with . We prove in particular that there exists a smallest univoque Pisot number, which has degree . Furthermore we give the smallest limit point of the set of univoque Pisot numbers.

     

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.

     

On irregular prime power divisors of the Bernoulli numbers

Let ( ) denote the usual th Bernoulli number. Let be a positive even integer where or . It is well known that the numerator of the reduced quotient is a product of powers of irregular primes. Let be an irregular pair with . We show that for every the congruence has a unique solution where and . The sequence defines a -adic integer which is a zero of a certain -adic zeta function originally defined by T. Kubota and H. W. Leopoldt. We show some properties of these functions and give some applications. Subsequently we give several computations of the (truncated) -adic expansion of for irregular pairs with below 1000.