sci.math, comp.sys.acorn.programmer
factoring 5-byte integers,nos. order 999,999,999,999,999
date:  18.07.99  13:33  pm.  nzst

rem  >  programspd.maths.RepUni15

My factorisation of 999,999,999,999,999 below
 agrees with David Wells,
PENGUIN Dictionary of Curious & Interesting Numbers
Revised edition  1997.  [see Table 7. Repunits.]

At the same time I spotted an error in the 1987 reprint
 edition of David's book under entry  2 438 195 760.

the [wrong]  number 4 867 391 520 has already been
corrected in the 1997 revised edn.

My program "Acorn UK BBC BASIC64. factsplit5"
 factors nos. up to 2^31 in MAXIMUM 22 seconds
and nos. up to 2^37 by trial division possibly in minutes.

###   The method is , if the test no. is too big for integer,
to split it into 2x integer factors, and then
reduce each factor ( < 2^31)  to (smaller) primes.
  E.g. refrain from
testing immediately by 2, 3, 5, etc. because the quotients may be
outside integer range.  So I initially start with a higher
test factor.

I have other factoring progs   :

primecabi  c*a^b+i.
pwrMOD  ??    etc.

//  don.

>RUN
YES.
BEST NEEDS basic64

 progm--    fin.soc.acorncpusr.donWn994/2.pi.factsplit5. byte/zeta4
don mcdonald,  16.07.99,  20:15 pm.  18.07.99  12:30 PM.


factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?1E15-1
1E15-1 = 999999999999999

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   932511 *  1072373409
   centiseconds = 66

fast fact.     932511  max 22 sec.
3 * 310837
31 * 10027
37 * 271
       271 prime.      centisec = 3

fast fact. 1072373409  max 22 sec.
3 * 357457803
3 * 119152601
41 * 2906161
   2906161 prime.      centisec = 79

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?1E18/999999
1E18/999999 = 1000001000001

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   52579 *  19019019
   centiseconds = 2760

fast fact.      52579  max 22 sec.
     52579 prime.      centisec = 12

fast fact.   19019019  max 22 sec.
3 * 6339673
19 * 333667
    333667 prime.      centisec = 29

factor 5 byte integer, max 2^40  gets most factors .TEST bugs


Date: Mon, 19 Jul 1999 11:24:29 -0700
From: Dann Corbit <DCorbit@SolutionsIQ.com>
To: 'Don McDonald' <dsmc@actrix.gen.nz>
Subject: RE: factoring 5-byte integers,nos. order 999,999,999,999,999Re: F inding , large prime numbers...


Thanks a lot, but I can already factor large numbers fairly quickly.  Each
of these completed in less than one second.
E:\crafty\Release>factor 999999999999999
first trying brute force division by small primes
prime factor     3
prime factor     3
prime factor     3
prime factor     31
prime factor     37
prime factor     41
prime factor     271
prime factor     2906161

E:\crafty\Release>factor 999999999999999999999999999999999999999999999
first trying brute force division by small primes
prime factor     3
prime factor     3
prime factor     3
prime factor     3
prime factor     31
prime factor     37
prime factor     41
prime factor     271
now trying 1000 iterations of brent's method
prime factor     238681
prime factor     333667
prime factor     2906161
prime factor     4185502830133110721

E:\crafty\Release>factor
9999999999999999999999999999999999999999999999999999999999999999999999999999
99999999999999
first trying brute force division by small primes
prime factor     3
prime factor     3
prime factor     3
prime factor     3
prime factor     7
prime factor     11
prime factor     13
prime factor     19
prime factor     31
prime factor     37
prime factor     41
prime factor     211
prime factor     241
prime factor     271
prime factor     2161
prime factor     9091
now trying 1000 iterations of brent's method
prime factor     29611
prime factor     238681
prime factor     52579
prime factor     333667
prime factor     3762091
prime factor     2906161
now trying william's (p+1) method 3 times
phase 1 - trying all primes less than 5000
phase 2 - trying last prime less than 500000
phase 1 - trying all primes less than 5000
phase 2 - trying last prime less than 500000
phase 1 - trying all primes less than 5000
phase 2 - trying last prime less than 500000
now trying pollard's (p-1) method
phase 1 - trying all primes less than 10000
phase 2 - trying last prime less than 1000000
finally - the quadratic sieve
using multiplier k= 1 and 360 small primes as factor base
working...  346
trying...
working...* 346
trying...
working...* 346
trying...
working...  346
trying...
working...  346
trying...
prime factor     8985695684401
prime factor     4185502830133110721

