Article 13084 of alt.sources:
Path: nntpd.lkg.dec.com!crl.dec.com!crl.dec.com!caen!usenet.cis.ufl.edu!usenet.eel.ufl.edu!brutus.bright.net!chi-news.cic.net!newsfeed.internetmci.com!info.ucla.edu!nnrp.info.ucla.edu!venice.pic.ucla.edu!not-for-mail
From: a540ami@pic.ucla.edu (Ami Fischman)
Newsgroups: alt.sources,alt.math.undergrad,sci.math
Subject: Factorization (lenstra, pollard)
Date: 23 Dec 1995 20:09:08 GMT
Organization: University of California, Los Angeles
Lines: 684
Message-ID: <4bhnl4$144o@saba.info.ucla.edu>
NNTP-Posting-Host: venice.pic.ucla.edu
Keywords: Lenstra, Pollard, elliptic curve
X-Newsreader: TIN [UNIX 1.3 950824BETA PL0]
Xref: nntpd.lkg.dec.com alt.sources:13084 sci.math:129641

#!/bin/sh
# This is a shell archive (produced by GNU sharutils 4.2).
# To extract the files from this archive, save it to some FILE, remove
# everything before the `!/bin/sh' line above, then type `sh FILE'.
#
# Made on 1995-12-22 16:40 PST by <a540ami@earth>.
# Source directory was `/h/a540/a540ami'.
#
# Existing files will *not* be overwritten unless `-c' is specified.
#
# This shar contains:
# length mode       name
# ------ ---------- ------------------------------------------
#    629 -rwx------ factor/Makefile
#    771 -rwx------ factor/fact.cc
#    638 -rw------- factor/utils.h
#   2600 -rwx------ factor/pollard.cc
#   2600 -rw------- factor/lenstra.cc
#   1919 -rw------- factor/utils.cc
#   2867 -rw------- factor/README
#
save_IFS="${IFS}"
IFS="${IFS}:"
gettext_dir=FAILED
locale_dir=FAILED
first_param="$1"
for dir in $PATH
do
  if test "$gettext_dir" = FAILED && test -f $dir/gettext \
     && ($dir/gettext --version >/dev/null 2>&1)
  then
    set `$dir/gettext --version 2>&1`
    if test "$3" = GNU
    then
      gettext_dir=$dir
    fi
  fi
  if test "$locale_dir" = FAILED && test -f $dir/shar \
     && ($dir/shar --print-text-domain-dir >/dev/null 2>&1)
  then
    locale_dir=`$dir/shar --print-text-domain-dir`
  fi
done
IFS="$save_IFS"
if test "$locale_dir" = FAILED || test "$gettext_dir" = FAILED
then
  echo=echo
else
  TEXTDOMAINDIR=$locale_dir
  export TEXTDOMAINDIR
  TEXTDOMAIN=sharutils
  export TEXTDOMAIN
  echo="$gettext_dir/gettext -s"
fi
touch -am 1231235999 $$.touch >/dev/null 2>&1
if test ! -f 1231235999 && test -f $$.touch; then
  shar_touch=touch
else
  shar_touch=:
  echo
  $echo 'WARNING: not restoring timestamps.  Consider getting and'
  $echo "installing GNU \`touch', distributed in GNU File Utilities..."
  echo
fi
rm -f 1231235999 $$.touch
#
if mkdir _sh27903; then
  $echo 'x -' 'creating lock directory'
else
  $echo 'failed to create lock directory'
  exit 1
fi
# ============= factor/Makefile ==============
if test ! -d 'factor'; then
  $echo 'x -' 'creating directory' 'factor'
  mkdir 'factor'
fi
if test -f 'factor/Makefile' && test "$first_param" != -c; then
  $echo 'x -' SKIPPING 'factor/Makefile' '(file already exists)'
else
  $echo 'x -' extracting 'factor/Makefile' '(text)'
  sed 's/^X//' << 'SHAR_EOF' > 'factor/Makefile' &&
