After the description of the models of Kubilius, Novoselov and Schwarz, and Spilker, respectively, a probability theory for finitely additive probability measures is developed by use of the Stone-Cech compactification...
详细信息
After the description of the models of Kubilius, Novoselov and Schwarz, and Spilker, respectively, a probability theory for finitely additive probability measures is developed by use of the Stone-Cech compactification of N. The new model is applied to the result of Erdos and Wintner about the limit distribution of additive functions and to the famous result of Szemeredi in combinatorial numbertheory. Further, it is explained how conjectures on prime values of irreducible polynomials are used in the search for large prime twins and Sophie Germain primes. (C) 2002 Elsevier Science Ltd. All rights reserved.
This article describes progress towards a conjecture of S.W. Graham. He conjectured that the number C-3(X) of Carmichael numbers up to X with three prime factors is = 1. He showed that his conjecture is true for X 10(...
详细信息
This article describes progress towards a conjecture of S.W. Graham. He conjectured that the number C-3(X) of Carmichael numbers up to X with three prime factors is <=root X for all X >= 1. He showed that his conjecture is true for X <= 10(16) and X>10(126). In this article, it is shown that the conjecture is true for X <= 10(24) and X > 2 * 10(40). In both cases, analytical methods establish the conjecture for large X and tables of Carmichael numbers are used for small X. (c) 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
We consider synthesis problems for a discrete event model of a real time distributed computational system. The model reflects information exchange events between software units of the system and is intended to constru...
详细信息
We consider synthesis problems for a discrete event model of a real time distributed computational system. The model reflects information exchange events between software units of the system and is intended to construct special test sequences that detect faults in these exchanges.
Public-key cryptosystems base their security on well-known number-theoretic problems, such as factorisation of a given number n . Hence, prime number generation is an absolute requirement. Many prime number generation...
详细信息
Public-key cryptosystems base their security on well-known number-theoretic problems, such as factorisation of a given number n . Hence, prime number generation is an absolute requirement. Many prime number generation techniques have been proposed up-to-date, which differ mainly in terms of complexity, certainty and speed. Pocklington's theorem, if implemented, can guarantee the generation of a true prime. The proposed implementation exhibits low complexity at the expense of long execution time.
In August 2002, Agrawal, Kayal and Saxena announced the first deterministic and polynomial-time primality-testing algorithm. For an input n, the Agarwal-Kayal-Saxena (AKS) algorithm runs in time Omicron (log(7.5) n) (...
详细信息
In August 2002, Agrawal, Kayal and Saxena announced the first deterministic and polynomial-time primality-testing algorithm. For an input n, the Agarwal-Kayal-Saxena (AKS) algorithm runs in time Omicron (log(7.5) n) (heuristic time Omicron (log(6) n)). Verification takes roughly the same amount of time. On the other hand, the Elliptic Curve Primality Proving algorithm (ECPP) runs in random heuristic time 6 (log6 n) (some variant has heuristic time complexity Omicron(log(4) n)) and generates certificates which can be easily verified. However, it is hard to analyze the provable time complexity of ECPP even for a small portion of primes. More recently, Berrizbeitia gave a variant of the AKS algorithm, in which some primes (of density Omicron(1/log(2) n)) cost much less time to prove than a general prime does. Building on these celebrated results, this paper explores the possibility of designing a randomized primality-proving algorithm based on the AKS algorithm. We first generalize Berrizbeitia's algorithm to one which has higher density (Omega (1/log log n)) of primes whose primality can be proved in time complexity 6(log4 n). For a general prime, one round of ECPP is deployed to reduce its primality proof to the proof of a random easily
Sturmian sequences appear in the work of Markoff on approximations of real numbers and minima of quadratic functions. In particular, Christoffel words, or equivalently pairs of relatively prime nonnegative integers, p...
详细信息
Sturmian sequences appear in the work of Markoff on approximations of real numbers and minima of quadratic functions. In particular, Christoffel words, or equivalently pairs of relatively prime nonnegative integers, parametrize the Markoff numbers. It was asked by Frobenius if this parametrization is injective. We answer this conjecture for a particular subclass of these numbers, and show that a special Sturmian sequence of irrational slope determines the order of the Markoff numbers in this subclass. (C) 2009 Elsevier B.V. All rights reserved.
In this paper, we present a mathematical analysis of some methods for generating amicable numbers, with an emphasis on proving the correctness of the methods and the correctness of the algorithms based on these methods.
In this paper, we present a mathematical analysis of some methods for generating amicable numbers, with an emphasis on proving the correctness of the methods and the correctness of the algorithms based on these methods.
In the present paper we describe and analyse a sieving algorithm for determining prime numbers. This external memory algorithm contains several parameters which are related to the sizes of the levels in the memory hie...
详细信息
In the present paper we describe and analyse a sieving algorithm for determining prime numbers. This external memory algorithm contains several parameters which are related to the sizes of the levels in the memory hierarchy. We examine how we should choose the values of these parameters in order to obtain an optimal running time. We compare the running times obtained by varying the parameters. We conclude that in this specific problem fine tuning pays off as we got a speed-up of almost 40%. (c) 2007 Elsevier Ltd. All rights reserved.
We introduce a new algorithm to compute the zeta function of. a curve over a finite field. This method extends previous work of ours to all curves for which a good lift to characteristic zero is known. We develop all ...
详细信息
We introduce a new algorithm to compute the zeta function of. a curve over a finite field. This method extends previous work of ours to all curves for which a good lift to characteristic zero is known. We develop all the necessary bounds, analyse the complexity of the algorithm and provide a complete implementation. (C) 2017 Elsevier Inc. All rights reserved.
Let k and n be positive integers, n > k. Define r(n, k) to be the minimum positive value of vertical bar root a(1) + ... + root a(k) - root b(1) - ... - root bk vertical bar where a(1), a(2),, a(k), b(1), b(2), ..,...
详细信息
Let k and n be positive integers, n > k. Define r(n, k) to be the minimum positive value of vertical bar root a(1) + ... + root a(k) - root b(1) - ... - root bk vertical bar where a(1), a(2),, a(k), b(1), b(2), .., b(k) are positive integers no larger than n. Define R(n, k) to be log r(n, k). It is important to find tight bounds for r(n, k) and R(n, k), in connection to the sum-of-square-roots problem, a famous open problem in computational geometry. The current best lower bound and upper bound are far apart. In this paper, we prove an upper bound of 2(O)((n/logn)) for R(n, k), which is better than the best known result O(2(2k) log n) whenever n <= ck log k for some constant c. In particular, our result implies an algorithm subexponential in k (i.e. with time complexity 2(o(k))(log n)(O(1))) to compare two sums of k square roots of integers of value o(k log k). We then present an algorithm to find r(n, k) exactly in n(k+o(k)) time and in n([k/2]+o(k)) space. As an example, we are able to compute r(100, 7) exactly in a few hours on a single PC. The numerical data indicate that the root separation bound is very far away from the true value of r(n. k). (C) 2011 Elsevier B.V. All rights reserved.
暂无评论