Re: Surrogate factoring demonstrated
From: Décio Luiz Gazzoni Filho (decio_at_decpp.removethis.net)
Date: 02/25/05
- Next message: Wolf Kirchmeir: "Re: Epistemology 201: The Science of Science"
- Previous message: Wolf Kirchmeir: "Re: Epistemology 201: The Science of Science"
- In reply to: jstevh_at_msn.com: "Re: Surrogate factoring demonstrated"
- Next in thread: Will Twentyman: "Re: Surrogate factoring demonstrated"
- Messages sorted by: [ date ] [ thread ]
Date: Thu, 24 Feb 2005 23:09:00 -0300
jstevh@msn.com wrote:
> <snip>
>
> The algorithm is so simple that it's amazing how often it does work.
It's far from simple, and there are many other factoring algorithms which
are simpler, more efficient and work everytime -- they're everything your
method isn't and will never be.
> Given a target M, you pick a j, where I now recommend picking a j as
> close to M as you can where j is *odd*, as I am now thinking that's
> important, again.
Oh, so that's what you're thinking *now*? I didn't know that mathematical
proofs could change according to the mood of the prover.
> Once you've picked j, you find T, using
>
> T = M^2 - j^2
>
> and my recommendation is that T have 2, 3 and 5 as factors, and there's
> a theoretical reason but I'm keeping things simple here.
The theoretical reason is that having 2, 3 and 5 as factors shaves less than
5 bits from T while multiplying the number of divisors of the cofactor of T
by 8. The more divisors your have, the more likely that the random
parameter w_num is going to have a factor in common with M -- but of
course, you also need more work to iterate through these extra divisors,
and nothing concrete is gained in the end.
> Then you just iterate through integers f_1 and f_2 such that
>
> f_1 f_2 = T^6
>
> so you need to factor T, and you use that f_1 and f_2 in
>
> w_num = +/-(f_1 +/- f_2) - 2T^2 (2j^2 + T)
>
> and you take the gcd of w_num with M, and if it's not 1, then you're
> done.
>
> For the sake of full disclosure I *do* force in factors of 2 by
> considering some rational f_1 and f_2, basically like
>
> 2 f_1 (f_2/2)
>
> as you have to balance out factors forced in that way, of course.
>
> Many of my solutions come with the forced in factors of 2.
>
> That is the full algorithm. I know it looks too simple to be worth
> anything, but if you try it, you will be amazed at the high factoring
> percentage--for small numbers i.e. under 40 bits.
No, it doesn't look simple at all.
*This* is simple: gcd((3^B! mod n) - 1,n). Guess what method I'm talking
about.
This is also simple: while(g == 1) { x = x^2 + 1 mod n; y = y^2 + 1 mod n; y
= y^2 + 1 mod n; g = gcd(x-y,n); }; return g; But I guess you don't know
that method either.
> Then again, I did factor a 90 bit number to demonstrate with, though it
> had 3 prime factors, where I'd multiplied by a cracking prime.
>
> That is, if the number doesn't factor you can multiply it by a large
> prime, and then it might factor.
That was just a random occurrence. However, the idea of multipliers has been
succesfully applied in CFRAC and QS, but that's because there's a well
developed theory behind that.
> The other thing that usually works is to square the number, and then it
> will factor.
Another random occurrence. In fact, not so random: by squaring the
composite, you double its size (as well as the surrogate's), so the
surrogate is likely to have more divisors.
> I'd appreciate some people posting some numbers on percentages of
> success and failure.
Tim has been doing that for a while now.
> The data has gotten rather sparse while I'm seeing some postings that
> seem to deny the true reality of how often this method works!
>
> There is nothing like the facts.
You *think* the method works often because we are blessed with computers so
fast that they can do millions of computations in the blink of an eye.
Why don't you try running surrogate factoring by hand, on paper, using no
computers and no calculators, to get a feel for how easy it really is?
You can also get a feel for how inferior your algorithm is by grabbing
something like PARI/GP, having it factor a batch of random integers, timing
it, then repeating the experiment with your method. I'd be really surprised
if PARI/GP were anything less than 1000 times faster on average than
surrogate factoring, for say 100-bit composites. (And it's only going to
get worse for surrogate factoring when the composites increase in size.)
Décio
- Next message: Wolf Kirchmeir: "Re: Epistemology 201: The Science of Science"
- Previous message: Wolf Kirchmeir: "Re: Epistemology 201: The Science of Science"
- In reply to: jstevh_at_msn.com: "Re: Surrogate factoring demonstrated"
- Next in thread: Will Twentyman: "Re: Surrogate factoring demonstrated"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
