Re: Surrogate factoring and the k/T ratio
- From: rossum <rossum48@xxxxxxxxxxxx>
- Date: Wed, 28 Feb 2007 16:36:30 +0000
On 24 Feb 2007 08:39:04 -0800, jstevh@xxxxxxxxx wrote:
For years I've done research on ways you might factor a targetAs biggus pointed out, doing what you say gives
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
(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.
[snip]
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.
Thinking about it, I realized that the k/T ratio was dropping, andSo I will use (a-b) = -1 and k = floor(T/5). With these values the
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.
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.
Probe ratio = 1 : 893.13
Trial average = 119.35 probes.
Random average = 368.228 probes.
500 tries, 0 misfactors found.
Average k's tried per factorisation: 74.806
As seems usual with James' methods it will factorise the target
number, but more slowly than existing methods.
Previously Tim Peters suggested that multiplying the surrogate by
27,000 would result in a faster factorisation. Trying this
modification the figures are:
Fermat average = 7.65 probes.
JSH average = 1512.02 probes.
Probe ratio = 1 : 197.65
Trial average = 120.134 probes.
Random average = 359.302 probes.
500 tries, 0 misfactors found.
Average k's tried per factorisation: 12.712
These figures would indicate that rather than using
S = 2k^2 - T
for the surrogate (S) it would be better to use
S = 27,000 * 2k^2 - T
However the improvement is not sufficient to make James' method faster
than existing factorisation methods. Even with the suggested
improvement it is nearly 200 times slower than Fermat's method.
rossum
.
- References:
- Surrogate factoring and the k/T ratio
- From: jstevh
- Surrogate factoring and the k/T ratio
- Prev by Date: Re: generating a primitive polynom for LFSR
- Next by Date: Re: My attempt to break Rijndael (SAT-attack)
- Previous by thread: Re: Surrogate factoring and the k/T ratio
- Next by thread: Ref for a proof?
- Index(es):
Relevant Pages
|
|
