pollardP-1.frink

View or download 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")]
}


View or download 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 17835 days, 15 hours, 27 minutes ago.