Finding strong pseudoprimes to several bases. II

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 . Upper bounds for were first given by Jaeschke, and those for were then sharpened by the first author in his previous paper (Math. Comp. 70 (2001), 863-872).

In this paper, we first follow the first author's previous work to use biquadratic residue characters and cubic residue characters as main tools to tabulate all strong pseudoprimes (spsp's) to the first five or six prime bases, which have the form with odd primes and ; then we tabulate all Carmichael numbers , to the first six prime bases up to 13, which have the form with each prime factor . There are in total 36 such Carmichael numbers, 12 numbers of which are also spsp's to base 17; 5 numbers are spsp's to bases 17 and 19; one number is an spsp to the first 11 prime bases up to 31. As a result the upper bounds for and are lowered from 20- and 22-decimal-digit numbers to a 19-decimal-digit number:

We conjecture that

and give reasons to support this conjecture. The main idea for finding these Carmichael numbers is that we loop on the largest prime factor and propose necessary conditions on to be a strong pseudoprime to the first prime bases. Comparisons of effectiveness with Arnault's, Bleichenbacher's, Jaeschke's, and Pinch's methods for finding (Carmichael) numbers with three prime factors, which are strong pseudoprimes to the first several prime bases, are given.

     

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

     

An analysis of the Rayleigh-Ritz method for approximating eigenspaces

This paper concerns the Rayleigh-Ritz method for computing an approximation to an eigenspace of a general matrix from a subspace that contains an approximation to . The method produces a pair that purports to approximate a pair , where is a basis for and . In this paper we consider the convergence of as the sine of the angle between and approaches zero. It is shown that under a natural hypothesis--called the uniform separation condition--the Ritz pairs converge to the eigenpair . When one is concerned with eigenvalues and eigenvectors, one can compute certain refined Ritz vectors whose convergence is guaranteed, even when the uniform separation condition is not satisfied. An attractive feature of the analysis is that it does not assume that has distinct eigenvalues or is diagonalizable.

     

On the uniformity of distribution of the RSA pairs

Let be a product of two distinct primes and . We show that for almost all exponents with the RSA pairs are uniformly distributed modulo when runs through

the group of units modulo (that is, as in the classical RSA scheme);

the set of -products , , where are selected at random (that is, as in the recently introduced RSA scheme with precomputation).

These results are based on some new bounds of exponential sums.

     

The -approximation order of surface spline interpolation

We show that if the open, bounded domain has a sufficiently smooth boundary and if the data function is sufficiently smooth, then the -norm of the error between and its surface spline interpolant is ( ), where and is an integer parameter specifying the surface spline. In case , this lower bound on the approximation order agrees with a previously obtained upper bound, and so we conclude that the -approximation order of surface spline interpolation is .

     

Tenth degree number fields with quintic fields having one real place

