Re: JSH: Step by step through the factoring algorithm

On Feb 24, 1:52 am, MichaelW <ms...@xxxxxxxxxx> wrote:
James and I have agreed to step through his factoring algorithm. The idea
is that I put up each step and he either agrees with the step as given or
requests changes. The idea is that at the end of the process we have a
complete explanation of the algorithm with an example.

Note that this is a math only thread. Please direct insults, unsolicited
psychological assessments, the spectre of cannibalism, accusation of
trollery, conspiracy theories and discussions of if it is possible for a
JSH thread to do without any of these topics to the many other threads
that are available for that purpose. Thank you for your courtesy.

Step One: Defining terms

We have an integer D that is composite, odd and non-square; D is the
target number to factor.

We also select (D-1) = f_1 * f_2 where (f_1,f_2) is a pair of integers
that factor (D-1). At the least we can use 1 and 2 as factors.

Consider the equation

r^2 - D * s^2 = t^2

We can rewrite this as

(r-t)(r+t) = D * s^2

The algorithm will be generating (r,s,t) such that

(1) s is very small (1 is optimal but small enough to easily divide into
(r-t) and (r+t) is sufficient)
(2) abs(r-t) and abs(r-t) are both > s^2 (thus avoiding trivial
factorisations)

Example: For our example we will be factoring D = 1111. D is of course
factored by 11 and 101.

D-1 = 1110. The possible values of (f_1,f_2) are (1,1110) (2,555) (3,370)
(5,222) (6,185) (10,111) (15,74) (30,37) (37,30) (74,15) (111,10) (222,5)
(370,3) (555,2) and (1110,1).

One solution for (r,s,v) is (112,2,90) such that

112^2 – 2^2 * 1111 = 90^2

And hence

(112 + 90) (112 – 90) = 1111 * 2^2
202 * 22 = 1111 * 2^2

Dividing through the factors of s^2 (2 and 2) gives us

101 * 11 = 1111

Thus we have a factorisation for D=1111.

Commentary: I know this is stating the obvious but it is important to
agree on terms and goals when specifying any algorithm. The next step
introduces the idea of functions for r,s,t using a single generating
variable v.

James, over to you. Do you agree so far or do you want changes?

Oh, yeah. Looks ok to me. But none of it so far is my research.
There's nothing new in there.


James Harris

.