Xref: utzoo sci.math:15816 comp.theory:1658 sci.crypt:4333
Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!hellgate.utah.edu!csn!ccncsu!ld231782@longs.LANCE.ColoState.EDU
From: ld231782@longs.LANCE.ColoState.EDU (L. Detweiler)
Newsgroups: sci.math,comp.theory,sci.crypt
Subject: Lankinen's recursive factoring algorithm
Message-ID: <13559@ccncsu.ColoState.EDU>
Date: 17 Mar 91 07:02:06 GMT
Sender: news@ccncsu.ColoState.EDU
Reply-To: ld231782@longs.LANCE.ColoState.EDU
Lines: 270

Let f(u,v,b,n) := | [otherwise]
                  |  f(u+b,v,2b,(n-v)/2) or f(u,v+b,2b,(n-u)/2) if n odd
                  |  f(u,v,2b,n/2) or f(u+b,v+b,2b,(n-u-v-b)/2) if n even
 
Thm: f(1,1,2,(m-1)/2) = (p,q) iff pq=m for odd m.
---
 
Pf:
--
 
Let the term `call' refer to any (recursive) instance of the function
(including the `base case' of the thm above).  More formally, if in the
definition above `or' is taken as set union, and undefined cases as the
empty set, then the range of the function f (when called in the specified
way) is a set of pairs, and a pair (p,q) is contained in this set iff pq=m
(the domains of all parameters are integers).  For purposes of explanation
let the term `return' informally denote this membership.
 
Main Thm:
--------
 
Then the thm becomes
 
f returns (p,q) iff pq=m for odd m when called in the above form.
 
That is, f returns the set of all factors of m.  The pf will be established
inductively.
 
Inductive Hypotheses:
--------------------
 
  (i) f is called for all uv=m (mod b) with
 (ii) u,v odd, b even, u<b, v<b,
(iii) n=(m-uv)/b, uv<=m, and
 (iv) all if n>=0.
 
Inductive Thm:
-------------
 
The inductive thm to be established here is:
 
