Re: Surrogate factoring and the k/T ratio
- From: jstevh@xxxxxxxxx
- Date: 28 Feb 2007 17:36:41 -0800
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
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
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
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
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.
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
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
And they get all the important things wrong.
- Prev by Date: Re: disc erasure
- Next by Date: Re: Quantum Cryptography can not work
- Previous by thread: Re: Surrogate factoring and the k/T ratio
- Next by thread: Re: Surrogate factoring and the k/T ratio