Computation of several cyclotomic Swan subgroups

Let denote the locally free class group, that is the group of stable isomorphism classes of locally free -modules, where is the ring of algebraic integers in the number field and is a finite group. We show how to compute the Swan subgroup, , of when , a primitive -th root of unity, , where is an odd (rational) prime so that and 2 is inert in We show that, under these hypotheses, this calculation reduces to computing a quotient ring of a polynomial ring; we do the computations obtaining for several primes a nontrivial divisor of These calculations give an alternative proof that the fields for =11, 13, 19, 29, 37, 53, 59, and 61 are not Hilbert-Speiser.

     

Special prime numbers and discrete logs in finite prime fields

A set of primes involving numbers such as , where and , is defined. An algorithm for computing discrete logs in the finite field of order with is suggested. Its heuristic expected running time is for , where as , , and . At present, the most efficient algorithm for computing discrete logs in the finite field of order for general is Schirokauer's adaptation of the Number Field Sieve. Its heuristic expected running time is for . Using rather than general does not enhance the performance of Schirokauer's algorithm. The definition of the set and the algorithm suggested in this paper are based on a more general congruence than that of the Number Field Sieve. The congruence is related to the resultant of integer polynomials. We also give a number of useful identities for resultants that allow us to specify this congruence for some .

     

Merging the Bramble-Pasciak-Steinbach and the Crouzeix-Thomée criterion for -projection onto finite element spaces

Suppose is a finite-dimensional linear space based on a triangulation of a domain , and let denote the -projection onto . Provided the mass matrix of each element and the surrounding mesh-sizes obey the inequalities due to Bramble, Pasciak, and Steinbach or that neighboring element-sizes obey the global growth-condition due to Crouzeix and Thomée, is -stable: For all we have with a constant that is independent of, e.g., the dimension of .

This paper provides a more flexible version of the Bramble-Pasciak- Steinbach criterion for -stability on an abstract level. In its general version, (i) the criterion is applicable to all kind of finite element spaces and yields, in particular, -stability for nonconforming schemes on arbitrary (shape-regular) meshes; (ii) it is weaker than (i.e., implied by) either the Bramble-Pasciak-Steinbach or the Crouzeix-Thomée criterion for regular triangulations into triangles; (iii) it guarantees -stability of a priori for a class of adaptively-refined triangulations into right isosceles triangles.

     

On the primality of

For each prime , let be the product of the primes less than or equal to . We have greatly extended the range for which the primality of and are known and have found two new primes of the first form ( ) and one of the second (). We supply heuristic estimates on the expected number of such primes and compare these estimates to the number actually found.

     

On the stability of the

We prove the stability in of the projection onto a family of finite element spaces of conforming piecewise linear functions satisfying certain local mesh conditions. We give explicit formulae to check these conditions for a given finite element mesh in any number of spatial dimensions. In particular, stability of the projection in holds for locally quasiuniform geometrically refined meshes as long as the volume of neighboring elements does not change too drastically.

     

New convergence results on the generalized Richardson extrapolation process GREP for logarithmic sequences

Let as , where and are known for for some 0$">, but and the are not known. The generalized Richardson extrapolation process GREP is used in obtaining good approximations to , the limit or antilimit of as . The approximations to obtained via GREPare defined by the linear systems , , where is a decreasing positive sequence with limit zero. The study of GREP for slowly varying functions was begun in two recent papers by the author. For such we have as with possibly complex and . In the present work we continue to study the convergence and stability of GREPas it is applied to such with different sets of collocation points that have been used in practical situations. In particular, we consider the cases in which (i) are arbitrary, (ii) , (iii) as for some 0$">, (iv) for all , (v) , and (vi) for all .

     

Explicit primality criteria for

Deterministic polynomial time primality criteria for have been known since the work of Lucas in 1876-1878. Little is known, however, about the existence of deterministic polynomial time primality tests for numbers of the more general form , where is any fixed prime. When (p-1)/2$"> we show that it is always possible to produce a Lucas-like deterministic test for the primality of which requires that only modular multiplications be performed modulo , as long as we can find a prime of the form such that is not divisible by . We also show that for all with such a can be found very readily, and that the most difficult case in which to find a appears, somewhat surprisingly, to be that for . Some explanation is provided as to why this case is so difficult.

     

A posteriori error estimates for general numerical methods for Hamilton-Jacobi equations. Part I: The steady state case

A new upper bound is provided for the L-norm of the difference between the viscosity solution of a model steady state Hamilton-Jacobi equation, , and any given approximation, . This upper bound is independent of the method used to compute the approximation ; it depends solely on the values that the residual takes on a subset of the domain which can be easily computed in terms of . Numerical experiments investigating the sharpness of the a posteriori error estimate are given.

     