CFLAGS = -O4
LDFLAGS = -s
CC = g++
X
TARGETS = fact pollard lenstra
X
all: $(TARGETS) 
X	echo Done
X
fact: fact.cc 
X	$(CC) $(CFLAGS) -o fact fact.cc $(LDFLAGS)
X
utils.o: utils.cc
X	$(CC) $(CFLAGS) -c utils.cc
X
pollard.o: pollard.cc 
X	$(CC) $(CFLAGS) -c pollard.cc 
X
pollard: pollard.o utils.o
X	$(CC) $(CFLAGS) -o pollard pollard.o utils.o $(LDFLAGS)
X
lenstra.o: lenstra.cc 
X	$(CC) $(CFLAGS) -c lenstra.cc
X
lenstra: lenstra.o utils.o
X	$(CC) $(CFLAGS) -o lenstra lenstra.o utils.o $(LDFLAGS)
X
clean: 
X	rm -f *.o *~ $(TARGETS) core mon.out a.out
X
strip:
X	strip $(TARGETS)
X
tar: clean
X	-(cd /exp; tar cvzf /mnt/arc/factor.tar.gz factor/)
SHAR_EOF
  $shar_touch -am 1222162495 'factor/Makefile' &&
  chmod 0700 'factor/Makefile' ||
  $echo 'restore of' 'factor/Makefile' 'failed'
  if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
  && ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
    md5sum -c << SHAR_EOF >/dev/null 2>&1 \
    || $echo 'factor/Makefile:' 'MD5 check failed'
53e7fcd10ce7f6a2792be011f00d8a79  factor/Makefile
SHAR_EOF
  else
    shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'factor/Makefile'`"
    test 629 -eq "$shar_count" ||
    $echo 'factor/Makefile:' 'original size' '629,' 'current size' "$shar_count!"
  fi
fi
# ============= factor/fact.cc ==============
if test -f 'factor/fact.cc' && test "$first_param" != -c; then
  $echo 'x -' SKIPPING 'factor/fact.cc' '(file already exists)'
else
  $echo 'x -' extracting 'factor/fact.cc' '(text)'
  sed 's/^X//' << 'SHAR_EOF' > 'factor/fact.cc' &&
/*
X * fact.cc -- Factor any integer (up to about 2^65536, I think) into primes
X *
X * Uses simplistic "up to sqrt(n)" approach.  Not practical.
X *
X * Compile: 
X *  g++ -s -O4 -o fact fact.cc
X * Invoke:
X *  ./fact NumberToFactor
X *
X * ChangeLog
X *  950516 -- Created by Ami Fischman <a540ami@pic.ucla.edu>
X */
X
#include <stdio.h>
#include <stdlib.h>
#include <Integer.h>
X
int main(int argc, char *argv[]) {
X    Integer bignum, i;
X    Integer Q, R;
X
X    if (argc!=2) {
X	fprintf(stderr, "Usage: %s NumberToFactor \n", argv[0]);
X	exit(1);
X    }
X    
X    bignum=atoI(argv[1]);
X    cout << bignum << ": ";
X
X    i=2;
X    while (i<=bignum) {
X	divide(bignum,i,Q,R);
X	if (R==0) {
X	    cout << i << " ";
X	    bignum=Q;
X	    --i;
X	};
X	++i;
X    };
X    cout << endl;
X    return 0;
};
X
X
SHAR_EOF
  $shar_touch -am 1124123895 'factor/fact.cc' &&
  chmod 0700 'factor/fact.cc' ||
  $echo 'restore of' 'factor/fact.cc' 'failed'
  if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
  && ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
    md5sum -c << SHAR_EOF >/dev/null 2>&1 \
    || $echo 'factor/fact.cc:' 'MD5 check failed'
24d72f4ba3fe09733cdede73181ae012  factor/fact.cc
SHAR_EOF
  else
    shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'factor/fact.cc'`"
    test 771 -eq "$shar_count" ||
    $echo 'factor/fact.cc:' 'original size' '771,' 'current size' "$shar_count!"
  fi
