From: "Dann Corbit" <dcorbit@solutionsiq.com>
Subject: Re: factoring 15 digit numbers
Date: Mon, 14 Feb 2000 20:23:34 -0800
Newsgroups: sci.math.num-analysis
Summary: [missing]

"Steve Leibel" <stevel@coastside.net> wrote in message
news:stevel-1402001917190001@192.168.100.2...
> In article <SYCGiBSng1gy@cc.usu.edu>, et@cc.usu.edu wrote:
>
> > hi, I am trying to write a program to factor numbers up to 15 digits as
> quickly
> > as possible. This is for a programing contest at my university.
> >
> > the three numbers are
> >
> > 327448517363898 = 2*3*7*17*29*37*83*113*199*229
> > 604940384068799 = 997*676009*897563
> > 174883994034750 = 2*3*3*3*3*3*5*5*5*7*7*11*11*13*13*13*13*17
> >
> > and a fourth number probably no larger then 10 digits.
> >
> > since these numbers are so small I think the quadratic sieve algorithim might
> > be overkill. Besides, I don't know if I can undestand the math behind it :)
> > We have been told we can use any source for this, so what I am looking
> for is a
> > good explination of the math involved for an algorithim that would be the most
> > efficient for numbers of this type.
> >
>
> Eric,
>
> You'd have to define "efficient" in order to get a good answer.  In
> general for 15 digit numbers, the basic trial division algorithm works
> just fine.  It only takes a long time if the number is prime or its
> smallest prime factor is large.  For the numbers you give, trial division
> will factor them very quickly.  Any number divisible by 2, 3, 5, or even
> 997 will factor quickly.
>
> Also, in terms of a contest, you would need to tell us the theoretical
> limits of the machine.  For example if you had lots and lots of memory,
> you could just preload all the factorizations and your algorithm would
> then be a simple lookup.  That is an extreme example, but it points out
> the need to state the hardware limitations in order to define the most
> "efficient" algorithm.
>
> A 10 digit number on any type of Pentium using the basic trial division
> algorithm will factor very quickly.

I would suggest a staged method, like that used by MIRACL.
Start with trial division, using only prime numbers that have been
precomputed.
Then use Brent's method, and move onward with more and more sophisticated
algorithms until you find a tough enough nutcracker.

There are 1,951,957 prime numbers between 2 and 31622776
[floor(sqrt(999999999999999))] which is a lot of operations on a 64 bit
integer.  Still, I should be pretty surprised if any number takes more than
a second to process even with brute force.  However, if it is some sort of
speed competition, I should think that a heuristic choice of Brent's method
might win at some point.

Here is a brute force program:
#include<math.h>
#include<float.h>
#include<limits.h>
#include<stdlib.h>
#include<stdio.h>
typedef unsigned long ul;typedef double m;typedef void v;
#define T(f,y)(*(f+(y)/16)&(1<<(((y)%16L)/2)))
#define S(f,y)(*(f+(y)/16)|=1<<(((y)%16L)/2))
#define N 65535
#define r return
#define w while
#define z for
#define e else
#define i if
#define p printf
#define h puts
#define t sqrt
#define x exit
unsigned char d[4096]={0};char s[1024];v foo(v){ul a=1,y;w((a+=2)<N)i(!T
(d,a))z(y=3*a;y<N;y+=a<<1)S(d,y);}ul pt(ul j){i(j==1)r 0;i((j%2)==0){i(j
==2)r 1;e r 0;}e r(!T(d,j)&&j!=1);}v lf(ul n){ul j,ub;i(n==0)h("NULL");e
i(n<4)p("%lu\n",n);e{ub=(ul)(t((m)n)+1.);w(n%2==0){h("2");n>>=1;}ub=(ul
)(t((m)n)+1.);ub=ub>N?N:ub;z(j=3;j<=ub;j+=2)i(pt((ul)j))w(n%j==0){p("%l\
u\n",j);n/=j;ub=(ul)(t((m)n)+1.);}i(n>1)p("%lu\n",n);p("\n");}}v df(m n)
{m j,ub,q;if(n<0)h("-1");n=n>0.?n:-n;i(log10(n)>DBL_DIG){h("Too large");
x(EXIT_FAILURE);}i(n==0.)h("NULL");e i(n<4)p("%.0f\n",n);e{ub=t(n)+1;w(
modf(n/2,&q)==0.){h("2");n=q;}ub=t(n)+1;z(j=3;j<=ub;j+=2)i((j<=N&&pt((ul
)j))||j>N)w(modf(n/j,&q)==0){p("%.0f\n",j);n=q;i(n<ULONG_MAX){lf((ul)n);
r;}ub=t(n)+1;}i(n>1)p("%.0f\n",n);p("\n");}}int main(int c,char*o[]){foo
();i(c>1){df(atof(o[1]));}e w(fgets(s,sizeof s,stdin)!=0){df(atof(s));}r
0;}

And the output:
327448517363898
2
3
7
17
29
37
83
113
199
229

604940384068799
997
676009
897563

174883994034750
2
3
3
3
3
3
5
5
5
7
7
11
11
13
13
13
13
17

It factors each of the test numbers in well under one second.  However, this
program would be badly beaten by a program that stores primes larger than
65521.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
 "The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup   http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm