Re: JSH: Moving through it

jstevh_at_msn.com
Date: 01/25/05 

Date: 24 Jan 2005 18:26:49 -0800

rupertmccal...@yahoo.com wrote:
> Why do you think you've solved the factoring problem?

There are lots of good factoring methods that have problems with two
primes specially chosen to be difficult to factor.

I considered that and thought that there might be a way to sort of
chain one factorization to another, so that instead of factoring the
hard target directly, you could factor some other number, which would
give you the factorization of the target.

That's what I call surrogate factoring and I've been working at it for
some time, and had a major breakthrough last December.

So, why is it a solution to the factoring problem?

I can explain *mathematically* in a small space.

Remember I focus on two quadratics:

yx^2 + Ax - j^2 = T

and

yz^2 + Az - j^2 = 0

where the idea is, given j, T, and A, can you find rational x, y and z?

The answer is, sometimes, yes, and since

x(yx + A) = j^2 + T

you can simply choose j^2 + T equal to the number you wish to factor to
be try and get an x that has a numerator that gives a non-trivial
factor of x.

Remember, x and y are rationals, so they can be fractions, and I've
seen they're usually fractions.

I'm sure you've seen me talking about that before, so why is the theory
I've worked out around these expressions a solution to the factoring
problem?

Well, it's rather easy to prove that if the numerator of x has one
prime factor in common with j^2 + T, which I call M, the target you're
trying to factor, then the rational y that is associated with it must
be given by the method I outline in my paper which involves using the
factors of T.

That set of y's is the complete set for finding factors of M from a
rational x.

That is just mathematically certain, and provable.

Still there is the question of whether or not for a given j, T, and A,
is there always a rational x that will work?

My initial assumption was that there was.

I found out when I wrote my program and it didn't factor 100% that
there wasn't.

I got frustrated, worried that maybe I was just wrong, and started
talking the problem out on Usenet.

The solution is that for a given rational x the probability that it
will factor M is approximately 50%, which has to do with quadratic
residues.

It is also possible that for the rational y's given by my method, you
will not find a rational x, which was a BIG concern.

However, I have theorized that's a matter of factors of 2.

Now then, some of you may think I've just shot down my own claim by
talking about 50% probability with a rational x, when you might find
for some j that you don't even get a rational x using all the y's that
you find using my algorithm.

But that's for one j.

You can change j.

More importantly, I think you can just multiply by factors of 2 in a
certain way, to get more rational x's and the probability rises rapidly
as you do so, until it's basically certainty with any typical j for a
large M.

That's all technical related to the theory, so what's easy?

There's not a lot of it that's easy. But the gist of it is that I have
this technique which allows you to pick some integer j, and then you
take M^2 - j^2 to get a number T, which is the number you *must* be
able to factor.

You can factor it anyway available from elliptic curve to the NFS, and
then you take the factors of that number, to get rational y's, and from
the rational y's, you can get rational x's, and if you find you're not
getting any x's that are rational, you need to multiply through by 2.

For each rational x that you find, there is a 50% probability you will
factor the number without regard to its size.

So, the method I've outlined merely requires that you be able to factor

M^2 - j^2

to get at the factorization of M, and if you find that M^2 - j^2 is
hard to factor with a particular j, then you shift to another one.

So, it doesn't matter how carefully someone picks the prime factors of
M, as you're going to factor something offset from M.

All of the engineering remaining has to do with testing what I've
outlined at the Yahoo! site, as there's actually not a lot.

Someone potentially can factor an RSA challenge number just by using
some technique to get M^2 - j^2 factored.

If they get any rational x's at all, there's a 50% probability that
anyone of them will factor and if they have n rationals x's the
probability of a factorization is

(1 - (1/2)^n)* 100%

so if you manage to find 4 rational x's then you have a 93.75%
probability of factoring the number, no matter how big the number is.

The mathematics proving every statement in this post is already worked
out, except for the guess that multiplying through by factors of 2 will
help give you a rational x's, though I have a good feeling about that
guess.

The rest of it is outlined in my paper and in posts at the Yahoo! site.

There's also a bit of information in how I implemented the theory in my
prototype, proof-of-concept program.

I'm more interested here in outside verification of the theory, so that
someone will take me seriously before it's too late.

If I'm wrong, then the paper and posts I've made will have flaws.

Mathematics allows you to check me here versus engaging in silly
discussions.

If I'm wrong, prove it. But when you see that I'm right, then someone
had better start acting sensible, or you will end up waiting until the
truth is forced upon you.

And that will probably mean that someone uses the new information to
undermine Internet security in some way, and that it is something so
big that you no longer have room to deny the truth here.

It's such a stupid, sad state of affairs. I *should* just be able to
explain, answer your questions, and work out the theory so that you
know it is correct.

But I think we all know that's not what's going to happen.

When something breaks...something big...then you'll pay attention.
James Harris

Relevant Pages

  • Re: Easy test of surrogate factoring
    ... > Here's an even easier test of surrogate factoring: ... It's a well-known technique to work backwards to figure out what's ... The reason is simple, the mathematics doesn't work for them either way, ... That proves that there are rules governing the value of the rationals ...
    (sci.math)
  • Re: Easy test of surrogate factoring
    ... > Here's an even easier test of surrogate factoring: ... It's a well-known technique to work backwards to figure out what's ... The reason is simple, the mathematics doesn't work for them either way, ... That proves that there are rules governing the value of the rationals ...
    (sci.crypt)
  • Re: JSH: Nearly done
    ... > theory and method for factoring that I call surrogate factoring. ... > The mathematics though is surprisingly simple, ... but are in the field of rationals. ...
    (sci.math)
  • Re: JSH: Nearly done
    ... > theory and method for factoring that I call surrogate factoring. ... > The mathematics though is surprisingly simple, ... but are in the field of rationals. ...
    (sci.crypt)
  • Re: SF: Areas of confusion, infinity
    ... > notably the set of rationals. ... choosing any integer is the same as the probability of any other ... That's what make the factoring problem interesting, i.e., not ... > is naive with the surrogate factoring theorem. ...
    (sci.crypt)