Prev: Converting byte[] to ASN1 stream fails - reads until byte 22
Next: Importance of chaos theory
From: Francois Grieu on 28 Jul 2010 05:32
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
From: Tom St Denis on 28 Jul 2010 06:46
On Jul 28, 5:32 am, 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

Can't you just compute it yourself? I'm fairly certain HAC has such
an algorithm to determine if some polynomial over GF(p^q)[x] is
irreducible.

Tom
From: Francois Grieu on 28 Jul 2010 07:08
On 28/07/2010 12:46, Tom St Denis wrote:
> On Jul 28, 5:32 am, Francois Grieu <fgrieu(a)gmail.com> wrote:
>> 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>

>
> 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.

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.

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


Francois Grieu
From: Thomas Pornin on 28 Jul 2010 09:44
According to Francois Grieu <fgrieu(a)gmail.com>:
> Also wanted:
> - proof there exists a primitive pentanomial
> of degree n for any n>4.

According to this article from HP-Labs in 1998:
http://www.hpl.hp.com/techreports/98/HPL-98-135.pdf
it is not really known whether there are _irreducible_ pentanomials
of degree n for all n>4. Since primitive polynomials are irreducible,
the proof you are looking for may be a bit hard to find...

As for testing whether a given irreducible polynomial is primitive,
I think there is no known general method faster than the one which
implies factoring 2^n-1. Of course, for some values of n, this can
be quite fast, especially the n such that 2^n-1 is prime.


As for software: here is below a C program I wrote once. It enumerates
the irreducible polynomials of degree n (3 <= n <= 63) and tests each of
them for primitivity. Of course, enumerating all those polynomials for
large values of n takes inordinate amounts of time... but you can
extract the irreducibility and primitivity test functions and use them
in loops which enumerates trinomials and pentanomials in any order that
you see fit.


--Thomas Pornin

/*
* Enumerate irreducible polynomials in Z2[X].
*
* Compile with DEGREE defined to the required polynomial degree. This
* value must lie between 3 and 63 (inclusive).
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#ifndef DEGREE
#define DEGREE 5
#endif

#define N (DEGREE + 1)

#if N < 4 || N > 64
#error DEGREE is out of range
#endif

/* ====================================================================== */

/*
* Print a polynomial.
*/
static void
print2(uint64_t x)
{
int i, f;

for (i = N - 1, f = 0; i >= 0; i --) {
if (!(x & ((uint64_t)1 << i)))
continue;
if (f) {
fputs(" + ", stdout);
} else {
f = 1;
}
if (i == 0) {
putchar('1');
} else if (i == 1) {
putchar('X');
} else {
printf("X^%d", i);
}
}
}

/*
* Get the bit length of the provided number. 0 has bit length 0.
*/
static int
bitlen(uint64_t x)
{
int b;
uint32_t y;

y = (x >> 32);
if (y != 0) {
b = 32;
} else {
y = (uint32_t)x;
b = 0;
}
if (y > 0x0000FFFF) { y >>= 16; b += 16; }
if (y > 0x000000FF) { y >>= 8; b += 8; }
if (y > 0x0000000F) { y >>= 4; b += 4; }
if (y > 0x00000003) { y >>= 2; b += 2; }
if (y > 0x00000001) { y >>= 1; b ++; }
if (y > 0x00000000) { b ++; }
return b;
}

/*
* Reduce polynomial a modulo polynomial b.
*/
static uint64_t
mod2(uint64_t a, uint64_t b)
{
int an = bitlen(a), bn = bitlen(b), i;

if (bn > an) {
return a;
}
b <<= an - bn;
for (i = an - bn; i >= 0; i --, b >>= 1) {
if (a & ((uint64_t)1 << (i + bn - 1)))
a ^= b;
}
return a;
}

/*
* Compute GCD of two polynomials.
*/
static uint64_t
gcd2(uint64_t a, uint64_t b)
{
while (b != 0) {
uint64_t t = mod2(a, b);

a = b;
b = t;
}
return a;
}

/*
* Mutiply polynomial z by X modulo m (of degree mn-1)
*/
static uint64_t
mulx2(uint64_t z, uint64_t m, int mn)
{
z <<= 1;
if (z & ((uint64_t)1 << (mn - 1)))
z ^= m;
return z;
}

/*
* Multiply two polynomials modulo m (of degree mn-1)
*/
static uint64_t
mul2(uint64_t a, uint64_t b, uint64_t m, int mn)
{
uint64_t u = a, v = 0U;
int i, bn = bitlen(b);

for (i = 0; i < bn; i ++) {
if (b & ((uint64_t)1 << i))
v ^= u;
u = mulx2(u, m, mn);
}
return v;
}

/*
* Compute a^e modulo m of degree mn-1
*/
static uint64_t
pexp2(uint64_t a, uint64_t e, uint64_t m, int mn)
{
uint64_t u = a, v = 1;

while (e > 0) {
if (e & (uint64_t)1)
v = mul2(v, u, m, mn);
u = mul2(u, u, m, mn);
e >>= 1;
}
return v;
}

/*
* Check whether the provided polynomial is irreducible.
*/
static int
irred2(uint64_t f)
{
uint64_t u = 2;
int i, fn;

fn = bitlen(f);
for (i = 0; i < (fn - 1) / 2; i ++) {
u = mul2(u, u, f, fn);
if (gcd2(f, u ^ 2) != 1)
return 0;
}
return 1;
}

