Re: Surrogate factoring works very well

On Mar 19, 6:23 pm, "Joseph Ashwood" <ashw...@xxxxxxx> wrote:
"rossum" <rossu...@xxxxxxxxxxxx> wrote in message

news:71msv29u87u7nt3obsghra6t3kv2vqadkk@xxxxxxxxxx

The code does compile and run once it is all downloaded. It is very
under-commented and at first glance appears over-complex for what it
does. James has included a certain amount of monitoring/timing code
which can presumably be removed for a production version, though he
has not made it easy to do so.

The big questions then:
Does it actually factor numbers?

Yes.

What is the asymptotic speed?

I saw another reply on that issue, but the code is VERY, very rough as
I'm doing research, trying to prove the concept and then worry more
about cleaning things up.

What is the realistic speed for 2Kbit numbers?

Theoretically, it will factor an RSA sized number on a desktop
computer in under ten minutes.

I have mentioned before that my goal for surrogate factoring has been
that benchmark, and the theory says it's achievable.

But right now, it's not doing anything like that, or I wouldn't be
posting about it!!!

Right now I'm trying to figure out why it doesn't do that well, so
far.


The first two are the crux of the claims, the third regards it's usability
(see Primes is in P).

The complaint regarding use of isProbablePrime is moot in my opinion, it
works well enough, and since Primes is in P using a more optimized algorithm
for the sizes is acceptable.
Joe

Um, what I've done is use surrogate factoring to call itself to factor
its own surrogate.

I've mentioned that another route would be to use something else like
the Number Field Sieve to factor the surrogate, as factoring has two
legs, is the way I put it.

BUT, with the small numbers I'm using for testing--I said under
10,000,000--surrogate factoring works damn well.

I had to limit recursion on the self calls as it was getting to be a
bit much, as I had runs where it factored 50,000+ surrogates as it
recursed calling itself--perfectly--just to factor some dinky number,
which seemed more than necessary.

But more importantly, readers curious about whether or not surrogate
factoring can work, who know their way around Java can just download
the source.

I haven't done a release, which would be a jar file anyway, as I'm
still fiddling with it, trying to get something that is a bit cleaner,
and maybe works with bigger numbers, which is about the k/T ratio.

But within a small range, honest researchers can already see that it
does better than random, and can see HOW it works, as the algebra is
trivial, to understand that the theory is for real.

Surrogate factoring is for real.

Last thing, yeah, I'm still talking a bit about it in posts, but as I
solve the practical problems, of course, the code can do all the
demonstrating I need, but make no mistake, the THEORY says that
someone following a different path, like using the NFS to factor the
surrogate, might already be able to factor an RSA sized number, in
minutes, today, right now, as we speak.

That's the theory. I'm in the process of trying to do maybe decades
worth of research in a few months to try and prove to the world this
is for real, as I creatively use surrogate factoring to call itself.

I may succeed quickly, but it may take a while. But I am trying.

But others might just go for the heart of it from the start using
other factoring methods on the surrogate, and factor with two legs--
NFS and surrogate factoring.


James Harris


.

Relevant Pages

  • Re: JSH: Unfair burden
    ... Such a seemingly minor addition is at a fundamental level but despite ... to show it a trivial addition and your community could not. ... I haven't tried surrogate factoring on this - it ...
    (sci.math)
  • Re: surrogate factoring
    ... "surrogate factoring" doesn't really mean anything specific. ... distinct (maybe odd) primes, and you want to find p and/or q. ...
    (sci.math)