Minimizing the time of detection of large (probably) prime numbers

Dragan Novak Vidakovic

Abstract


In this paper we present the experimental results that more clearly than any theory suggest an answer to the question: when in detection of large (probably) prime numbers to apply, a very resource demanding, Miller-Rabin algorithm. Or, to put it another way, when the dividing by first several tens of prime numbers should be replaced by primality testing? Goldbach hypothesis may also be helpful in intention to detect large prime numbers as quickly as we can, which we will also show in this paper.


Keywords


Public key cryptosystems; Prime numbers; Trial division; Miller-Rabin algorithm; Goldbach conjecture

Full Text:

PDF

References


A. Menezes, P.C. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, CRC Press, New York, 1997.

D. Vidakovic, “Analysis and implementation of asymmetric algorithms for data secrecy and integrity protectionâ€, Master Thesis (mentor J. Golic), Faculty of Electrical Engineering, Belgrade, Serbia, 1999.

Goldbach, C., Letter to L. Euler, June 7, 1742.

Sylvester, J. J., “On the partition of an even nimber into two primesâ€, Proc. London Math. Soc., s1-4(1). 4-6. 1871.

Cramer, H., “On the distribution of primesâ€, Proc. Camb. Phil. Soc., 20.272-280. 1920

Granvile, A., “Harald Cramer and the Distribution of Prime Numbersâ€, Scand. Actuarial J., 1. 12-28. 1995

Cojocaru, A.C. and Murty, M.R., An introduction to sieve methods and their applications, Cambridge University Press, Cambridge, 2005

Koblitz N., “Elliptic Curve Cryptosystemsâ€, Mathematics of Computation, 48, pp. 203-209,1987.

D. Vidakovic, D. Parezanovic, “Generating keys in elliptic curve cryptosystemsâ€, International Journal of Computer Science and Business Informatics, Vol. 4, No 1. August 2013

D. Vidakovic, D. Simic :â€A Novel Approach to Building Secure Systemsâ€, Second International Conference on Availability, Reliability and Security, In 1th IEEE International Workshop on Secure Software Engineering (SecSE 2007), Vienna, 2007., Austria, pp 1074-1081


Refbacks

  • There are currently no refbacks.


ISSN: 1694-2507 (Print)

ISSN: 1694-2108 (Online)