pollard.cal

早期freebsd实现

/*
 * Copyright (c) 1993 David I. Bell
 * Permission is granted to use, distribute, or modify this source,
 * provided that this copyright notice remains intact.
 *
 * Factor using Pollard's p-1 method.
 */

define factor(N, B, ai, af)
{
	local	a, k, i, d;

	if (isnull(B))
		B = 1000;
	if (isnull(ai))
		ai = 2;
	if (isnull(af))
		af = ai + 20;
	k = lcmfact(B);
	d = lfactor(N, B);
	if (d > 1)
		return d;
	for (a = ai; a <= af; a++) {
		i = pmod(a, k, N);
		d = gcd(i - 1, N);
		if ((d > 1) && (d != N))
			return d;
	}
	return 1;
}

global lib_debug;
if (lib_debug >= 0) {
    print "factor(N, B, ai, af) defined";
}