We present a new algorithm that finds all primes up to n using at most O(n/log log n) arithmetic operations and O(n/(log n log log n)) space. This algorithm is an improvement of a linear prime number sieve due to Prit...
详细信息
We present a new algorithm that finds all primes up to n using at most O(n/log log n) arithmetic operations and O(n/(log n log log n)) space. This algorithm is an improvement of a linear prime number sieve due to Pritchard. Our new algorithm matches the running time of the best previous prime number sieve, but uses less space by a factor of Theta(log n). In addition, we present the results of our implementations of most known prime number sieves.
We show that a shortest vector of a 2-dimensional integral lattice with respect to the l(oc)-norm can be computed with a constant number of extended-gcd computations, one common-convergent computation and a constant n...
详细信息
We show that a shortest vector of a 2-dimensional integral lattice with respect to the l(oc)-norm can be computed with a constant number of extended-gcd computations, one common-convergent computation and a constant number of arithmetic operations. It follows that in two dimensions, a fast basis-reduction algorithm can be solely based on Schonhage's classical algorithm on the fast computation of continued fractions and the reduction algorithm of Gauss. (C) 2001 Elsevier Science B.V. All rights reserved.
A positive integer n is a perfect power if there exist integers x and k, both at least 2, such that n = x(k). The usual algorithm to recognize perfect powers computes approximate kth roots for k less-than-or-equal-to ...
详细信息
A positive integer n is a perfect power if there exist integers x and k, both at least 2, such that n = x(k). The usual algorithm to recognize perfect powers computes approximate kth roots for k less-than-or-equal-to log2 n, and runs in time O(log3 n log log log n). First we improve this worst-case running time to O(log3 n) by using a modified Newton's method to compute approximate kth roots. Parallelizing this gives an NC2 algorithm. Second, we present a sieve algorithm that avoids kth-root computations by seeing if the input n is a perfect kth power modulo small primes. If n is chosen uniformly from a large enough interval, the average running time is O(log2 n). Third, we incorporate trial division to give a sieve algorithm with an average running time of O(log2 n/log2 log n) and a median running time of O(log n). The two sieve algorithms use a precomputed table of small primes. We give a heuristic argument and computational evidence that the largest prime needed in this table is (logn)1+o(1);assuming the Extended Riemann Hypothesis, primes up to (log n)2+o(1) suffice. The table can be computed in time roughly proportional to the largest prime it contains. We also present computational results indicating that our sieve algorithms perform extremely well in practice.
Each and Sorenson present two algorithms for testing whether a number n is a perfect power, with average running time O(log(2) n) under the assumption that n is chosen uniformly from an interval of length at least (lo...
详细信息
Each and Sorenson present two algorithms for testing whether a number n is a perfect power, with average running time O(log(2) n) under the assumption that n is chosen uniformly from an interval of length at least (log n)(3log log log n). We modify their algorithms to reduce the interval to polynomial size.
We present a randomized parallel algorithm that computes the greatest common divisor of two integers of n bits in length with probability 1-o(1) that takes O(n log log n/log n) time using O (n(6+epsilon)) processors f...
详细信息
We present a randomized parallel algorithm that computes the greatest common divisor of two integers of n bits in length with probability 1-o(1) that takes O(n log log n/log n) time using O (n(6+epsilon)) processors for any epsilon > 0 on the EREW PRAM parallel model of computation. The algorithm either gives a correct answer or reports failure. We believe this to be the first randomized sublinear time algorithm on the EREW PRAM for this problem. (C) 2009 Elsevier B.V. All rights reserved.
This paper is primarily concerned with the definition of perfect integers in the Gaussian plane and then testing their existence with the help of number theoretic algorithms and other computational tools. Here, we dea...
详细信息
ISBN:
(纸本)9781467373494
This paper is primarily concerned with the definition of perfect integers in the Gaussian plane and then testing their existence with the help of number theoretic algorithms and other computational tools. Here, we deal with Gaussian primes, their primary counterparts (which are essentially developments on primes), and the identification of Gaussian perfect integer, if any. Experimental results show that there is no definite indication of any Gaussian perfect integer up to a very large norm.
暂无评论