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

     

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 .

     

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 .

     

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

     

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.

     

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 .

     

Divisors in residue classes, constructively

Let be integers satisfying , , , and let . Lenstra showed that the number of integer divisors of equivalent to is upper bounded by . We re-examine this problem, showing how to explicitly construct all such divisors, and incidentally improve this bound to .

     

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.

     

Complexity of inverting the Euler function

Given an integer , how hard is it to find the set of all integers such that , where is the Euler totient function? We present a certain basic algorithm which, given the prime number factorization of , in polynomial time ``on average' (that is, ), finds the set of all such solutions . In fact, in the worst case this set of solutions is exponential in , and so cannot be constructed by a polynomial time algorithm. In the opposite direction, we show, under a widely accepted number theoretic conjecture, that the PARTITION PROBLEM, an NP-complete problem, can be reduced in polynomial (in the input size) time to the problem of deciding whether has a solution, for polynomially (in the input size of the PARTITION PROBLEM) many values of (where the prime factorizations of these are given). What this means is that the problem of deciding whether there even exists a solution to , let alone finding any or all such solutions, is very likely to be intractable. Finally, we establish close links between the problem of inverting the Euler function and the integer factorization problem.

     

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 .

     

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 .

     

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 .

     

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.

     

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.

     

Parity-regular Steinhaus graphs

Steinhaus graphs on vertices are certain simple graphs in bijective correspondence with binary -sequences of length . A conjecture of Dymacek in 1979 states that the only nontrivial regular Steinhaus graphs are those corresponding to the periodic binary sequences of any length . By an exhaustive search the conjecture was known to hold up to 25 vertices. We report here that it remains true up to 117 vertices. This is achieved by considering the weaker notion of parity-regular Steinhaus graphs, where all vertex degrees have the same parity. We show that these graphs can be parametrized by an -vector space of dimension approximately and thus constitute an efficiently describable domain where true regular Steinhaus graphs can be searched by computer.

     

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.

     

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.