Download or view pollardP-1.frink in plain text format
// Sample implementation of the Pollard p-1 algorithm for factoring numbers.
// This was the prototype implementation for the way that the factoring is
// actually implemented in Frink (the final product is written in Java and
// integrated with other factoring tests.)
//
// The algorithm was described wonderfully as Algorithm 5.3 in the book
// David M. Bressoud, _Factorization and Primality Testing_
//
// Thanks to Clint Williams for patronage and gift of this book.
//
factorPollardPMinus1[n, maxIter=1000000, startC=2, startI=0, startM=2 ] :=
{
if isPrime[n]
return n
c = startC
m = startM
iterations = 0
i = startI
while (iterations < maxIter)
{
i = i + 1
iterations = iterations + 1
m = modPow[m, i, n]
if i mod 10 == 0
{
g = gcd[m-1, n]
if g > 1
{
// If we get here, g is either a proper divisor,
// or it's equal to n.
if g == n
{
// If it's equal to n, then
// the algorithm won't work for this value of c.
// In that case, we have to increment c to the next
// prime and start over.
do
c = c + 1
while !isPrime[c]
println["Incrementing, i=$i, c=$c"]
m = c
i = 0
} else
return [factorPollardPMinus1[g, maxIter-iterations, c, i, m], factorPollardPMinus1[n/g, maxIter-iterations, c, i, m]]
}
}
}
println["No factor found."]
}
// Test run to factor the Mersenne primes.
for b = 1 to 128
{
println["\n$b:"]
start = now[]
print[factorPollardPMinus1[2^b-1]]
end = now[]
println["\t" + (end-start -> "ms")]
}
Download or view pollardP-1.frink in plain text format
This is a program written in the programming language Frink.
For more information, view the Frink
Documentation or see More Sample Frink Programs.
Alan Eliasen was born 19970 days, 15 hours, 38 minutes ago.