/*
* These are the prime factors of 2^n-1 for n ranging from 0 to 63
* (without multiplicity).
*/
static uint64_t ofactors2[][11] = {
{ 0 },
{ 0 },
{ 3 },
{ 7 },
{ 3, 5 },
{ 31 },
{ 3, 7 },
{ 127 },
{ 3, 5, 17 },
{ 7, 73 },
{ 3, 11, 31 },
{ 23, 89 },
{ 3, 5, 7, 13 },
{ 8191 },
{ 3, 43, 127 },
{ 7, 31, 151 },
{ 3, 5, 17, 257 },
{ 131071 },
{ 3, 7, 19, 73 },
{ 524287 },
{ 3, 5, 11, 31, 41 },
{ 7, 127, 337 },
{ 3, 23, 89, 683 },
{ 47, 178481 },
{ 3, 5, 7, 13, 17, 241 },
{ 31, 601, 1801 },
{ 3, 2731, 8191 },
{ 7, 73, 262657 },
{ 3, 5, 29, 43, 113, 127 },
{ 233, 1103, 2089 },
{ 3, 7, 11, 31, 151, 331 },
{ 2147483647 },
{ 3, 5, 17, 257, 65537 },
{ 7, 23, 89, 599479 },
{ 3, 43691, 131071 },
{ 31, 71, 127, 122921 },
{ 3, 5, 7, 13, 19, 37, 73, 109 },
{ 223, 616318177 },
{ 3, 174763, 524287 },
{ 7, 79, 8191, 121369 },
{ 3, 5, 11, 17, 31, 41, 61681 },
{ 13367, 164511353 },
{ 3, 7, 43, 127, 337, 5419 },
{ 431, 9719, 2099863 },
{ 3, 5, 23, 89, 397, 683, 2113 },
{ 7, 31, 73, 151, 631, 23311 },
{ 3, 47, 178481, 2796203 },
{ 2351, 4513, 13264529 },
{ 3, 5, 7, 13, 17, 97, 241, 257, 673 },
{ 127, 4432676798593 },
{ 3, 11, 31, 251, 601, 1801, 4051 },
{ 7, 103, 2143, 11119, 131071 },
{ 3, 5, 53, 157, 1613, 2731, 8191 },
{ 6361, 69431, 20394401 },
{ 3, 7, 19, 73, 87211, 262657 },
{ 23, 31, 89, 881, 3191, 201961 },
{ 3, 5, 17, 29, 43, 113, 127, 15790321 },
{ 7, 32377, 524287, 1212847 },
{ 3, 59, 233, 1103, 2089, 3033169 },
{ 179951, 3203431780337 },
{ 3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321 },
{ 2305843009213693951 },
{ 3, 715827883, 2147483647 },
{ 7, 73, 127, 337, 92737, 649657 }
};

/*
* Check if f is primitive. This must be called only if f is known
* to be irreducible.
*/
static int
primitive2(uint64_t f)
{
int i, fn = bitlen(f);
uint64_t go = ((uint64_t)1 << (fn - 1)) - 1;

#if 0
if (!irred2(f))
return 0;
#endif
for (i = 0; ofactors2[fn - 1][i] != 0; i ++) {
uint64_t e = go / ofactors2[fn - 1][i];

if (e == 1)
return 1;
if (pexp2(2U, e, f, fn) == 1U)
return 0;
}
return 1;
}

/* ====================================================================== */

int
main(void)
{
uint64_t u;

for (u = (uint64_t)1 << (N - 2); u < ((uint64_t)1 << (N - 1)); u ++) {
uint64_t p = (u << 1) | (uint64_t)1;

if (irred2(p)) {
print2(p);
if (primitive2(p)) {
printf(" (primitive)\n");
} else {
printf("\n");
}
}
}
return 0;
}
From: Francois Grieu on 28 Jul 2010 10:39
On 28/07/2010 15:44, Thomas Pornin wrote:
> According to Francois Grieu <fgrieu(a)gmail.com>:
>> Also wanted:
>> - proof there exists a primitive pentanomial
>> of degree n for any n>4.
>
> According to this article from HP-Labs in 1998:
> http://www.hpl.hp.com/techreports/98/HPL-98-135.pdf

A useful reference.

> it is not really known whether there are _irreducible_ pentanomials
> of degree n for all n>4. Since primitive polynomials are irreducible,
> the proof you are looking for may be a bit hard to find...

Indeed.

> As for testing whether a given irreducible polynomial is primitive,
> I think there is no known general method faster than the one which
> implies factoring 2^n-1. Of course, for some values of n, this can
> be quite fast, especially the n such that 2^n-1 is prime.

Perhaps there is also a probabilistic methods analog to Fermat or
Miller-Rabin test, but I failed to find an exposition.

> As for software: here is below a C program I wrote once. It enumerates
> the irreducible polynomials of degree n (3 <= n <= 63) and tests each of
> them for primitivity. Of course, enumerating all those polynomials for
> large values of n takes inordinate amounts of time... but you can
> extract the irreducibility and primitivity test functions and use them
> in loops which enumerates trinomials and pentanomials in any order that
> you see fit.

Compiled and worked on first try. I love C. With minor changes, this
will solve my problem up to n=63. I had like a few hundreds in mind,
but still that's very useful: I have something to start from and
compare against.

Many thanks.

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