Re: Public Key, Symbolic Calculation

From: Kristian Gjøsteen (kristiag+news_at_item.ntnu.no)
Date: 02/10/05 

Date: Thu, 10 Feb 2005 08:33:48 +0000 (UTC)

 <websnarf@gmail.com> wrote:
> So this is all still boot-strapped
>from the fact that the field we are working in is built up from finite
>fields.

What does this mean? Q is built up from finite fields? That does not
make sense.

>And if not, is the idea
>still dead?

For what it's worth: I spent five minutes googling factoring
polynomials over algebraic number fields, and I found a paper's
suggesting that factoring over algebraic number fields is easy.
But I cannot confidently say that this kills the idea.

So ignore that for a moment. Why shouldn't the following work to
kill the original proposal:

1. Find the complex roots of the public key polynomial.

2. Insert those roots into the ciphertext polynomial, and
        interpolate to get a complex approximation of the
        message polynomial.

3. Find the algebraic integers corresponding to the message
        polynomial coefficients.

Step 1 and 2 are obviously easy, and can be done efficiently to
arbitrary precision.

I have a vague feeling that Step 3 is easy, and that sufficient clues
have already appeared in this thread.

Now I do not have time to research this, so that should be left to
the interested reader, but the problem is: Given a complex approximation
of an algebraic number given, find the algebraic number.

>(he also didn't response to
>my query about whether or not the sample polynomial he showed is
>factorable using Maple -- I just assumed it wasn't and that he was
>using that to motivate his idea).

Just punching it into Maple doesn't give you a factorisation. You
probably need to tell Maple which field the roots are in, and I'm
not sufficiently familiar with Maple to do that.

Relevant Pages

  • Re: Attilla Bass, any info appreciated
    ... I just got my hands on an Attilla bass ... ... built by Attilla Balogh ... maple body, ... a nice solid hunk of maple with what seems to be pretty nice pickups ...
    (alt.guitar.bass)
  • Re: Factoring problem, solved
    ... I'm sure you wouldn't say it's safe to ignore every other factoring ... around to build an atomic bomb long before one got built. ... they had a *theory* and reasons to believe an atom bomb ... It's like having the physics behind building an atom bomb. ...
    (sci.math)
  • Re: Factoring problem, solved
    ... I'm sure you wouldn't say it's safe to ignore every other factoring ... around to build an atomic bomb long before one got built. ... they had a *theory* and reasons to believe an atom bomb ... It's like having the physics behind building an atom bomb. ...
    (sci.crypt)
  • Re: Surrogate factoring approach, analysis
    ... I wrote a prototype test program to test out my new factoring method. ... And you really can't be as stupid as you're playing here, ...
    (sci.math)
  • Re: Surrogate factoring approach, analysis
    ... I wrote a prototype test program to test out my new factoring method. ... And you really can't be as stupid as you're playing here, ...
    (sci.crypt)