JSH: Step by step through the factoring algorithm

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?

Regards, Michael W.
.

Relevant Pages

  • beta version of Victor Shoups book, "A Computational Introduction to Number Theory and Algebra&
    ... Computing with Large Integers ... The Basic Euclidean Algorithm ... Factoring and Computing Euler's phi-Function are Equivalent ... The Existence of Finite Fields ...
    (sci.crypt)
  • Re: Ultimate check, new way to factor or not?
    ... It's commonly known as a the "factoring sieve" and Fermat showed that ... It is listed as "algorithm ... "factoring with sieves" on pp.389. ... > when it defies the mathematics. ...
    (sci.crypt)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.crypt)
  • Re: Benchmark challenge
    ... >> inelegant program with benchmark data against which you can ... > James is claiming that his current program is just a prototype to test his ... > algorithm, and that there is therefore room for substantial ... James claimes that he has a "solution" to the factoring problem. ...
    (sci.math)