Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Theory and Algorithms

2010

Algorithm

Articles 1 - 4 of 4

Full-Text Articles in Physical Sciences and Mathematics

Modular Exponentiation Via The Explicit Chinese Remainder Theorem, Daniel J. Bernstein, Jonathan P. Sorenson Feb 2010

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.

Go to article

Modular Exponentiation Via The Explicit Chinese Remainder Theorem, Daniel J. Bernstein, Jonathan P. Sorenson Feb 2010

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.

Go to article

The Pseudosquares Prime Sieve, Jonathan P. Sorenson Feb 2010

The Pseudosquares Prime Sieve, Jonathan P. Sorenson

Jonathan P. Sorenson

We present the pseudosquares prime sieve, which finds all primes up to n.

Go to article

Fast Bounds On The Distribution Of Smooth Numbers, Scott T. Parsell, Jonathan P. Sorenson Feb 2010

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).

Go to article