-----Original Message-----
From: don mcdonald [mailto:dsmcdona@actrix.gen.nz]
Sent: Saturday, July 17, 1999 7:12 PM
To: ds mc donald
Subject: factoring 5-byte integers,nos. order 999,999,999,999,999Re:
Finding , large prime numbers...


On Sat, 17 Jul 1999, Komkommertje wrote:

> Date: Sat, 17 Jul 1999 11:53:21 GMT
> From: Komkommertje <not@home.org>
> Newsgroups: sci.math
> Subject: Re: Finding large prime numbers...
> 
> apessos@my-deja.com wrote:
> 
> >   How does one determine a number with 10, 20, or more digits is
> >prime?  What equations or algorithms should one use to be able to
> >factor a large number?
> 
> Just visit the site below and all your questions will be answered...
> 
> http://www.utm.edu/research/primes/
> 
sci.math, comp.sys.acorn.programmer
date:  18.07.99  13:33  pm.  nzst

rem  >  programspd.maths.RepUni15

My factorisation of 999,999,999,999,999 below
 agrees with David Wells,
PENGUIN Dictionary of Curious & Interesting Numbers
Revised edition  1997.  [see Table 7. Repunits.]

At the same time I spotted an error in the 1987 reprint
 edition of David's book under entry  2 438 195 760.

the [wrong]  number 4 867 391 520 has already been
corrected in the 1997 revised edn.

My program "Acorn UK BBC BASIC64. factsplit5"
 factors nos. up to 2^31 in MAXIMUM 22 seconds
and nos. up to 2^37 by trial division possibly in minutes.

###   The method is , if the test no. is too big for integer,
to split it into 2x integer factors, and then
reduce each factor ( < 2^31)  to (smaller) primes.
  E.g. refrain from
testing immediately by 2, 3, 5, etc. because the quotients may be
outside integer range.  So I initially start with a higher
test factor.

I have other factoring progs   :

primecabi  c*a^b+i.
pwrMOD  ??    etc.

//  don.

>RUN
YES.
BEST NEEDS basic64

 progm--    fin.soc.acorncpusr.donWn994/2.pi.factsplit5. byte/zeta4
don mcdonald,  16.07.99,  20:15 pm.  18.07.99  12:30 PM.


factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?1E15-1
1E15-1 = 999999999999999

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   932511 *  1072373409
   centiseconds = 66

fast fact.     932511  max 22 sec.
3 * 310837
31 * 10027
37 * 271
       271 prime.      centisec = 3

fast fact. 1072373409  max 22 sec.
3 * 357457803
3 * 119152601
41 * 2906161
   2906161 prime.      centisec = 79

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?1E18/999999
1E18/999999 = 1000001000001

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   52579 *  19019019
   centiseconds = 2760

fast fact.      52579  max 22 sec.
     52579 prime.      centisec = 12

fast fact.   19019019  max 22 sec.
3 * 6339673
19 * 333667
    333667 prime.      centisec = 29

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?2^37-1
2^37-1 = 137438953471

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   223 *  616318177
   centiseconds = 7

fast fact.        223  max 22 sec.
       223 prime.      centisec = 1

fast fact.  616318177  max 22 sec.
 616318177 prime.      centisec = 1131

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?2^31-1
2^31-1 = 2147483647


fast fact. 2147483647  max 22 sec.
2147483647 prime.      centisec = 2113  #  Euler

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?2^33-9
2^33-9 = 8589934583              (I believe Prime?.)

  x  > 2 ^31.  slow mins.         ##  NO. BELOW NO FACTORS.##
factors ? SQRT  x1 =  j*x1 =   92683 *  92680.7999633158179
   centiseconds = 4947

fast fact.      92683  max 22 sec.
     92683 prime.      centisec = 14

fast fact. 92680.7999633158179  max 22 sec.
2 * 46340.3999816579089
2 * 23170
2 * 11585
5 * 2317
7 * 331
       331 prime.      centisec = 3

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?18^4*(17^4+19^4)+ (17*19)^4
18^4*(17^4+19^4)+ (17*19)^4 = 33332818033     (prime.)##

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   182573 *  182572.549243316375 ##  NO.##
centiseconds = 9750

fast fact.     182573  max 22 sec.
41 * 4453
61 * 73
        73 prime.      centisec = 4