fi
# ============= factor/utils.h ==============
if test -f 'factor/utils.h' && test "$first_param" != -c; then
  $echo 'x -' SKIPPING 'factor/utils.h' '(file already exists)'
else
  $echo 'x -' extracting 'factor/utils.h' '(text)'
  sed 's/^X//' << 'SHAR_EOF' > 'factor/utils.h' &&
#include <stdio.h>
#include <stdlib.h>
#include <Integer.h>
#include <values.h>
#include <assert.h>
X
Integer LCM(Integer K);
int isprime(Integer n);
unsigned int strlen(int *str);
Integer pow(Integer a, Integer b);
int *binarize(Integer k);
Integer PWRmodN(Integer a, Integer k, Integer n);
Integer gcd(Integer A, Integer B);
Integer InvModN(Integer ma, Integer mn);
int strlen(char *str);
#define ABS(x) (((x)<0)? -(x): (x))
#define RedModN(x, n) divide((x), (n), q, (x)) //Reduce x (mod n)
#define ABSmodN(x, n) (((x)>=0)? (x): (n)+(x))     //Absolute val in Z/nZ
#define BITSET(k, i) ((1&((k)>>(i)))? 1: 0) //Is the i'th bit of k set?
SHAR_EOF
  $shar_touch -am 1209212595 'factor/utils.h' &&
  chmod 0600 'factor/utils.h' ||
  $echo 'restore of' 'factor/utils.h' 'failed'
  if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
  && ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
    md5sum -c << SHAR_EOF >/dev/null 2>&1 \
    || $echo 'factor/utils.h:' 'MD5 check failed'
