×

zbMATH — the first resource for mathematics

Sequences of numbers generated by addition in formal groups and new primality and factorization tests. (English) Zbl 0614.10004
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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] \scE. Bach and J. Shallit, Factoring with cyclotomic polynomials, in “IEEE Annu. Found. of Comput. Sci. Symposium,” to appear. · 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 un, vn of Lucas and elliptic functions, Bull. amer. math. soc., 29, 401-406, (1923) · JFM 49.0097.05
[4] Borevič, Z.I; Shafarevich, I.R, Number theory, (1966), Academic Press New York · Zbl 0145.04902
[5] Brillhart, J; Selfridge, J.L; Brillhart, J; Selfridge, J.L, Some factorization of 2^n ± 1 and related results, Math. comp., Math. comp., 21, 751-96, (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 bn ± 1, b = 2,3,5,6,7,10,11,12 up to high powers, () · Zbl 0527.10001
[8] Cassels, J.W.S; Cassels, J.W.S, Diophantine equations with special reference to elliptic curves, J. London math. soc., J. London math. soc., 42, 183-291, (1967), correction · Zbl 0138.27002
[9] Chudnovsky, D.V; Chudnovsky, G.V, Padé approximations and Diophantine geometry, (), 2212-2216 · Zbl 0577.14034
[10] Chudnovsky, D.V; Chudnovsky, G.V, Applications of Padé approximations to the Grothendieck conjecture on linear differential equations, (), 52-100 · Zbl 0565.14010
[11] Chudnovsky, D.V; Chudnovsky, G.V, The Grothendieck conjecture and Padé approximations, (), 87-91 · Zbl 0574.12022
[12] Chudnovsky, G.V, Contributions to the theory of transcendental numbers, (), 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, ()
[15] \scD. A. Cox, Mordell-Weil groups and invariants of elliptic surfaces, Amherst College preprint, in press.
[16] Clemens, C.H, ()
[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)
[20] Dickson, L.E, ()
[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, (), 330-333 · Zbl 0046.28905
[23] Eisenstein, G, Mathematische werke, (1957), Chelsea New York, 2 vols.
[24] Gauss, C.F, Disquisitiones arithmeticae, (1966), 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, () · Zbl 0584.14027
[26] Guy, R.K, How to factor a number, (), 49-89
[27] Hardy, G.H; Wright, E.M, An introduction to the theory of numbers, (1960), Oxford Univ. Press London, (Clarendon) · Zbl 0086.25803
[28] Hazewinkel, M, Formal groups and applications, (1973), 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 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; Jacobi, C.L; Jacobi, C.L, Fundamenta nova theoriae functionum ellipticarum, Gesammelte werke, Gesammelte werke, Vol. 1, 497-538, (1881), Konigsberg
[35] Katz, N.M, An overview of Delign’s proof of the Riemann hypothesis for varieties over finite field, (), 275-305
[36] Knuth, D.E, ()
[37] Lehmer, D.H, Computer technology applied to the theory of numbers, (), 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, (), 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, ()
[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] \scV. Miller, Use of elliptic curves in cryptography, to appear. · 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 F7, Math. comp., 29, 183-205, (1975) · Zbl 0302.10010
[49] Mumford, D; Mumford, D; Mumford, D, On the equations defining abelian varieties, I-III, Invent. math., Invent. math., 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, (), 29-30 · JFM 45.0332.12
[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, (), 521-528 · Zbl 0294.10005
[53] Pomerance, C, Recent development in primality testing, Math. intelligencer, 3, 97-105, (1980-1981) · Zbl 0476.10004
[54] \scC. Pomerance, Analysis and comparison of some integer factoring algorithms, in “Computational Methods in Number Theory (H. W. Lenstra, Jr. and R. Tijdeman, Eds.), Math. Centrum Tracts Vol. 154, Part I, pp. 89-139, Math. Centrum, Amsterdam.
[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 · 2n − 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 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; Tannery, J; Molk, J, Éléments de la théorie des fonctions elliptiques, (1956), Gauthier-Villars Paris, 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, () · Zbl 0212.25703
[65] Tate, J, Algorithm for determining the type of a singular fiber in an elliptic pencil, (), 33-52 · Zbl 1214.14020
[66] Tuckerman, B, The 24th mersenne prime, (), 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, (), 359-362 · Zbl 0041.36804
[70] Weil, A, Elliptic functions according to Eisenstein and Kronecker, (1976), Springer-Verlag New York · Zbl 0318.33004
[71] Weil, A, Variétiés abéliennes et courbes algébriques, (1948), 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), (), 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 = 2A3n − 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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.