Sequences of numbers generated by addition in formal groups and new primality and factorization tests. (English) Zbl 0614.10004

Chudnovsky, D. V.; Chudnovsky, G. V.

Adv. Appl. Math. 7, 385-434 (1986).

The authors give a comprehensive study of the relation of algebroid formal group laws to primality and factorization. The Fermat test and the Lucas test were perceived as special cases once the Lenstra test was studied. The addition law of elliptic curves in Weierstrass form is subject to a very detailed analysis, as well as other implementations, e.g., in Jacobi form. New results are also given for factoring \(n=\text{Norm}(\alpha)\) in K/\({\mathbb{Q}}\) based on the (partial) factorization of \(\text{Norm}(\alpha \pm 1)\). Elliptic divisibility sequences of Ward are also used for factorization and to make lists of probable primes.
In conclusion, the authors make the programmatic remark: ”A large field for future studies is opened by the possibility of considering other algebraic laws of addition related to the Frobenius operator (say, cubic surfaces or other intermediate Jacobians)”. There is a rather large bibliography of classical and contemporary sources, and it is very difficult to select a subset to cite because of the breadth of the article.

Reviewer: H.Cohn

MSC:

11Y11	Primality
11Y05	Factorization
11G05	Elliptic curves over global fields
11G10	Abelian varieties of dimension \(> 1\)
14L05	Formal groups, \(p\)-divisible groups

Keywords:

primality tests; implementations; factorization algorithms; abelian varieties; computational number theory; formal group laws; elliptic curves; bibliography

References:

