Xref: utzoo comp.sys.handhelds:8521 sci.math.symbolic:2545
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!ucla-cs!ucla-ma!euphemia!pmontgom
From: pmontgom@euphemia.math.ucla.edu (Peter Montgomery)
Newsgroups: comp.sys.handhelds,sci.math.symbolic
Subject: Re: HP48/Kalb/Bos dusts 80486/Mathematica
Message-ID: <1991Jun17.043819.19652@math.ucla.edu>
Date: 17 Jun 91 04:38:19 GMT
References: <43391@cup.portal.com>
Sender: news@math.ucla.edu
Followup-To: sci.math.symbolic
Organization: UCLA Mathematics Dept.
Lines: 73

In article <43391@cup.portal.com> jpser@cup.portal.com (John Paul Serafin) writes:
>I have stumbled across several integers which are factored by the ultimate 
>prime factor routines for the HP48 by Klaus Kalb and Jurjen Bos much
>faster than Mathematica 1.2 running on a 25MHz 486.   

	The second entry on the list has a typo, according to the
factorization given

>128,573,131,101,428,317
               ^ 
               2

	On a SUN 4/260, Maple V completes all four in 25 seconds:

    |\^/|      MAPLE V
._|\|   |/|_.  Copyright (c) 1981-1990 by the University of Waterloo.
 \  MAPLE  /   All rights reserved.  MAPLE is a registered trademark of
 <____ ____>   Waterloo Maple Software.
      |        Type ? for help.
> 
# HP 508 seconds (2^62 - 1)
> ifactor(4611686018427387903);
                          (3) (2147483647) (715827883)

# HP 241 seconds (1428317 changed to 2428317)
> ifactor(128573131102428317);
bytes used=1000072, alloc=655240, time=6.483
bytes used=2000192, alloc=851812, time=11.616
bytes used=3000336, alloc=917336, time=17.366
                            (573259391) (224284387)

# 573259391  * 224284387 ;
# HP 151 seconds
> ifactor(50303624411148161);
                            (224285003) (224284387)

# 224284387 * 224,285,003
# HP 45 seconds
> ifactor(5260991541853343);
                             (23456789) (224284387)

# 224284387  * 23456789 
> ;quit 
bytes used=3824236, alloc=917336, time=25.033

	On the same machine, my own factor program takes 
0.15 second to get 3 * 715827883 * 2147483647 using P-1, 
0.61 second to get 224284387 * 573259391 using Pollard Rho,
0.60 second to get 224284387 * 224285003 using Pollard Rho,
0.61 second to get 224284387 * 23456789 using Pollard Rho,
for a total of two seconds.

	The P-1 method may seem not to work for the first example
since 2^62-1 = 3pq where

		p = 715827883  = 1 + 2 * 3     * 7 * 11 * 31 * 151 * 331
		q = 2147483647 = 1 + 2 * 3 * 3 * 7 * 11 * 31 * 151 * 331

and so p-1 and q-1 have the same largest prime factor.  To overcome this,
after finding the factor 3 by trial division, select a base a
and compute a' = a^(pq-1) mod pq, using a' as the initial base for P-1.
In this case, unless a is a cube mod q, we will achieve
a' == 1 mod p but a' !== 1 mod q, and the first GCD will 
uncover our divisor p (after backtracking).  This technique also works 
when trying to factor a prime power p^k using P-1 
(a topic discussed in sci.math.symbolic recently), 
since the initial base a^(p^k - 1) mod p^k  will be congruent to 1 mod p.
However, it does not necessarily work for p^2 q.
--
        Peter L. Montgomery 
        pmontgom@MATH.UCLA.EDU 
        Department of Mathematics, UCLA, Los Angeles, CA 90024-1555
If I spent as much time on my dissertation as I do reading news, I'd graduate.