Re: Basically a sieve method, relation to quantum

jstevh_at_msn.com
Date: 01/24/05 

Date: 24 Jan 2005 14:53:32 -0800

Tim Peters wrote:
> [jstevh@msn.com]
> >>> The original algorithm in my program, will, my current analysis
shows,
> >>> factor about 50% of the time, which is astounding.
>
> [nospamplz@example.com]
> >> Wouldn't trial and error division find the factors 100% of the
time?
> >> Now it might take a while (maybe longer than the universe takes to
> >> reach heat-death) but the question is whether your algorithm would
be
> >> faster or not.
>
>
> [Dik T. Winter]
> > In a little test I tried: slower. I tried to factor
137305167623353 with
> > trial division (and not trial division by primes only, but by *all*
> > odd numbers until the square root). It took my simple program
about 2
> > seconds on this old Sun machine. Apparently JSH's program was in
the
> > minutes range.
>
> In fairness <heh>, JSH only claims his method is fast in this case if
it's
> *given* a complete factorization of 18852709056077064918470962609 -
j^2 for
> some integer j first (presumably j != 0 -- it's never clear what
assumptions
> he's making; btw, 188... is the square of your 137...).

Speed isn't the issue with the prototype program which is a proof of
concept.

Basically I came up with the theory last December, and wrote a paper.

The paper shows theoretically that I solved the factoring problem.

My initial implementation first off was meant to test the equations and
verify that I actually got factorizations.

I did.

However, I didn't get 100% factorization which I assumed I would get,
and hitting a wall as to why, I ended up talking about this publicly as
I worked out the theory.

Ok, now to the rest of this post...

> So let's give him one: 137305167623353^2 - 11^2 =
> 18852709056077064918470962488 = 2 * 2 * 2 * 3 * 13 * 13 * 23 * 79 *
853 *
> 3450977 * 869020048249.
>

Ok, here you can now take the factors of T, and plug them into my
algorithm, to pull out a factorization of the target.

I'm not going to do that with the numbers above, as the program isn't
set up that way, and I'm not interested in doing things for Usenet
posters as so many of you are buttheads.

> I couldn't make sense of what he thinks he's doing beyond that point.
Ok.

James Harris

Relevant Pages

  • Re: Polynomial time factoring algorithm?
    ... But what if S is your target composite to be factored? ... from working, like if S is odd then T must be odd, and f_1 and f_2 ... non-trivial factorization of your target composite S. ... factoring congruences. ...
    (sci.crypt)
  • SF: Simpler derivation
    ... so multiplying the second by r^2, ... Notice here you can also see why j and M need to be odd, ... it does not, and you do a single pass and don't get a factorization, ... significant powers of 2. ...
    (sci.math)
  • SF: Simpler derivation
    ... so multiplying the second by r^2, ... Notice here you can also see why j and M need to be odd, ... it does not, and you do a single pass and don't get a factorization, ... significant powers of 2. ...
    (sci.crypt)
  • Re: Reality check, surrogate factoring
    ... Like typically j is odd, as M is odd (though you may need to ... James picks an arbitrary j ... A good starting point is to use the factorization ... Of course, since we're in the realm of the rationals, "factor" is ...
    (sci.crypt)
  • Re: Reality check, surrogate factoring
    ... Like typically j is odd, as M is odd (though you may need to ... James picks an arbitrary j ... A good starting point is to use the factorization ... Of course, since we're in the realm of the rationals, "factor" is ...
    (sci.math)