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 .
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 . 相似文献
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
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.
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. .
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.
In this paper we consider the problem of inverting an circulant matrix with entries over . We show that the algorithm for inverting circulants, based on the reduction to diagonal form by means of FFT, has some drawbacks when working over . We present three different algorithms which do not use this approach. Our algorithms require different degrees of knowledge of and , and their costs range, roughly, from to operations over . Moreover, for each algorithm we give the cost in terms of bit operations. We also present an algorithm for the inversion of finitely generated bi-infinite Toeplitz matrices. The problems considered in this paper have applications to the theory of linear cellular automata.
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.
Bounds for the distance between adjacent zeros of cylinder functions are given; and are such that ; stands for the th positive zero of the cylinder (Bessel) function , , .
These bounds, together with the application of modified (global) Newton methods based on the monotonic functions and , give rise to forward ( ) and backward ( ) iterative relations between consecutive zeros of cylinder functions.
The problem of finding all the positive real zeros of Bessel functions for any real and inside an interval , 0$">, is solved in a simple way.
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).
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.
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.
Power series expansions for the even and odd angular Mathieu functions and , with small argument , are derived for general integer values of . The expansion coefficients that we evaluate are also useful for the calculation of the corresponding radial functions of any kind.
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.
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.
Using a carefully optimized segmented sieve and an efficient checking algorithm, the Goldbach conjecture has been verified and is now known to be true up to . The program was distributed to various workstations. It kept track of maximal values of the smaller prime in the minimal partition of the even numbers, where a minimal partition is a representation with being composite for all . The maximal prime needed in the considered interval was found to be 5569 and is needed for the partition 389965026819938 = 5569 + 389965026814369.
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.