Prev: Converting byte[] to ASN1 stream fails - reads until byte 22
Next: Importance of chaos theory
From: Scott Contini on 28 Jul 2010 20:25
On Jul 28, 7:32 pm, Francois Grieu <fgr...(a)gmail.com> wrote:
> Hello,
>
> I'm looking for a software to test if a trinomial or
> pentanomial with coefficients in Z2 is primitive;
> or perhaps, tables of such polynomials, one per
> degree, with some stated selection characteristic
> (preferably: first lexicographically, or equivalently
> smallest value for X=2).
>
> The closest thing that I have located is in the Handbook
> of Applied Cryptography
> <http://www.cacr.math.uwaterloo.ca/hac/>
> specifically Table 4.8
> <http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf>
> but
> - it is not a directly usable software;
> - I's like high confidence in the values;
> - for pentanomials, the selection criteria used is
>   not stated and not the one that I'd like.
>
> Also wanted:
> - proof there exists a primitive pentanomial
>   of degree n for any n>4.
> - extension of these sequences of the Online Encyclopedia
>   of Integer Sequences:
> <http://www.research.att.com/~njas/sequences/A132452>
> <http://www.research.att.com/~njas/sequences/A132450>
> <http://www.research.att.com/~njas/sequences/A132454>
>
> TIA,
>
>   François Grieu

The Magma Computer Algebra package has an online demo page:
http://magma.maths.usyd.edu.au/calc/

For example, type in:

P<x> := PolynomialRing(GF(2));
f := x^7+ x^3 + 1;
IsPrimitive(f);

And then click "Evaluate".

See also:
http://wwwmaths.anu.edu.au/~brent/trinom.html

scott
From: Kristian Gj�steen on 29 Jul 2010 07:02
Francois Grieu <fgrieu(a)gmail.com> wrote:
>On 28/07/2010 12:46, Tom St Denis wrote:
>> Can't you just compute it yourself?
>
>I could. This is nontrivial work, though, and I'm sort of
>hoping to reuse other's code. That happens, I'm told.
>
>> I'm fairly certain HAC has such an algorithm to determine
>> if some polynomial over GF(p^q)[x] is irreducible.
>
>The HAC does contain that: algorithm 4.69, with reference to
>algorithm 2.227 for modular exponentiation on the polynomials,
>and algorithm 2.218 for GCD of polynomials.

If I were to do this, I think that I would probably use Pari-GP
(polisirreducible is useful) or something similar. I usually have more
CPU time than programming time.

>I also need a test that the polynomial is primitive (in
>addition to irreducible). The HAC has algorithm 4.77, which
>itself needs access to the factorization of 2^^n-1. I guess
>there is some analog of the Fermat or Miller-Rabin test to
>quickly reject most non-primitives, but have not found a
>handy reference.

There are reasonably complete tables of factorizations of 2^n-1
(Cunningham project).

A polynomial is primitive iff the image of x in the factor ring has
maximal order. You check for maximal order by verifying that it does
not have smaller order. Knowing that the order must divide 2^n-1,
we do this by trying the maximal proper divisors of 2^n-1. We find the
maximal proper divisors from the factorization of 2^n-1.

Even if you don't have the full factorizations, if you have all the
factors below some reasonable bound (2^80), you can assume that x will
never have very small order, in which case it will be sufficient to test
only the large proper divisors of 2^n-1 (which we know). Obviously,
this approach may fail, but that would be somewhat surprising.

If there aren't any tables of "small" divisors of 2^n-1 available, you
can produce them using elliptic curve factorization. Adjusting the
parameters to be reasonable sure that you have every small factor is
likely to require some thinking.

>Even if I go the "do it from scratch" way, it would be nice
>to cross-reference my results with another source.

--
kg
First  |  Prev  | 
Pages: 1 2
Prev: Converting byte[] to ASN1 stream fails - reads until byte 22
Next: Importance of chaos theory