If b>m, then f returns (u,v), otherwise f is called for all u'v'=m (mod b')
with u',v' odd, b' even, u'<b', v'<b', n'<(m-u'v')/b', and u'v'<=m.
 
It will be shown that there is an exact correlation between the inductive
thm, instances of the function, and ultimately the main thm above.  So if
the inductive thm holds and the base case satisfies the hypotheses then the
main thm would be established, because the thm either satisfies the main
assertion or `delegates' the proof to another case that does by preserving
all inductive conditions (other than n'>=0, but the function is undefined
when n'<0).
 
Hence, for the inductive hypotheses and thm, the variables can be taken for
those in any (recursive) instance of the function, where the `prime'
variables denote the new values of the recursive call.
 
Main Thm by Hypotheses:
----------------------
 
Proceeding, note that for all recursive calls in f, n'<n and b'>b, so
eventually b>m or n<0.  The case where n<0 is irrelevant to the question of
what f returns (since it is undefined, it `doesn't return anything').
Otherwise, b>m.
 
Since, by hypothesis,                     uv = m (mod b)
                                          (u mod b)(v mod b) mod b = m mod b
Also, since u<b and v<b it follows that   (uv) mod b = m mod b
Then with uv<=m<b,                        uv=m
Finally, with n=(m-uv)/b,                 n=0
 
That is, when n>=0, b>m iff n=0 iff uv=m.  this establishes the exact
correspondence of the inductive thm, instances of the function, and the main
thm above.
 
It remains to establish that the inductive conditions hold in the recursive
function calls.
 
Inductive Conditions:
--------------------
 
(ii)
----
 
For a convenient abbreviation, herein let the variable `z' designate `both u
and v' or `either u or v' as determined by context.  That is, whatever holds
for z holds for both u and v, or either u or v, as the case may be.
 
By hypothesis, z is odd, and all recursive calls have either z'=z or z'=z+b
where b is even.  Hence z' is always odd.  Also, in all cases b'=2b, so b'
is even (in fact it must be a power of two from the base case).  For the
inequalities, if z'=z then z'<b' because z<b<2b.  Otherwise z'=z+b and z'<b'
because z+b<2b where z<b by hypothesis.
 
(iii)
-----
 
The equality is established for all cases from the equation n=(m-uv)/b of
the hypotheses.
 
                 n-v   m-uv-vb
In one case n' = --- = ------- and u'=u+b,v'=v, so n'=(m-u'v')/b'.
                  2      2b
 
By symmetry this holds for the other case when n is odd.  When n is even,
in one case
 
     n   m-uv
n' = - = ---- with u'=u and v'=v, so again n'=(m-u'v')/b'.
     2    2b
 
In the final case where u'=u+b, v'=v+b,
 
                           2
     n-u-v-b   m-uv-ub-vb-b    m-(u+b)(v+b)   m-u'v'
n' = ------- = ------------- = ------------ = ------
        2           2b              2b          b'
 
Finally, u'v'<=m holds because with n'=(m-u'v')/b' in all cases,
m=b'n'+u'v', and u'v'<=b'n'+u'v' for all (relevant) n'>=0.
 
(iv)
----
 
As noted, since the function is undefined when n<0 the case is
inconsequential (it is automatically satisfied).
 
(i)
---
 
First the justification of the `all' qualifier will be postponed, so that
it remains to show that u'v'=m (mod b').  All cases are established with
m=nb+uv by hypothesis. When u'=u+b and v'=v,
 
 
      u'v' = m (mod b')
(u + b)(v) = (nb + uv) (mod 2b)
   uv + vb = nb + uv (mod 2b)
        vb = nb (mod 2b)
         v = n (mod 2)
 
which follows because v is odd by hypothesis and n is odd in this case.
(``The reversion to synthesis is easy.'' --Fermat)  By symmetry
u'v'=m (mod b') holds for the other case of odd n.  When u'=u and v'=v,
 
u'v'= m (mod b')
 uv = m (mod 2b)
 uv = nb + uv (mod 2b)
  0 = nb (mod 2b)
  0 = n (mod 2)
 
which follows because n is even in this case.  Finally, when u'=u+b,v'=v+b,
 
              u'v' = m (mod b')
    (u + b)(v + b) = nb + uv (mod 2b)
uv + ub + vb + b^2 = nb + uv (mod 2b)
     ub + vb + b^2 = nb (mod 2b)
    (u + v)b + b^2 = nb (mod 2b)
             u + v = n (mod 2)
 
which follows because u and v are odd by hypothesis and n is even in this
case.
 
Finally, the `all' qualifier must be justified to hold as an inductive
condition.  It asserts that every case that satisfies all conditions
(i)-(iv) is encompassed by the multiple recursive calls (as well as the base
case).  For this some additional notation will be introduced.  For any pq=m
let
 
    p - p mod b      q - q mod b
x = -----------, y = -----------
        b                 b
 
for each instance of the function (in every recursive call).  With u<b and
v<b, the substitutions xb+u=p, yb+v=q imply u = p mod b, v = q mod b, and
since n=(m-uv)/b, n can then be expressed as
                                                         2               2
m-(p mod b)(q mod b)   pq-(p-bx)(q-by)   pq-(pq-qbx-pby+b xy)   qbx+pby-b xy
-------------------- = --------------- = -------------------- = ------------
          b                   b                    b                  b
 
or n=qx+py-bxy.  From this the following is readily verified, given that
that b is even and p,q odd: x,y have the same or opposite parity according
as n is even or odd, respectively.  Hence when n is odd x and y have
opposite parity, so let x=2x'+1 and y=2y'.
 
        xb + u = p      yb + v = q
(2x' + 1)b + u = p    2y'b + v = q
  x'2b + b + u = p    y'2b + v = q
 
With these variables the considerations above establish that x'b'+u'=p and
y'b'+v'=q.  This requires that u'=u+b and v'=v, as is exactly the case in
the function itself when n is odd (symmetry gives the other assignment with
u'=u and v'=v+b).  Similar considerations show that when n is even, the
inductive hypotheses alone require that u'=u and v'=v or u'=u+b and v'=v+b,
again as in the function.  Thus the function is called recursively for all
permissable values in the prime variables (that is, all those that satisfy
the inductive conditions).
 
Base Case:
---------
 
Because the main thm either holds for the inductive hypothesis or preserves
the inductive conditions, it only remains to show that the base case
satisfies the conditions as well to prove the thm.  However, this is trivial
to verify for all conditions (i)-(iv).  Since the base case is the *only*
form that satisfies (i) for b=2, the function is called for *all* parameters
satisfying (ii)-(iv), thereby satisfying (i) and completing the proof of the
main thm.
 
* * *
 
It may be illuminating to consider the relation of the Lankinen function in
a `computational hierarchy' of other factoring functions.*  Assumptions are
made herein on the basis of conventional digital (binary) computers.  Also,
complexity orders are given for the worst case scenarios (when the number to
be factored is prime).  However, all algorithms would probably perform to
the same constant multiple of the given orders for complete composite
factorizations.
 
Thm: Eratosthenes' Sieve is very roughtly O(ln(n)/n) in time and
     O(n*log2(n)) in space.
Pf: It works with all prime factors less than n (about ln(n)/n by the prime
    number thm), requiring an array of size proportional to n with log2(n)
    space for each entry.
 
Thm: `Odd factors' is O((sqrt(n)/2)*log2(n)) in time and O(log2(n)) in
     space.
Pf: It tests all odd factors less than the square root of n (about
    sqrt(n)/2), with log2(n) time for each division.  It requires only
    log2(n) space for the number and divisors.
 
Thm: Lankinen's algorithm is O(sqrt(n)/2) in time and O((sqrt(n)/2)*log2(n))
     in space.
Pf: The algorithm is easily modified to seach only for factors p<q for all
    pq=m.  Then the recursive call tree forms a geometric progression
    starting at one, and doubling until reaching sqrt(n)/2, or a length of
    log2(sqrt(n)/2).  From the formula for a geometric progression, there is
    a total of about 2^log2(sqrt(n)/2) = sqrt(n)/2 calls.  Assuming that
    addition, subtraction, comparison, and multiplication/division by two
    occur in constant time, this implies O(sqrt(n)/2) time and a
    O((sqrt(n)/2)*log2(n)) requirement of stack space.
 
Hence, if a ranking of factoring algorithms is viewed as a continuum, with
Eratothenes' sieve and `odd factors' at the extremes (the former with
relatively large space requirements but minimal time demand, and vice-versa
with the latter), Lankinen's function comes somewhere in the middle.  In
regard to timing characteristics, there is probably some number N such that,
in factoring it, Lankinen's algorithm and `odd factors' have the same
execution time (the large time overhead associated with the stack
maintenance of the former would cause a delay in overtaking the latter).
However, because Lankinen's is faster by a factor of about O(log2(n)), for
numbers around the range of twice N the expectation is that Lankinen's
algorithm would be twice as fast, and for numbers around twice that
(quadruple N), the algorithm should be three times faster, and so on.  Of
course, space requirements are much more significant, but still less than
the extreme.
 
* The author admits to some loss of rigor and confidence here, but hopefully
  nonetheless within the bounds of error.  This section isn't intended to be
  authoritative so much as it is to spur interest and research.
 
P.S. Lankinen's function might be useful in attacking the numerous
     unresolved conjectures about primes (e.g. on the infinitude of `twins'
     or Goldbach's).
 
P.P.S. Email the author for C code that implements Lankinen's algorithm or
       information on its historical development.
 

ld231782@longs.LANCE.ColoState.EDU