c919b764a08fa1db5c66436bd3254275  factor/utils.h
SHAR_EOF
  else
    shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'factor/utils.h'`"
    test 638 -eq "$shar_count" ||
    $echo 'factor/utils.h:' 'original size' '638,' 'current size' "$shar_count!"
  fi
fi
# ============= factor/pollard.cc ==============
if test -f 'factor/pollard.cc' && test "$first_param" != -c; then
  $echo 'x -' SKIPPING 'factor/pollard.cc' '(file already exists)'
else
  $echo 'x -' extracting 'factor/pollard.cc' '(text)'
  sed 's/^X//' << 'SHAR_EOF' > 'factor/pollard.cc' &&
/*
X * pollard.cc -- Use Pollard's p-1 Algorithm to factor a large integer
X * 
X * Uses Pollard's algorithm to (sometimes) factor a large integer into
X *  smaller pieces.  Note this algorithm has a rather high failure rate,
X *  and is only used as an intro to Lenstra's Elliptic Curve Algorithm.
X *  The algorithm was taken from "Rational Points on Elliptic Curves", by
X *  Silverman/Tate, pages 130-132.
X *
X * Compile:
X *  g++ -s -O4 -o pollard pollard.cc
X * Invoke:
X *  ./pollard NumberToFactor A K
X *  Where A is the base for the a^k-1 calculation (usually A=2).
X *   and K is a small number, s.t. LCM{1,2,...,K} is product of small
X *   primes to small powers.
X *
X * ChangeLog
X *  950516 -- Created by Ami Fischman <a540ami@pic.ucla.edu>
X */
X
#include <stdio.h>
#include <stdlib.h>
#include <Integer.h>
X
#include "utils.h"
X
Integer pollard_factor(Integer n, Integer a, Integer K) {
X    /* Return a non-trivial factor of N using Pollard's p-1 algorithm */
X    /* Assumes 1<a<n, and k=LCM[1,2,3,4...K], some K */
X    Integer D, k;
X
X    k=LCM(K);
X   
X    if (gcd(a, n) > 1) return gcd(a, n);
X
X    D=gcd(PWRmodN(a,k,n)-1,n);
X    if ((1<D)&&(D<n)) return D;
X    if ((D==1)&&(0!=(K%60))) {
X	//	cout << "Incrementing k from " << K << endl;
X	return pollard_factor(n,a,K+1);
X    }
X    if ((0==(K%60))||((D==n)&&(a+1<n))) {
X	//	cout << "Incrementing a from " << a << endl;
X	return pollard_factor(n,a+1,K);
X    }
X    cout << "K is " << K << " -- a is " << a << " -- n is " << n << " -- D is "<< D << endl;
X    return 0;
}
X
void Pollard(Integer n, Integer a, Integer k) {
X    /* Print out factorization of n using Pollard's p-1 alg successively */
X    Integer t,pf, R, t1;
X
X    t=n;
X    if (isprime(t)) cout << t << " is prime!" << endl;
X    else cout << t << " is not prime: " << endl;
X    cout << n << "=";
X    while ((isprime(t)==0)&&(t>1)) {
X	pf=pollard_factor(t,a,k);
X	if (pf==0) {
X	    cout << t << endl;
X	    cout << "Got a pf of 0, probably an error" << endl;
X	    exit(2);
X	}
X	cout << pf;
X	if (isprime(pf)) cout << "(p)";
X	else cout << "(np)";
X
X	cout.flush();
X	divide(t,pf,t1, R);
X	if (R!=0) {
X	    cerr << "Oh no! A hideos bug in dividing by a factor!" << endl;
X	    exit(3);
X	}
X	t=t1;
X	if ((isprime(t)==0)&&(t>1)) cout << " * ";
X	else cout << " * " << t;
X	if (isprime(pf)) cout << "(p)";
X	else cout << "(np)";
X
X    }
X    cout << endl;
}
X
int main(int argc, char *argv[]) {
X    Integer n, pf, a, k;
X
X    if (argc!=4) {
X	fprintf(stderr, "Usage: %s NumberToFactor A K\n", argv[0]);
X	exit(1);
X    }
X
X    n=atoI(argv[1]);
X    a=atoI(argv[2]);
X    k=atoI(argv[3]);
X    Pollard(n,a,k);
X    return 0;
}
X
X	
X
SHAR_EOF
  $shar_touch -am 1124124695 'factor/pollard.cc' &&
  chmod 0700 'factor/pollard.cc' ||
  $echo 'restore of' 'factor/pollard.cc' 'failed'
  if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
  && ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
    md5sum -c << SHAR_EOF >/dev/null 2>&1 \
    || $echo 'factor/pollard.cc:' 'MD5 check failed'
209bb1d1d3344e10459ece2090ff539b  factor/pollard.cc
SHAR_EOF
  else
    shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'factor/pollard.cc'`"
    test 2600 -eq "$shar_count" ||
    $echo 'factor/pollard.cc:' 'original size' '2600,' 'current size' "$shar_count!"
  fi
fi
# ============= factor/lenstra.cc ==============
if test -f 'factor/lenstra.cc' && test "$first_param" != -c; then
  $echo 'x -' SKIPPING 'factor/lenstra.cc' '(file already exists)'
else
  $echo 'x -' extracting 'factor/lenstra.cc' '(text)'
  sed 's/^X//' << 'SHAR_EOF' > 'factor/lenstra.cc' &&
