\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Some remarks on primality proving and elliptic curves

Abstract Related Papers Cited by
  • We give an overview of a method for using elliptic curves with complex multiplication to give efficient deterministic polynomial time primality tests for the integers in sequences of a special form. This technique has been used to find the largest proven primes $N$ for which there was no known significant partial factorization of $N-1$ or $N+1$.
    Mathematics Subject Classification: Primary: 11Y11; Secondary: 11G05, 14K22.

    Citation:

    \begin{equation} \\ \end{equation}
  • [1]

    A. Abatzoglou, A CM elliptic curve framework for deterministic primality proving on numbers of special form, Ph.D thesis, University of California at Irvine, 2014.

    [2]

    A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, available online at http://primes.utm.edu/primes/page.php?id=106847

    [3]

    A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, available online at http://primes.utm.edu/primes/page.php?id=117544

    [4]

    A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, Deterministic elliptic curve primality proving for a special sequence of numbers, in Algorithmic Number Theory, Math. Sci. Publ., 2013, 1-20.doi: 10.2140/obs.2013.1.1.

    [5]

    A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, A framework for deterministic primality proving using elliptic curves with complex multiplication, Math. Comp., to appear.

    [6]

    M. Agrawal, N. Kayal and N. Saxena, Primes is in P, Ann. Math., 160 (2004), 781-793.doi: 10.4007/annals.2004.160.781.

    [7]

    A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp., 61 (1993), 29-68.doi: 10.1090/S0025-5718-1993-1199989-X.

    [8]

    W. Bosma, Primality Testing with Elliptic Curves, Doctoraalscriptie Report, University of Amsterdam 85-12, 1985, available online at http://www.math.ru.nl/ bosma/pubs/PRITwEC1985.pdf

    [9]

    D. V. Chudnovsky and G. V. Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, Adv. Appl. Math., 7 (1986), 385-434.doi: 10.1016/0196-8858(86)90023-0.

    [10]

    R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Second edition, Springer, New York, 2005.

    [11]

    R. Denomme and G. Savin, Elliptic curve primality tests for Fermat and related primes, J. Number Theory, 128 (2008), 2398-2412.doi: 10.1016/j.jnt.2007.12.009.

    [12]

    S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, in STOC '86 - Proc. 18th Annual ACM Symp. Theory Computing, 1986, 316-329.doi: 10.1145/12130.12162.

    [13]

    S. Goldwasser and J. Kilian, Primality testing using elliptic curves, J. ACM, 46 (1999), 450-472.doi: 10.1145/320211.320213.

    [14]

    D. M. Gordon, Pseudoprimes on elliptic curves, in Théorie des nombres, de Gruyter, Berlin, 1989, 290-305.

    [15]

    B. H. Gross, Arithmetic on Elliptic Curves with Complex Multiplication, Springer, Berlin, 1980.

    [16]

    B. H. Gross, Minimal models for elliptic curves with complex multiplication, Compositio Math., 45 (1982), 155-164.

    [17]

    B. H. Gross, An elliptic curve test for Mersenne primes, J. Number Theory, 110 (2005), 114-119.doi: 10.1016/j.jnt.2003.11.011.

    [18]

    A. Gurevich and B. Kunyavskiĭ, Primality testing through algebraic groups, Arch. Math. (Basel), 93 (2009), 555-564.doi: 10.1007/s00013-009-0065-9.

    [19]

    A. Gurevich and B. Kunyavskiĭ, Deterministic primality tests based on tori and elliptic curves, Finite Fields Appl., 18 (2012), 222-236.doi: 10.1016/j.ffa.2011.07.011.

    [20]

    M. Kida, Primality tests using algebraic groups, Exper. Math., 13 (2004), 421-427.doi: 10.1080/10586458.2004.10504550.

    [21]

    H. W. Lenstra, Jr., Elliptic curves and number-theoretic algorithms, in Proc. Int. Congr. Math., Amer. Math. Soc., Providence, 1987, 99-120.

    [22]

    H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. Math., 126 (1987), 649-673.doi: 10.2307/1971363.

    [23]

    H. W. Lenstra, Jr. and C. Pomerance, Primality testing with Gaussian periods, available online at http://www.math.dartmouth.edu/~carlp/aks041411.pdf, 2011.

    [24]

    C. Pomerance, Primality testing: variations on a theme of Lucas, Congr. Numer., 201 (2010), 301-312.

    [25]

    K. Rubin and A. Silverberg, Point counting on reductions of CM elliptic curves, J. Number Theory, 129 (2009), 2903-2923.doi: 10.1016/j.jnt.2009.01.020.

    [26]

    R. Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp., 44 (1985), 483-494.doi: 10.2307/2007968.

    [27]

    A. Silverberg, Group order formulas for reductions of CM elliptic curves, in Proc. Conf. Arith. Geom. Crypt. Coding Theory, Amer. Math. Soc., Providence, 2010, 107-120.doi: 10.1090/conm/521/10277.

    [28]

    H. Stark, Counting points on CM elliptic curves, Rocky Mountain J. Math., 26 (1996), 1115-1138.doi: 10.1216/rmjm/1181072041.

    [29]

    Y. Tsumura, Primality tests for $2^p + 2^{\frac{p+1}{2}} + 1$ using elliptic curves, Proc. Amer. Math. Soc., 139 (2011), 2697-2703.doi: 10.1090/S0002-9939-2011-10839-6.

    [30]

    A. Wong, Primality Test Using Elliptic Curves with Complex Multiplication by $\mathbbQ(\sqrt{-7})$, Ph.D thesis, University of California at Irvine, 2013.

  • 加载中
SHARE

Article Metrics

HTML views() PDF downloads(66) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return