From Peter-Lawrence.Montgomery@cwi.nlThu Dec 14 07:20:04 1995
Date: Wed, 13 Dec 1995 09:00:21 EST
From: Peter-Lawrence.Montgomery@cwi.nl
To: Multiple recipients of list NMBRTHRY <NMBRTHRY@vm1.nodak.edu>
Subject: 47-digit ECM factor of most wanted number

        On Monday November 27 at 04:50, I found the 47-digit prime factor

        p47 = 12025702000065183805751513732616276516181800961

of 5^256 + 1 using the elliptic curve method (ECM) at Centrum voor
Wiskunde en Informatica (CWI) in Amsterdam.  The complete factorization is

        5^256 + 1 =   1655809 * 101199664791578113 * 4563566430220614493697
                    * p47 * p88,
where
        p88 = 46955555963938795295705098001562320756581733\
              03955183176829795300834096134412809302652417

is an 88-digit prime.  The first three factors were found by
Sam Wagstaff, Jr. in 1987 and are listed in

 [Cunn] ``Factorizations of b^n +- 1, b = 2, 3, 5, 6, 7, 10, 11, 12
          up to high powers'', by John Brillhart, D.H. Lehmer,
          J.L. Selfridge, Bryant Tuckerman, and S.S. Wagstaff, Jr.,
          Volume 22, Contemporary Mathematics,
          American Mathematical Society, 1988.

        I believe this p47 is the largest factor found by ECM
since the method was discovered in 1985.  Andreas Mueller,
University of Saarland (Germany), found the 44-digit factor:
27885873044042449777540626664487051863162949 of the
partition number p(19069) on June 21, 1995.  Franz-Dieter Berger,
also at University of Saarland, found the 43-digit factor
5688864305048653702791752405107044435136231 of p(19997) in 1993.
H. Kuwakado found the 43-digit factor
4578376497845545742407987348754758713076681
of 2^655 + 2^328 + 1 (which divides 2^1310 + 1) on September 25, 1995.

        Page lxxxvi of [Cunn] lists 10 ``Most Wanted'' composites and
24 ``More Wanted'' composites.  Those numbers were believed very hard
to factor with contemporary (i.e., 1988) technology.  All but two
of those 34 wanted numbers had been factored when Update 2.9 to [Cunn]
went to press in August, 1995.  Now the last two wanted numbers in the
1988 list, 2^1024 + 1 and 5^256 + 1, have been factored.  Richard Brent
found the 40-digit factor 4659775785220018543264560743076778192897
of 2^1024 + 1 by ECM on October 20, 1995.

        The successful elliptic curve used for the p47 had the form

                y^2 = x^3 + A x^2 + x
with
         A == 11178277277974656608242775790909309609374460526 (mod p47) .

This curve was chosen because its order was known to be divisible by 12.
The actual group order is

             p47 + 1 + 53794475423747666304958
           = 12025702000065183805751567527091700263848105920
           =   2^6 * 3 * 5 * 7 * 23 * 997 * 43237 * 554573 * 659723
             * 2220479 * 2459497 * 903335969

The step 1 limit was 3 million, slightly larger than 2459497.
If P0 is the output of step 1, then step 2 compares the
x-coordinate of (2^12)^i * (7^24)^j * P0
to that of (3^24)^k * (5^24)^l * P0
for various i, j, k, l  (51200 pairs (i,j) and 5120 pairs (k,l)).
It succeeded because (for example)
2^3444 * 7^120  == - 3^168 * 5^240 (mod 903335969).

        The factorizations of p47 +- 1 and p88 +- 1 are:

        p47 - 1 =   2^11 * 3^2 * 5 * 31 * 53 * 9433 * 235951
                  * 97020682513 * 367785350034213623

        p47 + 1 =   2 * 29 * 167 * 798569516740349
                  * 1554723792801246125434881983

        p88 - 1 =   2^9 * 163 * 194911 * 319343 * prp72

        p88 + 1 =   2 * 3^2 * 2410679449 * 72893689951
                  * 1068119314558144585233885015373
                  * 1389841619859126277197527215454819963

        I thank the many individuals at CWI who let my group
use idle SGI workstation cycles to factor large numbers.
Without their cooperation, this factor would not have been found.

                        Peter L. Montgomery