/*
X * lenstra.cc -- Use Lenstra's Elliptic Curves Algorithm 
X *               to factor a large integer
X * 
X *  The algorithm was taken from "Rational Points on Elliptic Curves", by
X *  Silverman/Tate, pages 133-138.
X *
X * Compile:
X *  g++ -s -O4 -o lenstra lenstra.cc
X * Invoke:
X *  ./lenstra NumbertoFactor InitialK
X * ChangeLog
X *  951124 -- Created by Ami Fischman <a540ami@pic.ucla.edu>
X */
X
#include <stdio.h>
#include <stdlib.h>
#include <Integer.h>
#include <limits.h>
X
#include "utils.h"
X
Integer LenstraFactor(Integer n, Integer K) {
X    Integer t, k, g, q;
X    int i, bp, breaker, firstsum, iter; 
X    Integer x,y, b, c, lambda, tx, ty, qx, qy, nx, ny;
X    Integer tblx, tbly;
X    
X    if (gcd(n,6)!=1) return gcd(6,n);
X    x=2; y=1; b=1; c=y*y-x*x*x-b*x;
X    iter=1;
X    while (1) {
X	iter++;
X	t=gcd(4*b*b*b+27*c*c, n);
X	while (t!=1) {
X	    if (t==n) {
X		++b; c=y*y-x*x*x-b*x;
X		t=gcd(4*b*b*b+27*c*c, n);
X		continue;
X	    };
X	    return t;
X	}
X	k=LCM(K);
X	for(i=0;pow(2,i)<=k;i++);
X	bp=i-1;
X	
X	tblx=x; 
X	tbly=y;
X	qx=1; qy=1; firstsum=1;
X	breaker=0;
X	for (i=1; i<=bp; i++) {
X	    tx=tblx; ty=tbly;
X	    g=gcd(2*ty, n);
X	    assert(g!=0);
X	    if (g==1) lambda=InvModN(2*ty, n)*(3*tx*tx+b);
X	    else if(g<n) return g;
X	    else {++K; iter=0; b=1; breaker=1; break;};
X	    if (iter==75) {K+=5; iter=0; b=1; breaker=1; break;};
X	    tblx=lambda*lambda-2*tx;
X	    tbly=lambda*(tx-tblx)-ty;
X	    RedModN(tblx, n); RedModN(tbly, n);
X	    tblx=ABSmodN(tblx, n); tbly=ABSmodN(tbly, n);
X	    
X	    if (testbit(k, i)) {        //Need to add tbl{x,y} in to q{x,y}
X		if (firstsum) {qx=tblx; qy=tbly;firstsum=0;}
X		else {
X		    g=gcd(ABSmodN(tblx-qx, n), n);
X		    assert(0!=g);
X		    if (g==1)
X		      lambda=InvModN(ABSmodN(tblx-qx,n),n)*ABSmodN(tbly-qy,n);
X		    else if (g==n) {K+=5; b=1; breaker=1; break;}
X		    else if (g<n) return g;
X		    if (iter==75) {K+=5; iter=0; b=1; breaker=1; break;};
X		    nx=ABSmodN(lambda*lambda-qx-tblx, n);
X		    ny=ABSmodN(lambda*(qx-nx)-qy, n);
X		    qx=nx; qy=ny;
X		    RedModN(qx, n); RedModN(qy, n);
X		    qx=ABSmodN(qx, n); qy=ABSmodN(qy, n);
X		}
X	    }
X	}
X	if (breaker) continue;
X	cout << "Failed with b=" << b << ".  Trying next..." << endl;
X	++b;
X    }
}
X
int main(int argc, char *argv[]) {
X    if (argc != 3) {
X	cerr << "Usage: " << argv[0] << " NumberToFactor InitialK\n" << endl;
X	cerr << "For an example, try " << argv[0] << " 1715761513 25" << endl;
X	return -1;
X    }
X    if (isprime(atoI(argv[1]))) {
X	cerr << argv[1] << " is prime..." << endl;
X	return 0;
X    }
X    cout << LenstraFactor(atoI(argv[1]), atoI(argv[2])) << endl;
X    return 0;
}
X
X    
SHAR_EOF
  $shar_touch -am 1210124595 'factor/lenstra.cc' &&
  chmod 0600 'factor/lenstra.cc' ||
  $echo 'restore of' 'factor/lenstra.cc' 'failed'
  if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
  && ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
    md5sum -c << SHAR_EOF >/dev/null 2>&1 \
    || $echo 'factor/lenstra.cc:' 'MD5 check failed'