fast fact. 182572.549243316375  max 22 sec.
2 * 91286.2746216581872
2 * 45643
13 * 3511
      3511 prime.      centisec = 5

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?6763*10627*29947
6763*10627*29947 = 2152302898747     ## important test Maple? IsPrime.

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   6763 *  318246769
   centiseconds = 257

fast fact.       6763  max 22 sec.
      6763 prime.      centisec = 4

fast fact.  318246769  max 22 sec.
10627 * 29947
     29947 prime.      centisec = 485

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?1E10-1
1E10-1 = 9999999999

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   9 *  1111111111
   centiseconds = 1

fast fact.          9  max 22 sec.
3 * 3
3 * 1
         1 prime.      centisec = 1

fast fact. 1111111111  max 22 sec.
11 * 101010101
41 * 2463661
271 * 9091
      9091 prime.      centisec = 15

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?1E11-1
1E11-1 = 99999999999

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   21649 *  4619151
   centiseconds = 1154

fast fact.      21649  max 22 sec.
     21649 prime.      centisec = 8

fast fact.    4619151  max 22 sec.
3 * 1539717
3 * 513239
    513239 prime.      centisec = 35

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?1E12-1
1E12-1 = 999999999999

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   999 *  1001001001
   centiseconds = 5

fast fact.        999  max 22 sec.
3 * 333
3 * 111
3 * 37
        37 prime.      centisec = 2

fast fact. 1001001001  max 22 sec.
7 * 143000143
11 * 13000013
13 * 1000001
101 * 9901
      9901 prime.      centisec = 7

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?1E14-1
1E14-1 = 99999999999999

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   153417 *  651818247
   centiseconds = 3224

fast fact.     153417  max 22 sec.
3 * 51139
11 * 4649
      4649 prime.      centisec = 4

fast fact.  651818247  max 22 sec.
3 * 217272749
239 * 909091
    909091 prime.      centisec = 45

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?2^32+1
2^32+1 = 4294967297

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   641 *  6700417   ## Euler.
   centiseconds = 36

fast fact.        641  max 22 sec.
       641 prime.      centisec = 2

fast fact.    6700417  max 22 sec.
   6700417 prime.      centisec = 119

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?13^10+1
13^10+1 = 137858491850               #  don.

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   421 *  327454850
   centiseconds = 18

fast fact.        421  max 22 sec.
       421 prime.      centisec = 2

fast fact.  327454850  max 22 sec.
2 * 163727425
5 * 32745485
5 * 6549097
17 * 385241
601 * 641
       641 prime.      centisec = 30

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?1E13-1
1E13-1 = 9999999999999

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   12561 *  796114959
   centiseconds = 176

fast fact.      12561  max 22 sec.
3 * 4187
53 * 79
        79 prime.      centisec = 3

fast fact.  796114959  max 22 sec.
3 * 265371653
 265371653 prime.      centisec = 742

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?1E16-1
1E16-1 = 10000000000000000

  x  > 2 ^31.  slow mins.
10000000000000000  too big. results may be inaccurate. stop  <ESC> 

Escape CLOSE SPOOL. at  erl ...          77

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?100895598169
100895598169 = 100895598169  ##  YES.  DAVID WELLS. ##  MERSENNE.

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   112303 *  898423
   centiseconds = 5998

fast fact.     112303  max 22 sec.
    112303 prime.      centisec = 17        ##  yes

fast fact.     898423  max 22 sec.
    898423 prime.      centisec = 45             ##  yes.

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?10662526601
10662526601 = 10662526601  # david wells etc. PENG DICT..

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   31 *  343952471
   centiseconds = 2

fast fact.         31  max 22 sec.
        31 prime.      centisec = 1

fast fact.  343952471  max 22 sec.
31 * 11095241
31 * 357911
71 * 5041
71 * 71
71 * 1
         1 prime.      centisec = 6

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?15527402881
15527402881 = 15527402881

  x  > 2 ^31.  slow mins.
factors ? SQRT  x1 =  j*x1 =   353 *  43986977
   centiseconds = 20

fast fact.        353  max 22 sec.
       353 prime.      centisec = 1

fast fact.   43986977  max 22 sec.
353 * 124609
353 * 353
353 * 1
         1 prime.      centisec = 18

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?
progm factsplit5   e n d.    CLOSEs * RAM SPOOL
> 

/ don.  (loto)
-- 