In this paper, we enumerate all number fields of degree of discriminant smaller than in absolute value containing a quintic field having one real place. For each one of the (resp. found fields of signature (resp. the field discriminant, the quintic field discriminant, a polynomial defining the relative quadratic extension, the corresponding relative discriminant, the corresponding polynomial over , and the Galois group of the Galois closure are given.

In a supplementary section, we give the first coincidence of discriminant of (resp. nonisomorphic fields of signature (resp. .

     

Upper bounds for the prime divisors of Wendt's determinant

Let be an even integer, . The resultant of the polynomials and is known as Wendt's determinant of order . We prove that among the prime divisors of only those which divide or can be larger than , where and is the th Lucas number, except when and . Using this estimate we derive criteria for the nonsolvability of Fermat's congruence.

     

Period of the power generator and small values of Carmichael's function

Consider the pseudorandom number generator where we are given the modulus , the initial value and the exponent . One case of particular interest is when the modulus is of the form , where are different primes of the same magnitude. It is known from work of the first and third authors that for moduli , if the period of the sequence exceeds , then the sequence is uniformly distributed. We show rigorously that for almost all choices of it is the case that for almost all choices of , the period of the power generator exceeds . And so, in this case, the power generator is uniformly distributed.

We also give some other cryptographic applications, namely, to ruling-out the cycling attack on the RSA cryptosystem and to so-called time-release crypto.

The principal tool is an estimate related to the Carmichael function , the size of the largest cyclic subgroup of the multiplicative group of residues modulo . In particular, we show that for any , we have for all integers with , apart from at most exceptions.

     

Wavelet bases in

Some years ago, compactly supported divergence-free wavelets were constructed which also gave rise to a stable (biorthogonal) wavelet splitting of . These bases have successfully been used both in the analysis and numerical treatment of the Stokes and Navier-Stokes equations. In this paper, we construct stable wavelet bases for the stream function spaces . Moreover, -free vector wavelets are constructed and analysed. The relationship between and are expressed in terms of these wavelets. We obtain discrete (orthogonal) Hodge decompositions.

Our construction works independently of the space dimension, but in terms of general assumptions on the underlying wavelet systems in that are used as building blocks. We give concrete examples of such bases for tensor product and certain more general domains . As an application, we obtain wavelet multilevel preconditioners in and .

     

Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields

We examine the problem of factoring the th cyclotomic polynomial, over , and distinct primes. Given the traces of the roots of we construct the coefficients of in time . We demonstrate a deterministic algorithm for factoring in time when has precisely two irreducible factors. Finally, we present a deterministic algorithm for computing the sum of the irreducible factors of in time .

     

On a conjecture of Erdos and Stewart

For any , let be the th prime number. In this paper, we confirm a conjecture of Erdos and Stewart concerning all the solutions of the diophantine equation , when .

     

Counting primes in residue classes

We explain how the Meissel-Lehmer-Lagarias-Miller-Odlyzko method for computing can be used for computing efficiently , the number of primes congruent to modulo up to . As an application, we computed the number of prime numbers of the form less than for several values of up to and found a new region where is less than near .

     

Computer verification of the Ankeny-Artin-Chowla Conjecture for all primes less than

Let be a prime congruent to 1 modulo 4, and let be rational integers such that is the fundamental unit of the real quadratic field . The Ankeny-Artin-Chowla conjecture (AAC conjecture) asserts that will not divide . This is equivalent to the assertion that will not divide , where denotes the th Bernoulli number. Although first published in 1952, this conjecture still remains unproved today. Indeed, it appears to be most difficult to prove. Even testing the conjecture can be quite challenging because of the size of the numbers ; for example, when , then both and exceed . In 1988 the AAC conjecture was verified by computer for all . In this paper we describe a new technique for testing the AAC conjecture and we provide some results of a computer run of the method for all primes up to .

     

The convergence of harmonic Ritz values, harmonic Ritz vectors, and refined harmonic Ritz vectors

This paper concerns a harmonic projection method for computing an approximation to an eigenpair of a large matrix . Given a target point and a subspace that contains an approximation to , the harmonic projection method returns an approximation to . Three convergence results are established as the deviation of from approaches zero. First, the harmonic Ritz value converges to if a certain Rayleigh quotient matrix is uniformly nonsingular. Second, the harmonic Ritz vector converges to if the Rayleigh quotient matrix is uniformly nonsingular and remains well separated from the other harmonic Ritz values. Third, better error bounds for the convergence of are derived when converges. However, we show that the harmonic projection method can fail to find the desired eigenvalue --in other words, the method can miss if it is very close to . To this end, we propose to compute the Rayleigh quotient of with respect to and take it as a new approximate eigenvalue. is shown to converge to once tends to , no matter how is close to . Finally, we show that if the Rayleigh quotient matrix is uniformly nonsingular, then the refined harmonic Ritz vector, or more generally the refined eigenvector approximation introduced by the author, converges. We construct examples to illustrate our theory.

     

Approximating the exponential from a Lie algebra to a Lie group

Consider a differential equation with and , where is a Lie algebra of the matricial Lie group . Every can be mapped to by the matrix exponential map with .

Most numerical methods for solving ordinary differential equations (ODEs) on Lie groups are based on the idea of representing the approximation of the exact solution , , by means of exact exponentials of suitable elements of the Lie algebra, applied to the initial value . This ensures that .

When the exponential is difficult to compute exactly, as is the case when the dimension is large, an approximation of plays an important role in the numerical solution of ODEs on Lie groups. In some cases rational or polynomial approximants are unsuitable and we consider alternative techniques, whereby is approximated by a product of simpler exponentials.

In this paper we present some ideas based on the use of the Strang splitting for the approximation of matrix exponentials. Several cases of and are considered, in tandem with general theory. Order conditions are discussed, and a number of numerical experiments conclude the paper.

     

Families of irreducible polynomials of Gaussian periods and matrices of cyclotomic numbers

Given an odd prime we show a way to construct large families of polynomials , , where is a set of primes of the form mod and is the irreducible polynomial of the Gaussian periods of degree in . Examples of these families when are worked in detail. We also show, given an integer and a prime mod , how to represent by matrices the Gaussian periods of degree in , and how to calculate in a simple way, with the help of a computer, irreducible polynomials for elements of .

     

Korovkin tests, approximation, and ergodic theory

We consider sequences of matrices with a block structure spectrally distributed as an -variate matrix-valued function , and, for any , we suppose that is a linear and positive operator. For every fixed we approximate the matrix in a suitable linear space of matrices by minimizing the Frobenius norm of when ranges over . The minimizer is denoted by . We show that only a simple Korovkin test over a finite number of polynomial test functions has to be performed in order to prove the following general facts:

1.

the sequence is distributed as ,

2.

the sequence is distributed as the constant function (i.e. is spectrally clustered at zero).

The first result is an ergodic one which can be used for solving numerical approximation theory problems. The second has a natural interpretation in the theory of the preconditioning associated to cg-like algorithms.

     

Continued fractions in local fields, II

The present paper is a continuation of an earlier work by the author. We propose some new definitions of -adic continued fractions. At the end of the paper we give numerical examples illustrating these definitions. It turns out that for every if then has a periodic continued fraction expansion. The same is not true in for some larger values of

     

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 .

     

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.