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.
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).
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. .
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.
In this paper we prove convergence and error estimates for the so-called 3-field formulation using piecewise linear finite elements stabilized with boundary bubbles. Optimal error bounds are proved in and in the broken norm for the internal variable , and in suitable weighted norms for the other variables and . 相似文献
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 .
We define a Carmichael number of order to be a composite integer such that th-power raising defines an endomorphism of every -algebra that can be generated as a -module by elements. We give a simple criterion to determine whether a number is a Carmichael number of order , and we give a heuristic argument (based on an argument of Erdos for the usual Carmichael numbers) that indicates that for every there should be infinitely many Carmichael numbers of order . The argument suggests a method for finding examples of higher-order Carmichael numbers; we use the method to provide examples of Carmichael numbers of order .
For the construction of an interpolatory integration rule on the unit circle with nodes by means of the Laurent polynomials as basis functions for the approximation, we have at our disposal two nonnegative integers and which determine the subspace of basis functions. The quadrature rule will integrate correctly any function from this subspace. In this paper upper bounds for the remainder term of interpolatory integration rules on are obtained. These bounds apply to analytic functions up to a finite number of isolated poles outside In addition, if the integrand function has no poles in the closed unit disc or is a rational function with poles outside , we propose a simple rule to determine the value of and hence in order to minimize the quadrature error term. Several numerical examples are given to illustrate the theoretical results.
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.
This paper is concerned with the construction and analysis of wavelet-based adaptive algorithms for the numerical solution of elliptic equations. These algorithms approximate the solution of the equation by a linear combination of wavelets. Therefore, a benchmark for their performance is provided by the rate of best approximation to by an arbitrary linear combination of wavelets (so called -term approximation), which would be obtained by keeping the largest wavelet coefficients of the real solution (which of course is unknown). The main result of the paper is the construction of an adaptive scheme which produces an approximation to with error in the energy norm, whenever such a rate is possible by -term approximation. The range of 0$"> for which this holds is only limited by the approximation properties of the wavelets together with their ability to compress the elliptic operator. Moreover, it is shown that the number of arithmetic operations needed to compute the approximate solution stays proportional to . The adaptive algorithm applies to a wide class of elliptic problems and wavelet bases. The analysis in this paper puts forward new techniques for treating elliptic problems as well as the linear systems of equations that arise from the wavelet discretization.
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.
The algorithm is a structure-preserving algorithm for computing the spectrum of symplectic matrices. Any symplectic matrix can be reduced to symplectic butterfly form. A symplectic matrix in butterfly form is uniquely determined by parameters. Using these parameters, we show how one step of the symplectic algorithm for can be carried out in arithmetic operations compared to arithmetic operations when working on the actual symplectic matrix. Moreover, the symplectic structure, which will be destroyed in the numerical process due to roundoff errors when working with a symplectic (butterfly) matrix, will be forced by working just with the parameters.
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 .
A systematic search for optimal lattice rules of specified trigonometric degree over the hypercube has been undertaken. The search is restricted to a population of lattice rules . This includes those where the dual lattice may be generated by points for each of which . The underlying theory, which suggests that such a restriction might be helpful, is presented. The general character of the search is described, and, for , and , , a list of -optimal rules is given. It is not known whether these are also optimal rules in the general sense; this matter is discussed.