Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
Articles 1 - 6 of 6
Full-Text Articles in Physical Sciences and Mathematics
Computing Prime Harmonic Sums, Eric Bach, Dominic Klyve, Jonathan P. Sorenson
Computing Prime Harmonic Sums, Eric Bach, Dominic Klyve, Jonathan P. Sorenson
Jonathan P. Sorenson
We discuss a method for computing Σ �≤� 1/�, using time about �2/3 and space about �1/3. It is based on the Meissel-Lehmer algorithm for computing the prime-counting function �(�), which was adapted and improved by Lagarias, Miller, and Odlyzko. We used this algorithm to determine the first point at which the prime harmonic sum first crosses.
Computing Prime Harmonic Sums, Eric Bach, Dominic Klyve, Jonathan P. Sorenson
Computing Prime Harmonic Sums, Eric Bach, Dominic Klyve, Jonathan P. Sorenson
Jonathan P. Sorenson
We discuss a method for computing Σ �≤� 1/�, using time about �2/3 and space about �1/3. It is based on the Meissel-Lehmer algorithm for computing the prime-counting function �(�), which was adapted and improved by Lagarias, Miller, and Odlyzko. We used this algorithm to determine the first point at which the prime harmonic sum first crosses.
Modular Exponentiation Via The Explicit Chinese Remainder Theorem, Daniel J. Bernstein, Jonathan P. Sorenson
Modular Exponentiation Via The Explicit Chinese Remainder Theorem, Daniel J. Bernstein, Jonathan P. Sorenson
Jonathan P. Sorenson
In this paper we consider the problem of computing xe mod m for large integers x, e, and m. This is the bottleneck in Rabin’s algorithm for testing primality, the Diffie-Hellman algorithm for exchanging cryptographic keys, and many other common algorithms.
Modular Exponentiation Via The Explicit Chinese Remainder Theorem, Daniel J. Bernstein, Jonathan P. Sorenson
Modular Exponentiation Via The Explicit Chinese Remainder Theorem, Daniel J. Bernstein, Jonathan P. Sorenson
Jonathan P. Sorenson
In this paper we consider the problem of computing xe mod m for large integers x, e, and m. This is the bottleneck in Rabin’s algorithm for testing primality, the Diffie-Hellman algorithm for exchanging cryptographic keys, and many other common algorithms.
The Pseudosquares Prime Sieve, Jonathan P. Sorenson
The Pseudosquares Prime Sieve, Jonathan P. Sorenson
Jonathan P. Sorenson
We present the pseudosquares prime sieve, which finds all primes up to n.
Fast Bounds On The Distribution Of Smooth Numbers, Scott T. Parsell, Jonathan P. Sorenson
Fast Bounds On The Distribution Of Smooth Numbers, Scott T. Parsell, Jonathan P. Sorenson
Jonathan P. Sorenson
In this paper we present improvements to Bernstein’s algorithm, which finds rigorous upper and lower bounds for (x, y).