Re: Re: Polynôme générateur

According to Michelot  <mhostettler@voila.fr>:
> Une question, est-il facile en observant la structure f(X) d'un
> polynôme, de déterminer s'il est primitif ou pas ?

Il faut d'abord déterminer s'il est irréductible. Ça ne se voit pas
"à l'oeil" mais c'est algorithmiquement assez aisé. Ensuite, pour
déterminer s'il est primitif, il faut faire quelques exponentiations.
Par exemple, pour n = 11 et un polynôme irréductible, le groupe des
inversibles a pour cardinal 2047. Le groupe engendré par X a un
cardinal qui divise donc 2047 ; c'est donc 2047 lui-même (auquel cas
le polynôme est primitif), ou alors un des diviseurs stricts de 2047,
i.e. 23 et 89.

Du coup, il suffit de calculer X^23 et X^89 modulo le polynôme, pour
voir si ça donne 1 ou pas. Si aucune des deux exponentiations ne donne
1, alors l'ordre de X n'est ni 23, ni 89 ; c'est donc 2047.

Là encore, algorithmiquement, c'est facile, sous réserve d'avoir
une factorisation de 2^n-1 (ce qui n'est pas un vrai problème pour
les n de moins de 150).


Alors à la main, bof. Mais je me suis fait un petit programme pour ça,
il y a quelques temps. Le voilà :


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

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

#ifndef DEGREE
#define DEGREE    11
#endif

#define N   (DEGREE + 1)

#if N < 4 || N > 20 || (UINT_MAX >> (N - 1)) == 0
#error DEGREE is out of range
#endif

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

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

	for (i = N - 1, f = 0; i >= 0; i --) {
		if (!(x & (1U << 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(unsigned x)
{
	int b = 0;

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

/*
 * Reduce polynomial a modulo polynomial b.
 */
static unsigned
mod2(unsigned a, unsigned 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 & (1U << (i + bn - 1)))
			a ^= b;
	}
	return a;
}

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

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

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

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

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

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

	while (e > 0) {
		if (e & 1U)
			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(unsigned f)
{
	unsigned u = 2U;
	int i, fn;

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

/*
 * These are the prime factors of 2^n-1 for n ranging from 0 to 20
 * (without multiplicity).
 */
static unsigned ofactors2[][6] = {
	{ 0, 0, 0, 0, 0, 0 },
	{ 0, 0, 0, 0, 0, 0 },
	{ 3, 0, 0, 0, 0, 0 },
	{ 7, 0, 0, 0, 0, 0 },
	{ 3, 5, 0, 0, 0, 0 },
	{ 31, 0, 0, 0, 0, 0 },
	{ 3, 7, 0, 0, 0, 0 },
	{ 127, 0, 0, 0, 0, 0 },
	{ 3, 5, 17, 0, 0, 0 },
	{ 7, 73, 0, 0, 0, 0 },
	{ 3, 11, 31, 0, 0, 0 },
	{ 23, 89, 0, 0, 0, 0 },
	{ 3, 5, 7, 13, 0, 0 },
	{ 8191, 0, 0, 0, 0, 0 },
	{ 3, 43, 127, 0, 0, 0 },
	{ 7, 31, 151, 0, 0, 0 },
	{ 3, 5, 17, 257, 0, 0 },
	{ 131071, 0, 0, 0, 0, 0 },
	{ 3, 7, 19, 73, 0, 0 },
	{ 524287, 0, 0, 0, 0, 0 },
	{ 3, 5, 11, 31, 41, 0 }
};

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

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

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

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

int
main(void)
{
	unsigned u;

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

		if (irred2(p)) {
			print2(p);
			if (primitive2(p))
				printf(" (primitive)\n");
			else
				printf("\n");
		}
	}
	return 0;
}