Re: Surrogate factoring, basic algorithm
jstevh_at_msn.com
Date: 02/22/05
- Next message: Bryan Olson: "Re: Adversarial Testing, was Re: Thou shalt have no"
- Previous message: Bryan Olson: "Re: To what degree has it been "broken"?"
- In reply to: Tim Peters: "Re: Surrogate factoring, basic algorithm"
- Next in thread: jstevh_at_msn.com: "Re: Surrogate factoring, basic algorithm"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 21 Feb 2005 17:08:00 -0800
Tim Peters wrote:
> [Décio]
> >> Would you please spell out an algorithm so I can implement it and
> >> check your assertion?
>
> [JSH]
> > Well, to not be paranoid, I guess I may as well.
> >
> > Find a j close to M, which minimizes T, and seems to work better
for
> > some unknown to me reason, and find an *even* j, which I know
> > contradicts what I said before, but it works a lot faster from what
I'm
> > seeing.
>
> It's at least interesting that it appears to be much easier to find
small
> non-factoring cases for this algorithm than for previous ones
specified
> here. I'll illustrate my understanding with M=35 and j=6 (the
smallest odd
> composite M that's not the square of a prime that fails to factor at
some j,
> according to my implementation).
>
That's somewhat interesting, though it IS possible that if you fully
calculate y, and then solve for x, that you might find a factorization
for some j.
I don't find that terribly interesting, but in the interest of
completeness thought I should toss it out.
Remember y, comes in with
yx^2 + Ax - M^2 = 0
and
yz^2 + Az - j^2 = 0
and actually I calculate y/A^2, again going with A not being important.
It IS possible that for some cases both the numerator and denominator
of y are coprime to M, but x gives a single prime factor.
I didn't want to complicate the algorithm, as in my opinion, that small
possibility isn't worth chasing down.
James Harris
- Next message: Bryan Olson: "Re: Adversarial Testing, was Re: Thou shalt have no"
- Previous message: Bryan Olson: "Re: To what degree has it been "broken"?"
- In reply to: Tim Peters: "Re: Surrogate factoring, basic algorithm"
- Next in thread: jstevh_at_msn.com: "Re: Surrogate factoring, basic algorithm"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
