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

An equivalent algorithm to trial division

Expand Messages
  • Kermit Rose
    The following code represents a novel, ( and inefficient ) way to factor by trial division. def FactorByGCD(z,trace = 0): #{ steps = 0 if z
    Message 1 of 1 , Sep 1, 2008
    • 0 Attachment
      The following code represents a novel, ( and inefficient ) way to factor
      by trial division.




      def FactorByGCD(z,trace = 0):

      #{
      steps = 0
      if z < 4:
      #{
      print " Factored z = ",z," by z is less than 4. steps = ",steps
      return (1,z)
      #}
      steps = steps + 1
      r = ksqrt(z)
      x = gcd(z,r)
      if x > 1:
      #{
      print " Factored z = ",z," by z has a factor in common with
      its integer square root. steps = ",steps
      return [x,z/x]
      #}
      steps = steps + 1
      pivot = r//2
      x = gcd(z,pivot)
      if x > 1:
      #{
      print " Factored z = ",z," by half integer square root of z has
      a factor in common with z. steps = ",steps
      return [x,z/x]
      #}
      c = 1
      square = pivot * pivot
      while square > 0:
      #{
      steps = steps + 1
      square = square - c
      if trace > 0:
      #{
      print " c = ",c," Trial gcd with ",square
      #}
      c = c + 2
      if trace > 0:
      #{
      print " New c = ",c
      #}

      x = gcd(z,square) ### test if z is divisible by any of [
      pivot - (c+1)/2 , pivot + (c + 1/2), (c + 3) / 2 ]


      if trace > 0:
      #{
      print " steps = ",steps," Trial gcd with ",square," gcd = ",x
      #}
      if x > 1:
      #{
      print " Factored z = ",z," by search for integer with common
      factors. steps = ",steps
      return [x,z/x]
      #}
      return [1,z]
      #}
    Your message has been successfully submitted and would be delivered to recipients shortly.