Re: Surrogate factoring approach, analysis

jstevh at msn.com

Bryan Olson

From:	jstevh at msn.com
Subject:	Re: Surrogate factoring approach, analysis
Date:	20 Jan 2005 16:16:18 -0800

I figured, well, why not try.

I'm running the numbers this guy put up through my current program
which is at the Yahoo! group.

Tim Smith wrote:
> In article <1104591454.431335.128080@z14g2000cwz.googlegroups.com>,
> jstevh@msn.com wrote:
> > It turns out that the analysis behind my surrogate factoring
approach is
> > rather easy to walk though with a few basic equations.
> >
> > That should mean I can get people to take me seriously, but you are
> > Usenet, and the problem is held by the math community, so clear
evidence
> > may not work!
>
> All you have to do is show that it works. Here are some composite
numbers
> to test on. Each is the product of two primes whose length is up to
the
> number of bits specified.
>
> Do a couple of examples from the 8 bit or 16 bit section to
illustrate how
> the method actually works, then see if you can do some from the 128
bit
> section.
>
> ====== factors up to 8 bits ======
> 57599

( 239 241 )

I'm copying output from the program, so that's direct output, though I
am leaving out some of the extra information it gives.

> 43139

Skipping...trivially factors as the program has a prime list up to 200.

> 24523

Same as above.

> 34121

Same as above.

> 35953

Same as above.

> 19043

Same as above.

> 33043

Same as above.

> 20567

Same as above, as again, the program automatically will check for
primes up to 200, so these are trivial factorizations for it, not worth
putting up.

> 36089

Same as above.

> 37769

Same as above. Hopefully more interesting below.

>
> ====== factors up to 16 bits ======
> 1996465633

( 35141 56813 )

> 2348221831

Couldn't find factors.

> 3574886741

( 57679 61979 )

> 3172590413

Couldn't find factors.

> 2514657533

Couldn't find factors.

> 1388161393

( 36217 38329 )

> 2335689907

Couldn't find factors.

> 2493433781

( 41879 59539 )

> 1840902013

( 39451 46663 )

> 2095611269

Couldn't find factors.

>
> ====== factors up to 24 bits ======
> 135247262314741

Couldn't find factors.

> 239937525733091

Couldn't find factors.

> 119059652313451

Couldn't find factors.

> 177805283351779

Couldn't find factors.

> 140979690859369

Couldn't find factors.

> 137305167623353

( 11173213 12288781 )

Whew! It's taking a lot longer now as the program really isn't built
for large numbers, yet. It's a proof of concept prototype not built
for speed.

I was worried it might not factor any numbers of this size.

Most of the time is taken with factoring T, the surrogate, and it's
possible that it's not decomposing it fully, but it got at least one.

Each factorization is taken a few minutes now...

> 156432070838873

Couldn't find factors.

I suspect it didn't fully factor T, looking at the factorization it
gave.

For those of you who don't know, T is the surrogate factored to factor
the target, which I call M. Yes, originally in the paper T was to be
the target, but I found my original approach didn't work, and I didn't
feel like changing T in all the equations.

So the program factors T, the surrogate, and then uses that
factorization to get y, and then calculates x, which it checks to see
if it has a gcd with M, the target.

That's how all the factorizations I've given have been done...using my
theory.

> 84697211728937

Couldn't find factors.

> 151766760236149

Couldn't find factors.

> 137083650684517

Couldn't find factors.

The code is at

http://groups.yahoo.com/group/sufactor/

in purple.jar, which does include the source.

Ok, it's took a long while with the numbers above, so I'm stopping
here.

Each attempt was a single pass with j calculated by taking floor(M/2),
getting its residue with respect to 6, and subtracting that. Then T =
M^2 - j^2.

And I used A = 8(92647), and I don't know if that made a difference as
I'm just trying things now.

It is a prototype program, though it is strangely slower than I'd hoped
with these numbers.

And I know, now more of you will make fun of me for such a pathetic
result, but I already said it doesn't factor everything.

If it did, I wouldn't be talking about it publicly.

The question is, what are the limits? Why does it factor some numbers
and not others? It looks from this little experiment like it's getting
worse as the numbers get bigger which is a bad sign, but what are the
mathematical reasons why?

Remember, this is from my theory, a theory you won't find in textbooks,
and if you had Newton write an algorithm based on congruence of squares
soon after he discovered it, would he write the Number Field Sieve?

Think about it before more you yucks decide to make fun of me.
James Harris

From:	Bryan Olson
Subject:	Re: Surrogate factoring approach, analysis
Date:	Fri, 21 Jan 2005 01:01:53 GMT

jstevh@msn.com wrote:
[...]
> The question is, what are the limits? Why does it factor some numbers
> and not others? It looks from this little experiment like it's getting
> worse as the numbers get bigger which is a bad sign, but what are the
> mathematical reasons why?

I expect those results are telling us something. If you recall
your previous "surrogate factoring" algorithm, it was simply
checking the greatest common divisor of the target and some not-
so-interesting numbers. The method amounted to "trial GCD".

The tendency to find small factors and miss large ones is what
we'd expect from such guess-and-check methods when the guesses
are more or less arbitrary.

--
--Bryan