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.
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 .
In the present paper we discuss the methods of Qin and Skaba, and we apply our results to the field
In the Appendix at the end of the paper K. Belabas and H. Gangl present the results of their computation of for some other values of The results agree with the conjectural structure of given in the paper by Browkin and Gangl.
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.
We propose an efficient search algorithm to solve the equation for a fixed value of 0$">. By parametrizing , this algorithm obtains and (if they exist) by solving a quadratic equation derived from divisors of . Thanks to the use of several efficient number-theoretic sieves, the new algorithm is much faster on average than previous straightforward algorithms. We performed a computer search for six values of below 1000 for which no solution had previously been found. We found three new integer solutions for and 931 in the range 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.
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.
The iteratively regularized Gauss-Newton method is applied to compute the stable solutions to nonlinear ill-posed problems when the data is given approximately by with . In this method, the iterative sequence is defined successively by
where is an initial guess of the exact solution and is a given decreasing sequence of positive numbers admitting suitable properties. When is used to approximate , the stopping index should be designated properly. In this paper, an a posteriori stopping rule is suggested to choose the stopping index of iteration, and with the integer determined by this rule it is proved that
with a constant independent of , where denotes the iterative solution corresponding to the noise free case. As a consequence of this result, the convergence of is obtained, and moreover the rate of convergence is derived when satisfies a suitable ``source-wise representation". The results of this paper suggest that the iteratively regularized Gauss-Newton method, combined with our stopping rule, defines a regularization method of optimal order for each . Numerical examples for parameter estimation of a differential equation are given to test the theoretical results.
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.
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 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.
We give a method for efficiently computing isomorphisms between towers of Artin-Schreier extensions over a finite field. We find that isomorphisms between towers of degree over a fixed field can be computed, composed, and inverted in time essentially linear in . The method relies on an approximation process.
. For given and , the extremal basis has the largest possible extremal -range
We give an algorithm to determine the -range. We prove some properties of the -range formula, and we conjecture its form for the extremal -range. We consider parameter bases , where the basis elements are given functions of . For we conjecture the extremal parameter bases for .