Re: Congruence based factoring algorithm, revised

On Tue, 2 Dec 2008 17:29:16 -0800 (PST), JSH <jstevh@xxxxxxxxx> wrote:

An initial presentation of a prior version of this algorithm had a
fatal error. The underlying equations are the same but I was using
them wrong. Here is the corrected algorithm.

It defies conventional wisdom by showing a congruence based factoring
method
You could phrase this better, something like:

"It is a congruence based factoring method ... "

that allows you to pick a large enough prime p, and solve for
f_1 and f_2, where f_1*f_2 = T, where T is the target composite to be
factored mod p.

With all positive integers, given a target composite T to be factored,
first find a prime number p greater than sqrt(T).
You missed a trick here James. It is possible that p is a factor of T
so you need to check that at this point. Indeed it is essential that
you check it, otherwise you will get into problems further on.

Then set a variable
I call 'a', to a=2 and calculate a variable I call k, with the
following congruence relationship:

k^2 = (1 + a^2)^{-1}(T) mod p.
This is where the problems with T mod p = 0 start. k = 0 is the only
solution.


where if it does not exist,
Here I assume you mean "if k does not exist,".

you increment 'a' by 1 and try again.
There is a 50% chance that any particular 'a' will work as there are
(p-1)/2 quadratic residues modulo p.

If you get a k then you check for a solution for f_1 and f_2,where

f_1*f_2 = T

with

f_1 = ak mod p and f_2 = a^{-1}(1 + a^2)k mod p.
More problems in the T mod p = 0 case. If k = 0 then f_1 = 0 and f_2
= 0. Divide by zero errors do not make for a good algorithm when
coding it up on a computer.


If ak is greater than p, and you've succeeded when you take ak modulo
p, you will have a factor of T. If it is less than p, see if a(p-k) is
greater than p, and check that mod p if it is. However, f_1 may be the
larger factor so also check f_2, as then it will give the smaller
factor exactly or p - f_2 will.
As I read this, there are three possible factors to try: f_1, f_2 and
p - f_2. I try them in that order and stop after the first factor is
found.

The T mod p = 0 case uses the third factor, since p - 0 = p which is
indeed a factor of T. You could have got to it a lot earlier in your
algorithm if you had checked for it when picking p.


I would appreciate comments or criticisms on this approach and
apologize if it's not close to some standard form. I am cutting and
pasting from several sources.

James Harris

I coded James' algorithm, with the additional check for T mod p = 0
and an early exit.

As I have done previously, I tested James' latest factoring method on
500 random composite odd numbers that are multiples of two different
primes, each in the range 500 to 1000. The results are compared to
Fermat's method, trial factorisation (both forward and reverse) and
random picking.

Fermat average = 7.54 probes.
JSH average = 31.44 probes.
Probe ratio = 1 : 4.170
Trial average = 119.50 probes.
Reverse average = 11.91 probes.
Random average = 667.75 probes.
500 trials, 0 misfactors found.

Average a's tried per factorisation: 11.744
Average p's tried per factorisation: 7.078
Average a's tried per p: 1.659
Average k's tried per factorisation: 6.092

Average timings over 200 numbers:
16 bits: 15.840 mSec average per number. 0 misfactors.
18 bits: 35.557 mSec average per number. 0 misfactors.
20 bits: 89.864 mSec average per number. 0 misfactors.
22 bits: 269.572 mSec average per number. 0 misfactors.
24 bits: 698.010 mSec average per number. 0 misfactors.

As seems usual with James' methods it will factorise the target number
correctly, but has no speed advantage over existing methods. Judging
from the timing tests, this latest method does not scale well to
larger numbers.

rossum

.

Relevant Pages

  • Re: JSH: Hammer falls, Pells Equation used to solve factoring problem
    ... This talk about minima is a red herring. ... I think it's worth pointing out that there are two possible ways that James' thinking is wrong about this. ... So it looks a lot like finding a v which gives rise to a factorisation of D will turn out to be no easier than finding a factor of D by trial division. ...
    (sci.math)
  • Re: JSH: Contradictory behavior, issue of math fraud
    ... James usually has you /in addition/ putzing around with systematically ... factors of S and count all the probes used for that. ... Average n's tried per factorisation: ... method after method that /essentially/ feed pseudo-random integers into ...
    (sci.math)
  • Re: JSH: SF Algorithm
    ... which with my program has meant roughly 32 surrogates to factor. ... I tested James' latest version of his ... Average k's tried per factorisation: ... This version runs faster than both random picking and James' current ...
    (sci.math)
  • Re: JSH: SF Algorithm
    ... I tested James' latest version of his ... Reverse average = 11.72 probes. ... Average k's tried per factorisation: ...
    (sci.math)
  • Re: Factorisation algorithms
    ... if the processing time for an arithmetic ... which is to say numbers with roughly N log N digits. ... The original claim for the algorithm was that factorisation is ...
    (sci.math)