117e8973bdd8ad2a4a3082b0bb73b488  factor/lenstra.cc
SHAR_EOF
  else
    shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'factor/lenstra.cc'`"
    test 2600 -eq "$shar_count" ||
    $echo 'factor/lenstra.cc:' 'original size' '2600,' 'current size' "$shar_count!"
  fi
fi
# ============= factor/utils.cc ==============
if test -f 'factor/utils.cc' && test "$first_param" != -c; then
  $echo 'x -' SKIPPING 'factor/utils.cc' '(file already exists)'
else
  $echo 'x -' extracting 'factor/utils.cc' '(text)'
  sed 's/^X//' << 'SHAR_EOF' > 'factor/utils.cc' &&
#include "utils.h"
X
int strlen(char *str) {
X    int i;
X    for (i=0;str[i];i++);
X    return i;
}
X
Integer LCM(Integer K) {
X    /* Return the least common multiple of [1,2,3,4,...,K] */
X    Integer i, result, Q, R;
X    result=1;
X    for (i=1;i<=K;++i) {
X	result=lcm(result,i);
X    }
X    return result;
}
X
int isprime(Integer n) {
X    /* Return 1 if n passes Fermat's Little thm for a==2..10 */
X    /* Basically, a^(p-1)=1 (mod p) hints at primality */
X    Integer count;
X    if (n<=10) 
X      if ((n==2)||(n==3)||(n==5)||(n==7)) return 1;
X      else return 0;
X    for (count=2; count<=10; ++count) 
X      if (PWRmodN(count, n-1, n)!=1) return 0;
X    return 1;
}
X
unsigned int strlen(int *str) {
X    unsigned int i;
X    for (i=0; str[i]; ++i);
X    return i;
}
X
Integer pow(Integer a, Integer b) {
X    /* Raise A to the B'th power (integers only) */
X    Integer i;
X    Integer res;
X    res=1;
X    for (i=0;i<b;++i)
X      res*=a;
X    return res;
}
X
Integer PWRmodN(Integer a, Integer k, Integer n) {
X    unsigned int len, i;
X    Integer walk, acc=1, q;
X    
X    len=lg(k)+1;
X    walk=a;
X    if (testbit(k,0)) acc*=walk;
X    for (i=1;i<len;i++) {
X	walk*=walk; RedModN(walk, n);
X	if (testbit(k,i)) {acc*=walk; RedModN(acc, n);};
X    }
X    return acc;
}
X
Integer gcd(Integer A, Integer B) {
X    Integer Q, R, T;
X    divide(A, B, Q, R);
X    R=(R!=0) ? R : ((A>B) ? B : A);
X    while (R>0) {	
X	T=R;
X	divide(B,T,Q,R);
X    }
X    return T;
}
X
/* Finds the inverse a in ax == 1 (mod n) NOTE: (a, n) must be 1!!! */
/* This comes from "A Concrete Introduction to Higher Algebra,"
X   by Lindsay Childs, pp 22-24 */
Integer InvModN(Integer ma, Integer mn) {
X    Integer aa=ma, nn=mn, tx, ty, q, r, x=1, y=0, ox=0, oy=1;
X    char sx=0;
X
X    while (divide(nn, aa, q, r), r!=0) {
X	tx = x * q; ty = y * q;
X	tx+=ox;
X	sx = !sx;
X	ty+=oy;
X	ox = x;	oy = y;
X	x = tx;	y = ty;
X	nn = aa; aa = r;
X    }
X    if (sx) return mn-x;
X    else return x;
}
SHAR_EOF
  $shar_touch -am 1201202695 'factor/utils.cc' &&
  chmod 0600 'factor/utils.cc' ||
  $echo 'restore of' 'factor/utils.cc' 'failed'
  if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
  && ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
    md5sum -c << SHAR_EOF >/dev/null 2>&1 \
    || $echo 'factor/utils.cc:' 'MD5 check failed'
b15567b2c520f0535a5b326f07e7986f  factor/utils.cc
SHAR_EOF
  else
    shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'factor/utils.cc'`"
    test 1919 -eq "$shar_count" ||
    $echo 'factor/utils.cc:' 'original size' '1919,' 'current size' "$shar_count!"
  fi