On a problem of Byrnes concerning polynomials with restricted coefficients, II

As in the earlier paper with this title, we consider a question of Byrnes concerning the minimal length of a polynomial with all coefficients in which has a zero of a given order at . In that paper we showed that for all and showed that the extremal polynomials for were those conjectured by Byrnes, but for that rather than . A polynomial with was exhibited for , but it was not shown there that this extremal was unique. Here we show that the extremal is unique. In the previous paper, we showed that is one of the 7 values or . Here we prove that without determining all extremal polynomials. We also make some progress toward determining . As in the previous paper, we use a combination of number theoretic ideas and combinatorial computation. The main point is that if is a primitive th root of unity where is a prime, then the condition that all coefficients of be in , together with the requirement that be divisible by puts severe restrictions on the possible values for the cyclotomic integer .

     

Solving norm equations in relative number fields using -units

In this paper, we are interested in solving the so-called norm equation , where is a given arbitrary extension of number fields and a given algebraic number of . By considering -units and relative class groups, we show that if there exists at least one solution (in , but not necessarily in ), then there exists a solution for which we can describe precisely its prime ideal factorization. In fact, we prove that under some explicit conditions, the -units that are norms are norms of -units. This allows us to limit the search for rational solutions to a finite number of tests, and we give the corresponding algorithm. When is an algebraic integer, we also study the existence of an integral solution, and we can adapt the algorithm to this case.

     

Security of the most significant bits of the Shamir message passing scheme

Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a ``hidden' element of a finite field of elements from rather short strings of the most significant bits of the remainder modulo of for several values of selected uniformly at random from . Unfortunately the applications to the computational security of most significant bits of private keys of some finite field exponentiation based cryptosystems given by Boneh and Venkatesan are not quite correct. For the Diffie-Hellman cryptosystem the result of Boneh and Venkatesan has been corrected and generalized in our recent paper. Here a similar analysis is given for the Shamir message passing scheme. The results depend on some bounds of exponential sums.

     

Rudin-Shapiro-like polynomials in

We examine sequences of polynomials with coefficients constructed using the iterations , where is the degree of and is the reciprocal polynomial of . If these generate the Rudin-Shapiro polynomials. We show that the norm of these polynomials is explicitly computable. We are particularly interested in the case where the iteration produces sequences with smallest possible asymptotic norm (or, equivalently, with largest possible asymptotic merit factor). The Rudin-Shapiro polynomials form one such sequence.

We determine all of degree less than 40 that generate sequences under the iteration with this property. These sequences have asymptotic merit factor 3. The first really distinct example has a of degree 19.

     

Finding strong pseudoprimes to several bases

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 primality testing algorithm which is not only easier to implement but also faster than either the Jacobi sum test or the elliptic curve test. Thanks to Pomerance et al. and Jaeschke, are known for . Upper bounds for were given by Jaeschke.

In this paper we tabulate all strong pseudoprimes (spsp's) to the first ten prime bases which have the form with odd primes and There are in total 44 such numbers, six of which are also spsp(31), and three numbers are spsp's to both bases 31 and 37. As a result the upper bounds for and are lowered from 28- and 29-decimal-digit numbers to 22-decimal-digit numbers, and a 24-decimal-digit upper bound for is obtained. The main tools used in our methods are the biquadratic residue characters and cubic residue characters. We propose necessary conditions for to be a strong pseudoprime to one or to several prime bases. Comparisons of effectiveness with both Jaeschke's and Arnault's methods are given.

     

The irreducibility of some level 1 Hecke polynomials

Let be the characteristic polynomial of the Hecke operator acting on the space of level 1 cusp forms . We show that is irreducible and has full Galois group over  for and ,  prime.

     

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 .

     

Directional Newton methods in variables

Directional Newton methods for functions of variables are shown to converge, under standard assumptions, to a solution of . The rate of convergence is quadratic, for near-gradient directions, and directions along components of the gradient of with maximal modulus. These methods are applied to solving systems of equations without inversion of the Jacobian matrix.

     

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.

     

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.

     

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 .

     

A stochastic particle numerical method for 3D Boltzmann equations without cutoff

Using the main ideas of Tanaka, the measure-solution of a -dimensional spatially homogeneous Boltzmann equation of Maxwellian molecules without cutoff is related to a Poisson-driven stochastic differential equation. Using this tool, the convergence to of solutions of approximating Boltzmann equations with cutoff is proved. Then, a result of Graham-Méléard is used and allows us to approximate with the empirical measure of an easily simulable interacting particle system. Precise rates of convergence are given. A numerical study lies at the end of the paper.