[1]	E. Bach and J. Shallitin; E. Bach and J. Shallitin · Zbl 0661.10008
[2]	Baker, H. F., Abel’s Theorem and the Allied Theory Including the Theory of the Theta Function (1897), Cambridge Univ. Press · JFM 28.0331.01
[3]	Bell, E. T., Analogies between the \(u_n, v_{n\) · JFM 49.0097.05
[4]	Borevič, Z. I.; Shafarevich, I. R., Number Theory (1966), Academic Press: Academic Press New York · Zbl 0145.04902
[5]	Brillhart, J.; Selfridge, J. L., Some factorization of \(2^n\) ± 1 and related results, Math. Comp., 21, 751 (1967), correction · Zbl 0146.04903
[6]	Brillhart, J.; Lehmer, D. H.; Selfridge, J. L., New primality criteria and factorization of \(2^m\) ± 1, Math. Comp., 29, 620-647 (1975) · Zbl 0311.10009
[7]	Brillhard, J.; Lehmer, D. H.; Selfridge, L. J.; Tuckerman, B.; Wagstaff, S. S., Factorization of \(b^n\) ± \(1, b = 2,3,5,6,7,10,11,12\) up to high powers, (Contemp. Math., Vol. 22 (1980), Amer. Math. Soc: Amer. Math. Soc Providence, R.I) · Zbl 0527.10001
[8]	Cassels, J. W.S, Diophantine equations with special reference to elliptic curves, J. London Math. Soc., 42, 183 (1967), correction · Zbl 0138.27002
[9]	Chudnovsky, D. V.; Chudnovsky, G. V., Padé approximations and diophantine geometry, (Proc. Natl. Acad. Sci. U.S.A., 82 (1985)), 2212-2216 · Zbl 0577.14034
[10]	Chudnovsky, D. V.; Chudnovsky, G. V., Applications of Padé approximations to the Grothendieck conjecture on linear differential equations, (Number Theory, New York 1984. Number Theory, New York 1984, Lecture Notes in Math., Vol. 1135 (1985), Springer-Verlag: Springer-Verlag New York), 52-100 · Zbl 0565.14010
[11]	Chudnovsky, D. V.; Chudnovsky, G. V., The Grothendieck conjecture and Padé approximations, (Proc. Japan Acad. Ser. A. Math. Sci., 61 (1985)), 87-91 · Zbl 0574.12022
[12]	Chudnovsky, G. V., Contributions to the Theory of Transcendental Numbers, (Math. Surveys Monogr., Vol. 19 (1984), Amer. Math. Soc: Amer. Math. Soc Providence, R.I), Chap. 7 · Zbl 0418.10031
[13]	Chudnovsky, D. V., Meromorphic solutions of nonlinear partial differential equations and many particle completely integrable systems, J. Math. Phys., 20, 2416-2422 (1979) · Zbl 0455.35096
[14]	Clebsch, A., (Lecons sur la Géométrie, Vol. 2 (1880), Gauthier-Villars: Gauthier-Villars Paris)
[15]	D. A. Cox; D. A. Cox
[16]	Clemens, C. H., (A Scrapbook of Complex Curve Theory (1980), Plenum: Plenum New York) · Zbl 0456.14016
[17]	David, J. A.; Holdridge, D. B., Most wanted factorizations using the quadratic sieve, Sandia report SAND 84-1658 (1984)
[18]	Delone, B. N.; Faddeev, D. K., The Theory of Irrationalities of the Third Degree, Amer. Math. Soc. Translation, Vol. 10 (1964), Providence, R.I. · Zbl 0133.30202
[19]	Desboves, M., Résolution en nombres entiers et sous sa forme la plus générale, de l’equation cubique, homogène, a trois incounues, Nouvelles Ann. de Math., 45, 545-579 (1886) · JFM 18.0148.03
[20]	Dickson, L. E., (History of the Theory of Numbers, Vols. 1-3 (1952), Chelsea: Chelsea New York)
[21]	Dixon, J. D., Asymptotically fast factorization of integers, Math. Comp., 36, 255-260 (1981) · Zbl 0452.10010
[22]	Durst, L. K., The apparition problem for equianharmonic divisibility sequences, (Proc. Natl. Acad. Sci. U.S.A., 38 (1952)), 330-333 · Zbl 0046.28905
[23]	Eisenstein, G., Mathematische Werke (1957), Chelsea: Chelsea New York, 2 vols.
[24]	Gauss, C. F., Disquisitiones Arithmeticae (1966), Yale Univ. Press: Yale Univ. Press New Haven, Conn, (translated by A. A. Clarke) · Zbl 0136.32301
[25]	Gross, B. H., Arithmetic on elliptic curves with complex multiplication, (Lecture Notes in Math., Vol. 776 (1980), Springer-Verlag: Springer-Verlag New York) · Zbl 0584.14027
[26]	Guy, R. K., How to factor a number, (Proc. Fifth Manitoba Conf. Numer. Math., Utilitas. Proc. Fifth Manitoba Conf. Numer. Math., Utilitas, Winnipeg (1975)), 49-89 · Zbl 0338.10001
[27]	Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1960), Oxford Univ. Press: Oxford Univ. Press London, (Clarendon) · Zbl 0086.25803
[28]	Hazewinkel, M., Formal Groups and Applications (1973), Academic Press: Academic Press New York
[29]	Heegner, K., Diophantische analysis and modulfunktionen, Math. Z., 56, 227-253 (1952) · Zbl 0049.16202
[30]	Honda, T., Isogeny classes of Abelian varieties over finite fields, J. Math. Soc. Japan, 20, 83-95 (1968) · Zbl 0203.53302
[31]	Honda, T., On the theory of commutative formal groups, J. Math. Soc. Japan, 22, 213-246 (1970) · Zbl 0202.03101
[32]	Igusa, J.-I, Theta Functions (1972), Springer-Verlag: Springer-Verlag New York · Zbl 0157.20902
[33]	Inkeri, K., Tests for primality, Ann. Acad. Sci. Fenn. Ser. A I Math., 279 (1960) · Zbl 0092.27506
[34]	Jacobi, C. L., Gesammelte Werke, Vol. 1, 497-538 (1881)
[35]	Katz, N. M., An overview of Delign’s proof of the Riemann hypothesis for varieties over finite field, (Mathematical developments arising from Hilbert problem, Proc. Sympos. Pure Math., Vol. 28 (1976), Amer. Math. Soc: Amer. Math. Soc Providence, R.I), 275-305 · Zbl 0339.14013
[36]	Knuth, D. E., (The Art of Computer Programming, Vol. 2 (1981), Addison-Wesley: Addison-Wesley Reading, Mass) · Zbl 0477.65002
[37]	Lehmer, D. H., Computer technology applied to the theory of numbers, (MAA Studies in Math., Vol. 6 (1969), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J), 117-151 · Zbl 0168.29304
[38]	Lehmer, D. H., An extended theory of Lucas’ functions, Ann. of Math., 31, 419-448 (1930) · JFM 56.0874.04
[39]	Lenstra, H. W., Primality testing algorithms, (Séminaire Bourbaki, 33 année (1980/1981)), No. 576 · Zbl 0507.10003
[40]	Lenstra, H. W., Miller’s primality test, Inform. Process. Lett., 8, 86-88 (1979) · Zbl 0399.10006
[41]	Lichtenbaum, S., On \(p\)-adic \(L\)-functions associated to elliptic curves, Invent. Math., 56, 19-55 (1980) · Zbl 0425.12017
[42]	Lucas, E., (Théorie des Nombres, Tome 1 (1961), Blanchard: Blanchard Paris) · Zbl 0098.03601
[43]	Lucas, E., Considerations nouvelles sur la théorie des nombres premiers et sur la division géometrique de la circonference en parties egales, Assoc. France Adv. Sci. C.R., 6, 162 (1877)
[44]	Mazur, B., Modular curves and the Eisenstein ideal, Inst. Hautes Etudes Sci. Publ. Math., 47, 33-186 (1978) · Zbl 0394.14008
[45]	Miller, G. L., Riemann’s hypothesis and tests for primality, J. Comput System Sci., 13, 300-317 (1976) · Zbl 0349.68025
[46]	V. Miller; V. Miller · Zbl 0589.94005
[47]	Montgomery, P., Modular multiplication without trial division, Math. Comp., 44, 519-521 (1985) · Zbl 0559.10006
[48]	Morrison, M. A.; Brillhart, J., A method of factoring and the factorization of \(F_7\), Math. Comp., 29, 183-205 (1975) · Zbl 0302.10010
[49]	Mumford, D., On the equations defining Abelian varieties, I-III, Invent. Math., 3, 215-244 (1967) · Zbl 0173.22903
[50]	Pocklington, H. C., The determination of the prime or composite nature of large numbers by Fermat’s theorem, (Proc. Cambridge Philos. Soc., 18 (1914-1916)), 29-30
[51]	Pollard, J. M., A Monte Carlo method for factorization, BIT, 15, 331-334 (1975) · Zbl 0312.10006
[52]	Pollard, J. M., Theorems on factorization and primality testing, (Proc. Cambridge Philos. Soc., 76 (1974)), 521-528 · Zbl 0294.10005
[53]	Pomerance, C., Recent development in primality testing, Math. Intelligencer, 3, 97-105 (1980-1981) · Zbl 0476.10004
[54]	C. Pomerancein; C. Pomerancein
[55]	Proth, E., Théoremes sur les nombres premiers, C. R. Acad. Sci. Paris Ser. I Math., 87, 926 (1879) · JFM 10.0119.02
[56]	Rabin, M. O., Probabilistic algorithm for primality testing, J. Number Theory, 12, 128-138 (1980) · Zbl 0426.10006
[57]	Riesel, H., Lucasian criteria for the primality of \(N = h\) · \(2^n\) − 1, Math. Comp., 23, 869-875 (1969) · Zbl 0186.07803
[58]	Sarnak, P., Statistical properties of eigenvalues of the Hecke operators (1985), preprint, to appear
[59]	Schoof, R., Elliptic curves over finite fields and the computation of square roots mod \(p\), Math. Comp., 44, 483-494 (1985) · Zbl 0579.14025
[60]	Serre, J. P., Groupes Algébriques et Corps de Classes (1959), Hermann: Hermann Paris · Zbl 0097.35604
[61]	Slowinski, D., Searching for the 27th Mersenne prime, J. Recreational Math., 11, 258-261 (1978-1979) · Zbl 0411.10002
[62]	Tannery, J.; Molk, J., Éléments de la Théorie des Fonctions Elliptiques (1956), 2 vols. · JFM 25.0758.01
[63]	Tate, J., Endomorphisms of Abelian varieties over finite fields, Invent. Math., 2, 134-144 (1966) · Zbl 0147.20303
[64]	Tate, J., Classes d’isogénie des variétés Abéliennes sur un corps fini, (Séminaire Bourbaki No. 352 (1968)) · Zbl 0212.25703
[65]	Tate, J., Algorithm for determining the type of a singular fiber in an elliptic pencil, (Modular Functions of One Variable IV. Modular Functions of One Variable IV, Lecture Notes Math., Vol. 476 (1975), Springer-Verlag: Springer-Verlag New York), 33-52 · Zbl 1214.14020
[66]	Tuckerman, B., The 24th Mersenne prime, (Proc. Natl. Acad. Sci. U.S.A., 68 (1971)), 2319-2320 · Zbl 0224.10006
[67]	Ward, M., Memoir on elliptic divisibility sequences, Amer. J. Math., 70, 31-74 (1948) · Zbl 0035.03702
[68]	Ward, M., Arithmetical properties of the elliptic polynomials arising from the real multiplication of the Jacobi functions, Amer. J. Math., 72, 284-302 (1950) · Zbl 0036.03901
[69]	Ward, M., Arithmetical properties of polynomials associated with the lemniscate elliptic functions, (Proc. Natl. Acad. Sci. U.S.A., 36 (1950)), 359-362 · Zbl 0041.36804
[70]	Weil, A., Elliptic Functions According to Eisenstein and Kronecker (1976), Springer-Verlag: Springer-Verlag New York · Zbl 0318.33004
[71]	Weil, A., Variétiés Abéliennes et Courbes Algébriques (1948), Hermann: Hermann Paris · Zbl 0037.16202
[72]	Weil, A., Number of solutions of equations in finite fields, Bull. Amer. Math. Soc., 55, 497-508 (1949) · Zbl 0032.39402
[73]	Watson, G. N., Singular moduli (3), (Proc. London Math. Soc., 40 (1936)), 83-142 · Zbl 0012.19702
[74]	Weber, H., Lehrbuch der Algebra, Vol. 3 (1908), Braunschweig
[75]	Williams, H. C., A \(p + 1\) method of factoring, Math. Comp., 39, 225-234 (1982) · Zbl 0492.10004
[76]	Williams, H. C., The primality of \(N = 2 A3^n\) − 1, Canad. Bull., 15, 585-589 (1972) · Zbl 0251.10009
[77]	Williams, H. C., A class of primality tests for trinomials which includes the Lucas-Lehmer test, Pacific J. Math., 98, 477-497 (1962) · Zbl 0482.10007
[78]	Williams, H. C.; Judd, J. S., Some algorithms for prime testing using generalized Lehmer functions, Math. Comp., 30, 867-886 (1976) · Zbl 0342.10007
[79]	Williams, H. C.; Holte, R., Some observations on primality testing, Math. Comp., 32, 905-917 (1978) · Zbl 0382.10005
[80]	Yamauchi, M., Some identities on the character sum containing \(x(x\) − 1)\((x\) − \(λ)\), Nagoya Math. J., 42, 109-113 (1971) · Zbl 0219.14015