Re: Ultimate check, new way to factor or not?
tomstdenis_at_gmail.com
Date: 01/27/05
- Next message: infobahn: "Re: [Lit.] Buffer overruns"
- Previous message: newstome_at_comcast.net: "Re: [Lit.] Buffer overruns"
- In reply to: jstevh_at_msn.com: "Re: Ultimate check, new way to factor or not?"
- Next in thread: infobahn: "Re: Ultimate check, new way to factor or not?"
- Reply: infobahn: "Re: Ultimate check, new way to factor or not?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 26 Jan 2005 19:39:37 -0800
jst...@msn.com wrote:
> > But, you know, a new *inefficient* way to factor
> > simply isn't interesting.
>
> How fast was congruence of squares when discovered?
Not fast. It was invented when people did math by hand. It was faster
than trial division which was a "big speedup" then.
> Do you even know who discovered it?
Fermat. It's cited in TAOCP and most elementary number theory texts.
It's commonly known as a the "factoring sieve" and Fermat showed that
you can speed over many "invalid potential squares" by using a properly
constructed sieve.
For the benefit of others... In "The Art of Computer Programming"
volume 2, pp. 386 descries Fermat method. It is listed as "algorithm
C" [pp.387]
Algorithm C. Given an odd number N this algorithm determines the
largest factor of N less than or equal to \sqrt{N}.
1. x = 2\sqrt{N}, y = 1, r = \lfloor \sqrt{n} \rfloor ^2 - N
2. if r == 0 then we terminate as N = ((x-y)/2)((x + y - 2)/2) and
(x-y)/2 is the largest factor.
3. r = r + x, x = x + 2
4. r = r - y, y = y + 2
5. if r > 0 goto 4, otherwise goto 2
At first this seems slow as it takes exponential time (in practice it's
equal to the distance from \sqrt{N}).
So this seems a bit slow.. . Fermat then refined this method, from
pp.387, "...It is not quite correct to call Algorithm C Fermats Method,
since fermat used a somewhat streamlined approach..."
The change was to not maintain y but instead look at x^2 - N and guess
whether or not the value was square. This was by using a sieve. E.g.
there are 3 Q.Rs modulo 7. So reduce x^2 - N modulo 7. If the result
is not a quadratic residue then you know that you're not on a possible
factor.
He explains the sieve more on pp.387-388 even citing the factorization
of 8616460799 as "done by hand". Next he describes algorithm D.
"factoring with sieves" on pp.389.
Just so you know ... ;-)
> >What you haven't done is
> > demonstrate your repeated claim that it is
> > polynomial time. Since it can only increase the
>
> That's easily done and has to do with the number of combinations
> generated at each level of calculation, where I mean recursion level.
>
> It's just not worth going into more detail than that now.
Well I'd say it is as you're going on about being persecuted. Maybe
you should actually take the time to present your results. Also just
because it's recursive doesn't mean it's polynomial time. What if you
have to recurse a sub-exponential number of times?
> > size of the surrogate target, you have to end up
> > factoring something with a different method, and
> > the only known different methods are more than
> > polynomial time. Therefore I conclude that your
>
> That's not exactly true.
>
> Besides, I don't have to use different methods to factor T, as in
fact,
> my prototype program recursively calls itself--shrinking numbers all
> the way--until it gets to something under 200, at which point is uses
a
> prime list.
>
> So I know you're not paying attention, already, or you'd have known
> that without me having to repeat it here.
You haven't shown that your algorithm works, is efficient or even
terminates. I'd say Greg has valid reason to disagree with your
polynomial time claim.
> Now, factoring is in general hard, with *certain* types of numbers,
> while not necessarily so with others.
The GNFS would disagree. It can factor ANY number in sub-exponential
time. There are no "harder than average" numbers. Now specially
constructed [e.g. smooth or narrow DoS] composites can be factored in
quick average time those same algorithms (like Fermats) have a large
theta function and their big-oh is nasty.
> My surrogate T, is offset from M, the target by the formula
>
> T = M^2 - j^2
>
> which factors somewhat, immediately into
>
> T = (M-j)(M+j)
>
> where for positive j, M-j is necessarily less than M, and M+j can be
> *given* whatever factor you wish by picking j appropriately, so that
> you can factor it immediately to shrink the number.
You have yet to show how you pick M and j efficiently. If you could
show it then people would be out breaking RSA left right and center.
> There are any number of smart things you can do when you can have as
> much control as my method gives.
But your description is not complete. And what we DO know about it so
far is not new.
> Now I don't see posters talking about that, as you're not interested
in
> the mathematics or what's possible, but only in trying to dismiss my
> discovery.
That's because so far you haven't shown anything that is new or worthy
of the attention you are craving.
People aren't just telling you to factor RSA challenges to shut you up.
They're doing it to show to you that you're wrong. If your method
worked was well as you claimed you'd be factoring RSA sized composites
and getting a lot of attention.
> But you're wasting your time, as mainstream mathematicians will try
to
> ignore it anyway, no matter what you do, so your effort is pointless.
I suspect Greg doesn't have a lot of time, thought or otherwise
invested in this thread. [Nor do many others].
> > method cannot be polynomial time. Now, if it's
> > subexponential, it could still be interesting, but
> > you haven't argued for that, either.
> >
>
> There are only so many factoring methods known, even inefficient
ones,
> while certain key features of my discovery make it very exciting, and
> make it definite that an inefficiency claim at this point is
> short-sighted.
>
> That you jump to a conclusion isn't a surprise to me.
Well given that you haven't shown otherwise what conclusion would you
have them "jump to"? Are you suggesting it's smarter to assume your
method works perfectly?
> You just have something you wish to believe and can't pause for even
a
> moment to let facts gather before you jump in with your opinion, even
> when it defies the mathematics.
Why would it defy mathematics? Either your algorithm works or it
doesn't. There is no magic here.
> I, on the other hand, have worked out a lot of the theory, and the
> theory says that this factoring method is in fact a solution to the
> factoring problem.
You have yet to demonstrate that you understand the principles of the
scientific process. So far I haven't seen a single theory written by
you. You say "I have theories" yet all you write in usenet is
self-serving accusations of persecution and random equations that
aren't "rational". equations are not theories!!!
The fact that you can't implement your algorithm [because you're lazy,
incapable or it just doesn't work] would tend to suggest otherwise.
> That is a statement of mathematical fact. If you don't believe it's
> mathematical fact then you have the route of proving your disbelief
> mathematically.
What is? You haven't written any proofs let alone theories to support
your claim that anything you're saying here has any shred of truth to
it.
> There are a LOT of little proofs that I've ran through at this point
in
> order to come to my conclusion, many of them extraordinary in terms
of
> what the mathematics shows MUST be true.
... psst why not share your "proofs" with the group?
> For that reason, I can confidently state--before there's an
> implementation that I know of which shows this--that the factoring
> problem has been solved and it's now just a matter of time before the
> implementation demonstrating that is out there.
What are you doing talking on usenet then? Get coding!
> You can debate about it all you want, but like I said earlier today,
> I'm just goofing off, as the hard theoretical work--I think--is done.
Then you're sadly mistaken.
If you want to raise yourself above crankdome [which I doubt you do]
then you would just shut up, write a proper paper, implement the
algorithm and get published. Instead you'll ramble on usenet, accuse
people of wild things and plague the earth.
> In the end, the real world will determine the truth as factoring is
> important in the real world, and your opinions, thoughts or feelings
> have no impact here.
Then why are you sharing them?
> In the meantime, sure, chattering about it can be fun, but it's not
> substantive.
Dude, nothing you produce [at least here] is impactful. If you stopped
posting for a week people would begin to forget you and after a month
you'd be a fading memory in many peoples minds.
People remember Fermat [in this case] because he was capable of
actually respecting others and writing cogent papers/ideas down for
others to read.
You think if Fermat wrote "I can factor, see m = t^2 -j^2 see see I can
factor in polynomial time!!!" that anyone would take him serious?
... posting because I wanted to read TAOCP for a bit ;-)
Tom
- Next message: infobahn: "Re: [Lit.] Buffer overruns"
- Previous message: newstome_at_comcast.net: "Re: [Lit.] Buffer overruns"
- In reply to: jstevh_at_msn.com: "Re: Ultimate check, new way to factor or not?"
- Next in thread: infobahn: "Re: Ultimate check, new way to factor or not?"
- Reply: infobahn: "Re: Ultimate check, new way to factor or not?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
