Re: Public Key, Symbolic Calculation

websnarf_at_gmail.com
Date: 02/10/05 

Date: 9 Feb 2005 17:43:05 -0800

David Wagner wrote:
> [...] I take it from your questions that you're not familiar with
> this part of the literature.

You are correct, I just did a bunch of googling -- I had actually heard
of the Berlekemp method, but thought it was only a probabilistic
method, and was not aware that it has been extended to all of Z.

But the extension Z, if I understand correctly is done by repeating
Berlekemp's method for increasing n in mod p^n, until a modular factor
is found that is also a real factor (or something similar to that.)
And the fact that this extends to Q is just a side effect of the fact
that polynomials with coefficients in Q are really the same as
polynomials with coefficients in Z. So this is all still boot-strapped
from the fact that the field we are working in is built up from finite
fields.

But the algebraics over Z are not a finite field, and I don't think you
can build them up from finite fields can they? And if not, is the idea
still dead?

> [...] If you are going to work on this problem, I consider
> it essential background.

I'm not a serious enough mathematician to go to that level of study of
the problem. It seemed like an idea worth flushing out to me, its just
that Kiuhnm was really expressing it badly (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).

> [...] There are some beautiful algorithms here; well worth studying!

Yes, unfortunately its all written in Mathematicianese. I mean
Pollard-Rho is an extremely trivial thing to understand, if only it is
explained by someone who isn't a professional mathematician. (Did you
know there are ways of implementing it in O(1) storage? Something not
easily sussed out while its trapped in ivory towers.) And I'm sure I
would "get" this Berlekemp method, if it were written more clearly. 

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

Relevant Pages

  • Re: Looking for algorithm
    ... > sequence of C's as your checksum.) ... My pitiful finite field knowledge is being sorely tested, ... I've used PARI/GP to test a few polynomials, to see how well I understood ... For example for ring operations I use "modulo the polynomial ...
    (sci.crypt)
  • Re: Properties of polynomials over finite fields
    ... > multivariate polynomials over a finite field F in their proofs. ... > from the affine space F^k to the field F and make various claims about ...
    (sci.math.research)
  • Re: Nomenclature question
    ... >However I am not sure that the context really resolves this. ... >Hence, for example, there are six second order polynomials that do not ... I still do not like the wording. ... Suppose we have a finite field F, a finite extension field E of F, ...
    (sci.crypt)
  • Re: Properties of polynomials over finite fields
    ... tim_ptacek@pobox.com (Tim Ptacek) wrote: ... > multivariate polynomials over a finite field F in their proofs. ...
    (sci.math)