Re: Public Key, Symbolic Calculation

websnarf_at_gmail.com
Date: 02/09/05 

Date: 8 Feb 2005 21:57:08 -0800

David Wagner wrote:
> >But Abel's statement that there is no deterministic way of
> >factoring polynomials, [...]
>
> Does Abel's theorem really say that? I thought it said that one
> particular method of solving (using radicals) won't work. But what
about
> other methods (e.g., that don't restrict themselves to solely
radicals)?

Uhh ... if you don't express the answer in terms of radicals, then how
were you planning to express the result?

> In fact, I think your claim is wrong; if I recall correctly, I
believe
> it is known that the problem of factoring polynomials over Q is in P.

Ok, now I am cofused. Factor the polynomial in terms of what? If you
want to get approximations to the result, then I agree; in fact I am
fairly sure its O(ln(n)). But this doesn't really help because you get
the results "within epsilon", but I think the point is to come up with
an encoding where you just can't ignore this epsilon -- i.e., that the
essential "private data/key" is *in* that epsilon. Furthermore, I
don't think we are restricting our polynomials to being over Q; you can
see the first example Kiuhnm gave -- even the coefficients would be
expressed in terms of algebraic numbers.

If on the other hand you are saying that *IF* a polynomial is
factorable in terms of radicals, then it can be factored in P, then I
will admit that I don't know if this is true or not. I assumed either
it was not, or it was not known. If its true, then I will agree that
this idea is probably not worth pursuing in this form.

> This is true even for polynomials of degree greater than four, and
true
> even though Abel's theorem says that you can't find the roots of such
> a polynomial just by using radicals. Of course, if you can factor
> a polynomial over Q, you can find all its roots in Q, so here is an
> example where you can do more if you don't restrict yourself to just
> using radicals.

Ok now I really don't follow. The idea (or at least I thought the
idea) is not to product polynomials with roots in Q, but in fact with
algebraic roots (admittedly a tautology -- I mean roots with a
sufficiently complex redical form even when "maximally" simplified.) 

---
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

Relevant Pages

  • Re: Question on algebraic numbers
    ... adjoining to Q the roots of all polynomials over Q. ... extensions of Q which have a solvable Galois group. ... solutions by radicals). ...
    (sci.math)
  • Re: Public Key, Symbolic Calculation
    ... particular method of solving (using radicals) won't work. ... that don't restrict themselves to solely radicals)? ... This is true even for polynomials of degree greater than four, ... even though Abel's theorem says that you can't find the roots of such ...
    (sci.crypt)
  • Re: The incomprehensible work of a precocious mathematician
    ... BY RADICALS. ... Resolved Questions in Mathematics ... ... properties of polynomials ... ... The complexity of resolvent resolved. ...
    (sci.math)
  • Re: The incomprehensible work of a precocious mathematician
    ... BY RADICALS. ... Resolved Questions in Mathematics ... ... properties of polynomials ... ... The complexity of resolvent resolved. ...
    (sci.math)
  • Re: JSH: Keep it simple
    ... arbitrary rule that you take roots of monic polynomials with integer coefficients. ... integral root is divisible by something that is coprime to ... Your claim regarding rational roots of this polynomial cannot do that, since the standard theory makes no claims regarding common factors among such roots. ...
    (sci.math)