# pollardP-1.frink

``` // 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")] } ```

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 18864 days, 23 hours, 54 minutes ago.