Re: Factoring, sf, and reasonable requests

From: Tim Peters (tim.one_at_comcast.net)
Date: 02/19/05 

Date: Sat, 19 Feb 2005 02:53:56 -0500

[JSH]
> What I did was find a previously unknown factoring method.

Well, until it actually factors reliably, calling it "a factoring method"
seems overly generous. Until then, it's just a system of equations for
which you don't know how to find non-trivial integer solutions efficiently.

Here: given composite M=x*y, with x and y integer and 1 < x <= y < M, there
obviously exists an integer k, 0 <= k < M, such that x+k=y. Then
x*y=x*(x+k), so

    x^2 + k x - M = 0

So all we have to do is find an integer k in range such that

    k^2 + 4M

is a square. Such a k must exist (for example, y-x is a solution).
Candidate divisors of M can then be computed from the quadratic equation.
For example, if M=15, then k=2 gives k^2+4*15 = 64 = 8^2, and the quadratic
equation gives 3 and -5 as divisor of 15. Wow. k=14 gives k^2+4*M = 256 =
16^2, and then the quadratic equation gives 15 and -1 as divisors of 15, so
this method doesn't always give an interesting divisor either.

AFAIK, that's a previously unknown factoring method too. But it's not of
any interest unless I can show that such a k can be found efficiently. I
can't (although I can suggest a lot of tricks to save the trouble of
checking _every_ k in range), and, contrary to what you seem to believe,
correct ideas of no importance are a dime a dozen. You've presented no
evidence to suspect that your equations are more useful than that one, and
computer experiments with your algorithms suggest they're less useful than
that one.

> If mathematicians were what people supposed then they wouldn't be able
> to sit back, and ignore such a major find, making the unreasonable
> request that unless I can factor RSA numbers, it's of no importance.

LOL! *I* think that's an unreasonable request, but *you* were the
chucklehead who posted endless repetitions of claims like:

    now the full solution to the factoring problem is not only known,
    but easily implemented, as the math is childishly simple.

and

    The more elegant solution I'm working on involves just factoring T.
    And it's so elegant it allows a recursive solution, which potentially
    could factor a 4048 bit number on a single pc in a few hours.

and

    Well, if you'd followed my instructions, by now you might be emailing
    RSA.

and

    It's trivial to see that proves a closed form.

    Now then, I say you people are worse than frauds, you are selfish,
    and stupid and willing to let other people suffer for your mistakes
    and failures.

    I say you don't care about the hundreds of billions of dollars
    flowing as we speak around the world dependent on an idea that I've
    shown to be flawed with a couple of quadratics!!!

    And I say that if other people die because of you being frauds then
    you should die with them.

You first -- I don't normally appreciate being called a liar, but you accuse
people of that (& worse) so routinely it's lost all shock value.

I would have been happy if one of your algorithms managed to crack _any_
non-trivial (relative to currently known methods) composite in reasonable
time. Instead your latest method appears to fail to find any factor about
half the time for products of two random 7-digit primes, while those are
easy to factor (and quickly) via many current methods. For example,

M = 23884964307899 = 3448553 * 6926083 j = 11942482153949
ended after 2096640 gcds without finding a factor

When it succeeds, it's rarely something to get excited about. For example,

M = 7070891544373 = 3751357 * 1884889 j = 3535445772187
found factor 1884889 after 6374827 gcds, 5120287 more than random-gcd
   expected to require

_Sometimes_ it beats random-gcd:

M = 9304478594563 = 5849471 * 1590653 j = 4652239297281
found factor 1590653 after 594442 gcds, 656139 less than random-gcd
   expected to require

Unfortunately, factoring failures make it run so slow that it's painful to
set up a proper statistical test to stick a confidence level on whether it's
truly worse than random-gcd when it works.

Worst of all, the larger the composite, the less likely the algorithm is to
find a factor at all (here I'm only using the j you suggested, the smallest
odd integer >= M/2).

So getting a factor is like flipping a coin (in very slow motion ...) for
13-14 digit composites that are no trouble at all to factor by other current
methods, and all evidence suggests the algorithm degenerates to no
appreciable chance of finding a factor for composites of currently
interesting sizes.

So exactly what is there to get excited about here? A correct system of
equations you can't solve? There are millions of those. The trick is in
finding a system that _can_ be solved efficiently. Alas, that likely
requires a fresh insight into the nature of the problem, and one that's
escaped the thousands of serious people who came before you.

[... a few equations, and much bizarre ranting, deleted ...]

Relevant Pages

  • Re: Factoring, sf, and reasonable requests
    ... Well, until it actually factors reliably, calling it "a factoring method" ... I would have been happy if one of your algorithms managed to crack _any_ ... found factor 1884889 after 6374827 gcds, 5120287 more than random-gcd ... Worst of all, the larger the composite, the less likely the algorithm is to ...
    (sci.crypt)
  • Re: JSH: Of course theyre lying
    ... Depending on which iteration of your factoring method you're referring to, the claims have been, variously: ... All of these claims, for their respective "factoring" algorithms, have been fairly well-supported with cohesive mathematical and informal arguments. ... Your responses, on the other hand, have been to repeat things you've already said, to lapse into paranoid ravings, or to drop the thread entirely - not exactly behaviour that will encourage people to listen to you. ... Certainly, your most recent algorithm doesn't factor 15 any faster than trial division, but that's almost meaningless as 15's factors are all in the first three prime numbers. ...
    (sci.math)