/*********************************************************************
 *	shor.cc -- Use Shor's Algorithm 
 *		to factor a large integer
 * 
 *	Compile:
 *	 g++ -s -O4 -o shor shor.cc
 *	Invoke:
 *	 ./shor NumbertoFactor InitialK
 * ChangeLog:
 *  970225 -- Created by Paul Herman <a540pau@pslc.ucla.edu>
**********************************************************************/

#include <Integer.h>

#define max(a,b)	(a<b)? b : a


/********************************************************************
/*  Period:  This computes the size of the group generated by a mod n
/*           i.e. |<a>|
/********************************************************************/
int	Period(Integer a, Integer n) {
	register int count;

	count = 1;
	while (PowModN(a, count, n) != 1) count++;
	return count;
}

/*********************
/*  ShorFactor:  Finds a factor of n by looking at the group generated
/*               by <a> mod n.  Let t = |<a>|/2  .  Check to see if
/*               t +/- 1 and n have a common factor.  If not, try another a 
/*********************/

Integer ShorFactor(Integer n) {
	Integer a, t1, t2, f1, f2;
	int r;

	a=2;
	while (a<=n) {
		f1 = gcd(a, n);
		if (f1 != 1) return f1;

		r = Period(a, n);
		t1 = PowModN(a, (r/2), n);
		t1 += 1;
		t2 = t1 - 2;

		f1 = gcd(t1, n);
		if (f1 != 1) return f1;

		f2 = gcd(t2, n);
		if (f2 != 1) return f1;

		a += 1;
		}
	return (Integer)1;	// No luck at all (This never happens)
}

int main(int argc, char *argv[]) {
    Integer n, k;

    if (argc != 2) {
	cerr << "Usage: " << argv[0] << " NumberToFactor" << endl;
	cerr << "For an example, try " << argv[0] << " 1715761513" << endl;
	return -1;
    }

    n = argv[1];

    cout << n << ": " << flush;
    while (!isprime(n) && n > 1) {
        k = ShorFactor(n);
        cout << k << " " << flush;	
	n /= k;
	}
    cout << n << endl;
    return 0;
}