Prime-number algorithm for public-key systems. (English. Russian original) Zbl 0858.11065
Cybern. Syst. Anal. 31, No. 6, 878-885 (1995); translation from Kibern. Sist. Anal. 1995, No. 6, 112-120 (1995).
The problem of generating prime numbers for use in cryptographic systems is addressed. A few of the known primality tests are reviewed, including pseudoprime, deterministic and hypothesis tests. Other techniques that have been used for generating primes are briefly noted and a new recursive technique described.
Reviewer: I.F.Blake (Palo Alto)
MSC:
| 11Y11 | Primality |
| 94A60 | Cryptography |
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
| 11Y16 | Number-theoretic algorithms; complexity |
Keywords:
public-key systems; pseudoprime test; deterministic test; hypothesis test; generating prime numbers; cryptographic systemsSoftware:
ECPPReferences:
| [1] | International Standard ISO/IEC 9594-8, 1st ed. (1990), pp. 12–15. |
| [2] | National Institute of Standards and Technology (NIST), Announcement and Specifications for a Digital Signature Standard (DSS) (Aug. 19, 1992). |
| [3] | D. L. Messy, ”An introduction to modern cryptology,” Proc. IEEE,76, No. 5, 24–42 (1988). |
| [4] | T. El Gamal, ”A public key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Trans. Inform. Theory,31, 469–472 (1985). · Zbl 0571.94014 · doi:10.1109/TIT.1985.1057074 |
| [5] | S. Peter, ”LUC,” Dr. Dobb’s J., 44–49 (Jan. 1993). |
| [6] | 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). · Zbl 0823.94015 |
| [7] | 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). · Zbl 0375.68023 · doi:10.1109/TIT.1978.1055817 |
| [8] | J. M. Pollard, ”Theorems on factorization and primality testing,” Proc. Cambridge Phil. Soc.,76, 521–528 (1974). · Zbl 0294.10005 · doi:10.1017/S0305004100049252 |
| [9] | E. Bach and J. Shallit, ”Factoring with cyclomatic polynomials,” Math. Comp.,52, 201–219 (1989). · Zbl 0661.10008 · doi:10.1090/S0025-5718-1989-0947467-1 |
| [10] | D. E. Knuth and Trabb Pardo, ”Analysis of simple factorization algorithms,” Theor. Comput. Sci.,3, 321–348 (1976). · Zbl 0362.10006 · doi:10.1016/0304-3975(76)90050-5 |
| [11] | C. F. Gauss, Works in the Theory of Numbers [Russian translation], Izv. AN SSSR, Moscow (1959). · Zbl 0091.12507 |
| [12] | C. Hooley, Applications of Sieve Methods to the Theory of Numbers [Russian translation], Nauka, Moscow (1987). · Zbl 0624.10037 |
| [13] | V. R. Pratt, ”Every prime has a succinct certificate,” SIAM J. Comput.,4, 214–220 (1975). · Zbl 0316.68031 · doi:10.1137/0204018 |
| [14] | G. L. Miller, ”Rieman hypothesis and methods of testing primality of numbers,” Kibern. Sb., No. 23, 31–50 (1986). · Zbl 0607.68028 |
| [15] | L. Adleman, C. Pomerance, and R. S. Rumely, ”On distinguishing prime numbers from composite numbers,” Ann. Math.,117, 173–206 (1983). · Zbl 0526.10004 · doi:10.2307/2006975 |
| [16] | H. W. Lenstra, ”Factoring integers with elliptic curves,” Ann. Math.,126, 649–673 (1987). · Zbl 0629.10006 · doi:10.2307/1971363 |
| [17] | 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. |
| [18] | A. O. Atkin and F. Morain, ”Elliptic curves and primality proving,” Math. Comp.,61, No. 203, 29–69 (1993). · Zbl 0792.11056 · doi:10.1090/S0025-5718-1993-1199989-X |
| [19] | H. Williams, ”Testing numbers for primality by computer,” Kibern. Sb., No. 23, 51–99 (1986). · Zbl 0607.10004 |
| [20] | O. N. Vasilenko, ”Modern methods of primality testing,” Kibern. Sb., No. 25, 162–188 (1988). · Zbl 0669.10013 |
| [21] | J. D. Dixon, ”Factorization and primality testing,” Am. Math. Monthly,91, No. 6, 333–352 (1984). · Zbl 0548.10003 · doi:10.2307/2322136 |
| [22] | J. Gordon, ”Strong RSA keys,” Electronics Lett.,20, No. 5, 514–516. |
| [23] | 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. |
| [24] | W. Bosma, ”Explicit primality criteria forh{\(\cdot\)}2 k {\(\pm\)}1,” Math. Comp.,61, No. 203, 97–111 (1993). · Zbl 0817.11060 |
| [25] | A. A. Bukhshtab, Theory of Numbers [in Russian], Prosveshchenie, Moscow (1966). · Zbl 0144.27402 |
| [26] | R. G. E. Pinch, ”The Carmichael numbers up to 1015,” Math. Comp.,61, No. 203, 381–391 (1993). · Zbl 0780.11069 |
| [27] | S. H. Kim and C. Pomerance, ”The probability that a random probable prime is composite,” Math. Comp.,53, 721–741 (1989). · Zbl 0687.10001 · doi:10.1090/S0025-5718-1989-0982368-4 |
| [28] | M. O. Rabin, ”Probabilistic algorithm for primality testing,” J. Number Theory,12, 128–138 (1980). · Zbl 0426.10006 · doi:10.1016/0022-314X(80)90084-0 |
| [29] | 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). · Zbl 0788.11059 |
| [30] | P. Beauchemin and G. Brassard, ”The generation of random numbers that are probably prime,” J. Cryptol.,1, 53–64 (1988). · Zbl 0669.10014 · doi:10.1007/BF00206325 |
| [31] | C. Pomerance, J. L. Selfridge, and J. Wagstaff, ”The pseudoprimes to 25{\(\cdot\)}109,” Math. Comp.,35, 1003–10026 (1980). · Zbl 0444.10007 |
| [32] | G. Jaeschke, ”On strong pseudoprimes to several bases,” Math. Comp.,61, No. 204, 915–926 (1993). · Zbl 0802.11001 · doi:10.1090/S0025-5718-1993-1192971-8 |
| [33] | A. O. Gel’fond and Yu. V. Linnik, Elementary Methods in Analytical Number Theory [in Russian], Fizmatgiz, Moscow (1962). |
| [34] | D. Knuth, The Art of Computer Programming [Russian translation], Vol. 2, Mir, Moscow (1977). · Zbl 0417.68001 |
| [35] | V. N. Chubarikov, ”Problems of the theory of primes connected with classical theorems of P. L. Chebyshev,” Vestnik MGU, No. 5, 19–24 (1991). · Zbl 0739.01015 |
| [36] | E. Trost, Prime Numbers [Russian translation], Fizmatgiz, Moscow (1959). |
| [37] | H. C. Williams and C. Schmid, ”Some remarks concerning the MIT public key cryptosystem,” BIT,19, No. 4, 525–538 (1979). · Zbl 0418.94010 · doi:10.1007/BF01931269 |
| [38] | 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. |
| [39] | 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. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
