Re: Ultimate check, new way to factor or not?

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 01/27/05 

Date: 26 Jan 2005 17:53:48 -0800

In article <1106787329.830488.269890@c13g2000cwb.googlegroups.com>,
 <jstevh@msn.com> wrote:
>Did I find a new way to factor or not?

You seem to have found a way to factor. I don't
know whether it is a new way or not.

But, you know, a new *inefficient* way to factor
simply isn't interesting. What you haven't done is
demonstrate your repeated claim that it is
polynomial time. Since it can only increase the
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
method cannot be polynomial time. Now, if it's
subexponential, it could still be interesting, but
you haven't argued for that, either.

It seems to me that it all boils down to just how
easy it is to factor a random large number, or
more precisely, given many large numbers in a
given range (spread out just below M^2), what is
the chance that at least one of them will be
completely factorizable by trial division. This
is, by the way, called "smoothness" and underlies
methods like the quadratic sieve. Which is why I'm
not sure if your method is new, or not... it might
just be a special case of the quadratic sieve. I'm
not expert enough to comment on that.

>If I did not, then if you're a reasonable person you should require
>that someone PROVE I did not.

I disagree. Why should I or anyone else have to
prove you wrong, when it's your job to prove that
you're right? That's what "burden of proof" is all
about.

[snip]
>And they will ignore my recent research, like they're already doing as
>I've been talking about this for a while, and I contacted
>mathematicians in the field by email, and they will not be able to give
>you a reasonable answer why.

I can tell you why. It's because professionals get
paid to do what they do, and you're asking them
for free work. Try getting your backyard
landscaped that way, and see what happens. (I just
tried. They laughed at me. :-)

>Should a find of a new way to factor be acknowledged by mainstream
>mathematicians?

That depends. There are two criteria: newness and
"interestingness". If you present them with a
valid proof that the method works (which you may
have done, but I haven't seen it), you then need
to go on and show that it's interesting. This
requires proving a polynomial or good
subexponential running time. You certainly haven't
done that.

Until you show that the method is interesting, why
is anyone obligated to spend any of their precious
time doing anything at all with it?

Here's an example of what I mean. I once invented
a new (to me) factoring algorithm. It turns out
that efficient methods of factoring polynomials
exist. So, take the number to be factored M, and a
small integer x, and express M = P(x). Factor P(x)
using the polynomial factoring algorithm,
P(x)=a(x).b(x). Now a(x), evaluated with the
actual small integer used, must be a factor of M.
This algorithm works, and is trivial to prove.
However, what I missed was the fact that P(x) is
almost always irreducible. You have no good way of
choosing an x that will work. (To this day, I
still don't even know that such an "x" exists for
for an arbitrary composite M.) What I do know is
that the probability of hitting on such an x is so
low that the method is too slow to be of
interest, once you try out lots of values for x.

Do you acknowledge my new factoring method? Should
other mathematicians? I don't expect them to.

Greg. 

-- 
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au

Relevant Pages

  • Re: JSH: Contradictory behavior, issue of math fraud
    ... that is a polynomial time rather than an exponential time ... If practicality is all that matters then acknowledge that "pure math" ... Let's say that down the line someone proves that surrogate factoring ...
    (sci.math)
  • Re: JSH: Nearly done
    ... my response to your "polynomial time" below.) ... algorithms really are, so I'll tell you: For a factoring algorithm to ... it doesn't hurt to use recursion in a "proof of concept" ...
    (sci.math)
  • Re: Ultimate check, new way to factor or not?
    ... > polynomial time. ... Now, factoring is in general hard, with *certain* types of numbers, ... the mathematics or what's possible, but only in trying to dismiss my ... while certain key features of my discovery make it very exciting, ...
    (sci.crypt)
  • Re: A factoring algorithm
    ... > I have a new factoring algorithm which seems to be very fast with ... Your post lacks specifics. ... then this factorization is readily found in polynomial time ...
    (sci.crypt)
  • Re: Quantum Computers breaking ciphers
    ... > is a factor in polynomial time. ... The factoring algorithm is the thing that /gives/ you the candidate. ... They no longer do my traditional winks tournament lunch - liver and bacon. ...
    (sci.crypt)