1
A better algorithm for factoring odd positive integers is .
Let be an odd composite number. Prove that can be written as the difference of two perfect squares:
Consequently, a positive odd integer can be factored exactly when we can find integers and such that
Write a program to implement the following factorization algorithm based on the observation in part (a). The expression
ceiling(sqrt(n))
means the smallest integer greater than or equal to the square root of Write another program to do factorization using trial division and compare the speed of the two algorithms. Which algorithm is faster and why?
x := ceiling(sqrt(n)) y := 1