Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
International Standard ISO/IEC 9594-8, 1st ed. (1990), pp. 12–15.
National Institute of Standards and Technology (NIST), Announcement and Specifications for a Digital Signature Standard (DSS) (Aug. 19, 1992).
D. L. Messy, “An introduction to modern cryptology,” Proc. IEEE,76, No. 5, 24–42 (1988).
T. El Gamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Trans. Inform. Theory,31, 469–472 (1985).
S. Peter, “LUC,” Dr. Dobb's J., 44–49 (Jan. 1993).
V. M. Sidel'nikov, M. A. Cherepnev, and V. V. Yashchenko, “Public key distribution system based on noncommutative semigroups,” Dokl. RAN,332, No. 5, 566–567 (1993).
S. C. Pohling and M. E. Hellman, “An improved algorithm for computing logarithms overGF(p) and its cryptographic significance,” IEEE Trans. Inform. Theory,24, 106–110 (1978).
J. M. Pollard, “Theorems on factorization and primality testing,” Proc. Cambridge Phil. Soc.,76, 521–528 (1974).
E. Bach and J. Shallit, “Factoring with cyclomatic polynomials,” Math. Comp.,52, 201–219 (1989).
D. E. Knuth and Trabb Pardo, “Analysis of simple factorization algorithms,” Theor. Comput. Sci.,3, 321–348 (1976).
C. F. Gauss, Works in the Theory of Numbers [Russian translation], Izv. AN SSSR, Moscow (1959).
C. Hooley, Applications of Sieve Methods to the Theory of Numbers [Russian translation], Nauka, Moscow (1987).
V. R. Pratt, “Every prime has a succinct certificate,” SIAM J. Comput.,4, 214–220 (1975).
G. L. Miller, “Rieman hypothesis and methods of testing primality of numbers,” Kibern. Sb., No. 23, 31–50 (1986).
L. Adleman, C. Pomerance, and R. S. Rumely, “On distinguishing prime numbers from composite numbers,” Ann. Math.,117, 173–206 (1983).
H. W. Lenstra, “Factoring integers with elliptic curves,” Ann. Math.,126, 649–673 (1987).
S. Goldwasser and J. Killian, “Almost all primes can be quickly certified,” Proc. 18th Ann. ACM Symp. on Theory of Computing (1986), pp. 316–329.
A. O. Atkin and F. Morain, “Elliptic curves and primality proving,” Math. Comp.,61, No. 203, 29–69 (1993).
H. Williams, “Testing numbers for primality by computer,” Kibern. Sb., No. 23, 51–99 (1986).
O. N. Vasilenko, “Modern methods of primality testing,” Kibern. Sb., No. 25, 162–188 (1988).
J. D. Dixon, “Factorization and primality testing,” Am. Math. Monthly,91, No. 6, 333–352 (1984).
J. Gordon, “Strong RSA keys,” Electronics Lett.,20, No. 5, 514–516.
N. Demytko, “Generating multiprecision integers with guaranteed primality,” in: Computer Security in the Information Age: Proc. 5th IFIP Int. Conf. on Computer Security, IFIP/SEC '88, Gold Coast, Queensland, Australia, May 19–21 (1988), pp. 1–8.
W. Bosma, “Explicit primality criteria forh·2k±1,” Math. Comp.,61, No. 203, 97–111 (1993).
A. A. Bukhshtab, Theory of Numbers [in Russian], Prosveshchenie, Moscow (1966).
R. G. E. Pinch, “The Carmichael numbers up to 1015,” Math. Comp.,61, No. 203, 381–391 (1993).
S. H. Kim and C. Pomerance, “The probability that a random probable prime is composite,” Math. Comp.,53, 721–741 (1989).
M. O. Rabin, “Probabilistic algorithm for primality testing,” J. Number Theory,12, 128–138 (1980).
I. Damgard, P. Landrock, and C. Pomerance, “Average case error estimates for the strong probable prime test,” Math. Comp.,61, No. 203, 177–195 (1993).
P. Beauchemin and G. Brassard, “The generation of random numbers that are probably prime,” J. Cryptol.,1, 53–64 (1988).
C. Pomerance, J. L. Selfridge, and J. Wagstaff, “The pseudoprimes to 25·109,” Math. Comp.,35, 1003–10026 (1980).
G. Jaeschke, “On strong pseudoprimes to several bases,” Math. Comp.,61, No. 204, 915–926 (1993).
A. O. Gel'fond and Yu. V. Linnik, Elementary Methods in Analytical Number Theory [in Russian], Fizmatgiz, Moscow (1962).
D. Knuth, The Art of Computer Programming [Russian translation], Vol. 2, Mir, Moscow (1977).
V. N. Chubarikov, “Problems of the theory of primes connected with classical theorems of P. L. Chebyshev,” Vestnik MGU, No. 5, 19–24 (1991).
E. Trost, Prime Numbers [Russian translation], Fizmatgiz, Moscow (1959).
H. C. Williams and C. Schmid, “Some remarks concerning the MIT public key cryptosystem,” BIT,19, No. 4, 525–538 (1979).
A. M. Kudin, “A constructive algorithm to find prime numbers for public key systems,” in: Symposium on Issues of Computational Optimization [in Russian], abstracts of papers, Kiev (1993), p. 90.
A. M. Kudin, An Estimate of the Prime Multiplier in an Algorithm to Find Prime Numbers Satisfying Special Conditions [in Russian], Kiev (1994). Unpublished manuscript, GNTB Ukr. 15.05.94, No. 979-Uk94.
Additional information
Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 112–120, November–December, 1995.
Rights and permissions
About this article
Cite this article
Kudin, A.M. Prime-number algorithm for public-key systems. Cybern Syst Anal 31, 878–885 (1995). https://doi.org/10.1007/BF02366625
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02366625