Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: Long polynomials vs. crypto
Replies: 4   Last Post: May 27, 2012 7:39 AM

 Messages: [ Previous | Next ]
 Joe Snod Posts: 82 Registered: 8/28/10
Re: Long polynomials vs. crypto
Posted: May 27, 2012 3:48 AM

On May 26, 5:35 pm, kg <kristiag+n...@math.ntnu.no> wrote:
> Jim Hammond  <joe.s...@yahoo.com> wrote:
>

> >I've noticed that the problem of factoring a polynomial of arbitrary
> >order seems to involve a lot of the same buzzwords as modern crypto,
> >specifically elliptic curves and lattices, with the latter being, if I
> >understand correctly, a generalization of the period matrices of the
> >former.

>
> >Also, the summation that represents a long integer is almost identical
> >to the one for a long polynomial, except that the polynomial has a
> >variable in the summation, in the same place that the integer has a
> >base, ie

>
> >polynomial = sum from (k=1 to n) of [(a_n)*x^n], where
> >a=coefficients, x=independent variable, n=number of terms

>
> >integer = sum from (k=1 to n) of [(a_n)*b^n], where
> >a="coefficients," b=base, n=number of digits

>
> Factoring polynomials and factoring integers are superficially similar
> problems. But the two algebraic structures are actually very different.
> One example is how we can find square factors in a polynomial by computing
> the gcd of the polynomial and its derivative.
>

> >Does this mean that, if the problem of factoring a polynomial of
> >arbitrarily high order is ever solved, the solution would greatly
> >advance the problem of cracking public key crypto?  If so, how far
> >would it advance the solution?  Would it crack it completely?

>
> Depending a bit on exactly what you mean by factoring a polynomial,

This LLL algorithm is new to me, but for about two years now, I've
been hoping to code the Theta Function method from "Beyond the
Quartic," since I'm committed to closed form. I think I've finally
assembled all the ingredients I need and am ready to start coding.

> Note that there are relations between factoring and polynomial
> factorization, in the sense that being able to factor certain quadratic
> polynomials over certain rings will allow you to factor integers.

Why isn't that a solution to factoring RSA? Can you suggest a
reference on this topic?

Date Subject Author
5/26/12 Joe Snod
5/26/12 Kristian Gjøsteen
5/27/12 Joe Snod
5/27/12 Kristian Gjøsteen
5/27/12 William Elliot