Loading ...
Sorry, an error occurred while loading the content.

Factor iteration algorithm

Expand Messages
  • Kermit Rose
    The following is a test run of my most recent factor algorithm. Is anyone interested in knowing the details of this algorithm? I generate a twelve digit
    Message 1 of 1 , Oct 8, 2008
    View Source
    • 0 Attachment
      The following is a test run of my most recent factor algorithm.

      Is anyone interested in knowing the details of this algorithm?


      I generate a twelve digit positive integer that is the product of two 6
      digit primes.

      >>> p12[0]
      776206165373L

      The parameters of FactorIterate are (z,trace,scale).

      If trace is > 0, intermediate results are printed out.

      Scale controls the size of the iteration step.
      If scale is smaller, each iteration step skips over
      a larger number of possible factors.

      If scale is larger, each iteration step skips over a
      smaller number of possible factors.


      >>> FactorIterate(p12[0],0,3500)



      Factor Iteration did not converge within 10000 steps.

      If convergence does not occur reasonably soon,
      then I should try again with a smaller scale parameter.

      Or I can try again with the same scale parameter,
      because the algorithm relies heavily on random integers,
      and it behaves differently each time it is called.

      >>> FactorIterate(p12[0],0,3500)



      Factor Iteration did not converge within 10000 steps.

      Trying again with a smaller scale.

      >>> FactorIterate(p12[0],0,3000)



      Factor Iteration did not converge within 10000 steps.

      Trying again with a smaller scale.


      >>> FactorIterate(p12[0],0,2000)



      Factor Iteration did not converge within 10000 steps.

      Trying again with a smaller scale.

      >>> FactorIterate(p12[0],0,1000)



      Factor Iteration did not converge within 10000 steps.

      Trying again with a smaller scale.


      >>> FactorIterate(p12[0],0,500)



      Factor Iteration did not converge within 10000 steps.

      Trying again with a smaller scale.

      >>> FactorIterate(p12[0],0,200)


      Found factor at iteration step 1291
      by s2 has factor in common with z.
      [976177L, 795149L]



      >>> p12[1]
      134117759761L
      >>> FactorIterate(p12[1],0,200)


      Factor iteration converged in 3690 steps,
      but did not discover the factors of z.
      [1, 134117759761L]

      Trying again with a larger scale.

      >>> FactorIterate(p12[1],0,300)


      Factor iteration converged in 4896 steps,
      but did not discover the factors of z.

      [1, 134117759761L]

      Trying again with a smaller scale.


      >>> FactorIterate(p12[1],0,250)


      Factor iteration converged in 5432 steps,
      but did not discover the factors of z.
      [1, 134117759761L]

      Trying again with a larger scale.


      >>> FactorIterate(p12[1],0,275)


      Factor iteration converged in 5990 steps,
      but did not discover the factors of z.

      [1, 134117759761L]


      Trying again with a larger scale.

      >>> FactorIterate(p12[1],0,280)


      Factor iteration converged in 4952 steps,
      but did not discover the factors of z.
      [1, 134117759761L]

      Trying again with a larger scale.

      >>> FactorIterate(p12[1],0,290)


      Factor iteration converged in 7996 steps,
      but did not discover the factors of z.
      [1, 134117759761L]


      Trying again with a larger scale

      >>> FactorIterate(p12[1],0,295)


      Found factor at iteration step 2481
      by s4 has factor in common with z.
      [213461L, 628301L]
      >>>
    Your message has been successfully submitted and would be delivered to recipients shortly.