Re: Surrogate factoring and the k/T ratio

On Feb 28, 5:36 pm, jst...@xxxxxxxxx wrote:
On Feb 28, 8:36 am, rossum <rossu...@xxxxxxxxxxxx> wrote:





On 24 Feb 2007 08:39:04 -0800, jst...@xxxxxxxxx wrote:

For years I've done research on ways you might factor a target
composite T by factoring some other number I call the surrogate, and
after a lot of failed approaches I realized that the idea
mathematically reduced to a couple of very simple relations:

x^2 ? y^2 mod T

and

k^2 ? 2xk mod T

where the first should be familiar enough, while the second is an
addition needed mathematically by the concept of surrogate factoring.

So after a lot of years of fumbling around I found mathematically I
could reduce the idea quite simply to the given relations.

Now using those requires going to explicit equations:

x^2 = y^2 + aT

and

k^2 = 2xk + bT

and I can add one to the other, and complete the square to find:

(x+k)^2 = y^2 + 2k^2 + (a-b)T

As biggus pointed out, doing what you say gives

(x+k)^2 = y^2 + 4k^2 + (a+b)T
^ ^

Where the '4' and the '+' are different from your result.

I will use your equation for my tests, but there is still an open
question here.

So, if you have

4f_1f_2 = 2k^2 + (a-b)T

then y = f_1 - f_2 and

x = f_1 + f_2 - k

and now the idea is just slightly more complicated, and you can see
that actually trying to factor with it requires that you pick a-b and
k.

[snip]

Thinking about it, I realized that the k/T ratio was dropping, and
that when it was factoring very well the k/T ratio was about 0.2 or
20%. But I don't know if that is the prime value, as the research is
very rough at this point. But an optimal k/T ratio seems key.

The lower the ratio the better as the surrogate you factor is 2k^2 +
(a-b)T, so the smaller it is, the better, so I used a-b=-1, and a k
that was about 20% of T, and got great results.

So I will use (a-b) = -1 and k = floor(T/5). With these values the
surrogate to factor is 2k^2 - T. If a value of k fails to produce a
proper factor then I will increment k by 1 and try again.

As I have done previously, I tested James' 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 and random picking.

Each "probe" is a GCD, trial division or equivalent. It is not a
count of the number of k's tried since each k results in many possible
factors of 2k^2 - T. I have indicated separately the mean number of
values of k tried.

Fermat average = 7.238 probes.
JSH average = 6464.48 probes.

That's wrong.

The damn thing is brutally efficient. Brutally.

With the small numbers in the range you claim to be testing, I'm
getting answers with a single k or within 1 or 2 of it, so you
completely screwed up or you're just incompetent or something, I don't
know what and I don't care really.

Before I talked about but did not test, now I'm testing, so I know
what it actually does, and succinctly, performance follows theory.

Surrogate factoring IS here now. Usenet is worthless for talking it
out so I'll focus more on my own sites as for instance, I have to
update my math blog which has some actual examples which I have to
update.

I really do not know why some of you lie about mathematics, but I note
for those who don't understand, it is EASIER to lie about mathematics
than other areas as it is so hard for others to check!!!

How many of you reading this are capable of quickly checking
yourselves to be sure?

That's why it's easy to lie about math.

I'm over my fears about this research as I am no longer thinking that
hey, it'll crash the world economy. The odd coincidence of the stock
market drop yesterday actually calmed my fears even more.

Even if this thing brings things down a bit, it'd just be another
storm that will come and go.

Usenet is USELESS in terms of the replies to me as my analysis
indicates that a lot of the people replying are not, well, all there
as they say. Quite simply, they are not competent to comment on my
research.

And they get all the important things wrong.

James Harris- Hide quoted text -

- Show quoted text -

Are you going to bother claiming the RSA prizes on offer, or just
settle for fame alone?

.

Relevant Pages

  • 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: Surrogate factoring and the k/T ratio
    ... addition needed mathematically by the concept of surrogate factoring. ... composite odd numbers that are multiples of two different primes, ... I really do not know why some of you lie about mathematics, ...
    (sci.crypt)
  • Reality check, surrogate factoring
    ... Surrogate factoring is meant to beat the tactic of picking two hard ... and it will be really big for a big target. ... of the time for rationals x's. ...
    (sci.math)
  • Reality check, surrogate factoring
    ... Surrogate factoring is meant to beat the tactic of picking two hard ... and it will be really big for a big target. ... of the time for rationals x's. ...
    (sci.crypt)
Loading