## An equivalent algorithm to trial division

Expand Messages
• 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
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.