Re: Factoring with cubic equations?

From: lapin des pyrenees (moc_at_com)
Date: 10/04/03 

Date: Sat, 4 Oct 2003 09:05:15 -0400

the reason we use f(x)=x^2 is not because it's the "quickest non-linear
polynomial ", the real reason is because we are too dumb to derive a quicker
polynomial!

btw, I derived a way to generate all the squares used in the QS method.

Note: I did not say that: given a number N I can tell you the squares x^2
and y^2. All I am saying is that there exist a way to generate all those
squares independently of the corresponding number N to which they relate.

If this result is important,by that I mean ( as a question ) will it make
the search for the squares related to a given number faster if we knew where
to look?
 if it is faster, I will release the way it's done.

le lapin des vosges

"Simon Johnson" <Ckwop@hotmail.com> wrote in message
news:f5668ae7.0310032318.5f5411af@posting.google.com...
> > how can I explain something to someone who already knows everything. I
can't
> >
> > but no, the method applies to any number, no matter how big. the
graphing as
> > you well know is not needed since as you know the cubic can be solved
> > algebraically. I just wanted to show people thru simple examples how the
> > method works.
>
> Bob pretty much qualifies as an expert in the field of factoring as
> far as i'm concerned. I think Bob's point is not that your method
> doesn't work.. it's just that it doesn't work quickly with a
> reasonable amount of memory.
>
> >
> > a lot of people think along the well-known methods of factoring but I
have
> > seen very few that try to come up with something different.
>
> They're is good reason for this.. I'm not an expert in the field but I
> have implemented Pollard Rho for fun and i've looked at the Quadratic
> Sieve and they all appear to try and find values such that:
>
> (x^2) mod n = (y^2) mod n
>
> where x!=y
>
> This is no accident.. If we rearrange the above equation we get:
>
> (x^2-y^2) mod n = 0 mod n
>
> (x+y)(x-y) mod n = 0 mod n
>
> This means that either (x+y) or (x-y) is a multiple of n or a factor
> of n. f(x) = x^2 mod n is the quickest non-linear polynomial to
> evaluate which is probably why we use this polynomial and not some
> other.
>
> I assume the NFS and QS are just faster ways to find x^2 = y^2 mod n
> with the above condition.
>
> > >
> > > Trivially, if we can find a representation
> > > of N as a REDUCIBLE polynomial, then
> > > N is factored. However, finding such a
> > > representation is the essence of the
> > > factoring problem.
> >
> > are you implying that we are missing what the essence of the factoring
> > problem is.
>
> yes.. he is implying that the essence of the problem is not factoring
> n, but factoring n *quickly*.
>
> > > Your required condition that N be small
> > > enough to find the cubic 'graphically' does
> > > not convey confidence in the method.
> > > Factoring small numbers (or finding their
> > > representation as a polynomial) is easy.
> >
> > No, you missed the point. the point was to give people a chance to see
that
> > it works
> > for all numbers, not just the example I gave. the only way to do that is
to
> > let them choose the number but since I have limited resources, I cannot
> > handle big ones but it's irrelevant.
> > it's like saying we have to prove the law of gravity at every point in
this
> > universe before we convince ourselves that the law if universal!
>
> In physics we can't prove that the law of physics here are the same as
> over there with absolute certainty. But in maths we can prove that a
> property does hold for every number. So you should really prove
> strictly that your method works for every integer.
>
> "I can't handle big ones but it's irrelevant"
>
> Cryptography relies on factoring big numbers. You're algorithm is no
> improvement if it can't factor these numbers.
>
> > > 2^701 - 2^351 + 1
>
> Ouch! :P
>
> > >
> >
> > well, if you have the resources, then derive the method and use it for
these
> > numbers. you will then convince yourself and plenty of others that it
works.
> >
> > >
> > > "You can lead a horse's ass to knowledge, but you can't make him
think."
> >
> > how about you disprove the method and show all of us that you really can
> > think and think better than any of us!
>
> You method might work.. i don't dispute that it does.. what i dispute
> is that it is an improvement over faster algorithms :)
>
> Simon.

Relevant Pages

  • Surrogate factoring, correcting sign problems
    ... really don't like an answer for some reason. ... That is, you can find integer Ax from the relation for Az, by factoring ... I talked about algorithms that just checked Ax to see if it has ... It turns out that you can use the Ax to do the difference of squares or ...
    (sci.crypt)
  • Difference of squares, SF
    ... Using a difference of squares you can sometimes factor a target ... After months of discussing surrogate factoring I've yet to hear anyone ... problem so there must be a reason that you wouldn't factor M. ...
    (sci.crypt)
  • Re: JSH: Latest factoring idea is crap
    ... is good enough for top mathematicians, he's got no reason to try to make it ... Since he's attracted to messy methods involving multiple free choices, ... factoring 35 and show him that it didn't find a factor after all. ... Subject: JSH: Now what? ...
    (sci.math)
  • Re: JSH: Contradictory behavior, issue of math fraud
    ... or "spinning straw into gold". ... the mathematical community in the correctness of your algorithm. ... with a viable factoring approach then it stands to reason that they ...
    (sci.math)
  • Re: scott19u.zip
    ... not a good reason to be completely dismissive, ... Ron Rivest estimated that factoring a ... people say they think AES is a secure block cipher it's not on some ... My Crypto code ...
    (sci.crypt)