fi
# ============= factor/README ==============
if test -f 'factor/README' && test "$first_param" != -c; then
  $echo 'x -' SKIPPING 'factor/README' '(file already exists)'
else
  $echo 'x -' extracting 'factor/README' '(text)'
  sed 's/^X//' << 'SHAR_EOF' > 'factor/README' &&
This is my factorization "package", which is basically a bunch of programs 
designed to factor large integers.  Note that it relies rather heavily on 
GNU's libg++ (and it's implementation of Integers, in particular).  Porting 
this to other platforms supporting lartge integers should be trivial, but 
tedious (which is why I haven't done it...;).
X
The following programs/algorithms are present:
1) "Dumb" factorization -- done by fact.cc, and is just attempting to divide
X	by integers sequentially, looking for a factor.  Don't use this --
X	it's just there for demonstration purposes (i.e., a big integer 
X	version of `factor').
X
2) pollard.cc -- An implementation of Pollard's p-1 algorithm, which only 
X	works well for a small number of integers, since it has rather
X	strict limitations on the kind of factors it can find.
X
3) lenstra.cc -- The whole reason I wrote these programs was to implement 
X	Lenstra's Elliptic Curve algorithm for factorization.  In the spring
X	of 1995 I had to give a lecture on this algorithm, and I searched
X	for an implementation, but the only one I could find (which was at 
X	AT&T) required me to sign all kinds of doc's about derived work,
X	etc, which I didn't feel like doing.  This program is the result
X	of my frustration...
X
4) utils.cc -- rather trivial functions to do things such as greatest common
X	divisor, least common multiple, checking for primality, raising to a
X	power modulo some number, finding inverses in Z/nZ (which do not
X	exist if n isn't prime, since then Z/nZ isn't a field), reduction
X	modulo N, and checking whether or not certain bits are set in a
X	large integer.
X
The algorithm for InvModN (in utils.cc) comes from "A Concrete Introduction
to Higher Algebra," by Lindsay Childs, and all other algorithms come from 
"Rational Points on Elliptic Curves," by Silverman/Tate.
X
If you have any questions/comments, please feel free to mail me at
(preferably) a540ami@pic.ucla.edu, or amifi@ucla.edu.
X
NOTES:
1) libg++ imposes a limit on Integer size: as far as I can see, it's 2^64k,
which should be fine (unless you're trying to factor numbers with more than
64000 decimal places, in which case you probably shouldn't be using this
program...;)
X
2) You will probably want to play with the curve and values for b and K in
lenstra's algorithm -- what I have there was just a test case (I was testing
1715761513 while developing, as that's the number Silverman/Tate do).
X
3) Copying: You are free to do whatever you like with this code, except
claiming to have written it.  I'd like to hear about any interesting stuff
you do with it, though, so drop me a line.
X
4) If anyone feels like cleaning this (code and pathetic README) up for me,
I'll gladly take any changes.  
X
5) Lastly, if you know of any other implementations (free or PD, *not*
requiring non-disclosure agreements, etc.), please let me know.
X
Ami.
SHAR_EOF
  $shar_touch -am 1222162395 'factor/README' &&
  chmod 0600 'factor/README' ||
  $echo 'restore of' 'factor/README' 'failed'
  if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
  && ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
    md5sum -c << SHAR_EOF >/dev/null 2>&1 \
    || $echo 'factor/README:' 'MD5 check failed'
3323fcaf475dcb120ae68902584e4a60  factor/README
SHAR_EOF
  else
    shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'factor/README'`"
    test 2867 -eq "$shar_count" ||
    $echo 'factor/README:' 'original size' '2867,' 'current size' "$shar_count!"
  fi
fi
rm -fr _sh27903
exit 0


