Список статей

Мы в социальных сетях

       

Неприводимый многочлен

В предыдущей статье были рассмотрены основные понятия теории конечных полей, однако вопрос о том где брать неприводимые полиномы остался без ответа. Эта статья как раз посвящена рассмотрению алгоритмов генерации неприводимых многочленов.

Идея генерации неприводимых полиномов над конечным полем является итеративным процессом. Если заданный порядок неприводимого многочлена \(d = 1\), значит все полиномы этого порядка являются неприводимыми. Если \(d > 1\), то сначала следует сгенерировать все полиномы степени \(d\), которых получится ровно \(2^{d-1}\) (для поля Галуа \(GF(2)\)). Возьмем любой полином \(p \in P\) (порядка \(d\)) из полученного множества и проверим его. Допустим, полином не является неприводимым, тогда существует два полинома \(q_1, q_2\) порядка \(d'\), такого, что \(1 < d' < d \), т.е. \(p = q_1\cdot q_2\). По крайней мере один из них имеет степень \(\dfrac{d}{2}\). Так же можно предположить что один из \(q\) является неприводимым для степени \( < \dfrac{d}{2}\). Итак, для проверки полинома \(p\) достаточно проверить, является ли полином \(q\) неприводимым для полиномов степени, ниже \(\dfrac{d}{2}\).
Пусть полиномы будут представлены в виде целых чисел
Формальный алгоритм:

  • Если \(d = 1\), вернуть список с единицей и нулем
  • Если \(d = 2\), вернуть список с неприводимыми полиномами степени 2 (взять из справочной таблицы)
  • Сгенерировать множество целых чисел от нуля до \(2^{d-1} - 1\), добавив еще один старший разряд (равный единице) к каждому числу, получится полином степени \(d\)
  • Взять i-тый полином \(p_i\) из полученного множества и проверить:
    1. Получить список list неприводимых полиномов степени \(\dfrac{d}{2}\) путем рекурсивного вызова функции
    2. Если \(p_i\) делится без остатка хотя бы на один из полиномов списка list, то он не является неприводимым
    3. Иначе, если \(p_i\) не делится без остатка ни на один из полиномов списка list, то добавляем его в результирующий список resultList
    4. Перейти к проверке следующего полинома (пункт 1)
  • Вернуть результирующий список resultList

Стоить заметить, что в пункте 2 идет проверка степени 2 (список неприводимых полиномов степени 2 можно посмотреть в таблицах), это сделано для большей скорости работы алгоритма, этот пункт можно опустить.
Ниже приведен код алгоритма на псевдо-языке:

function check(p: int, list: List[int]): bool= {
	list.foreach((item: int): bool=> {
		if (t polynomialMod item == 0){
			return false
		}
	})
	return true
}

function generate(d: int): List[int] = {
	if (d == 1) return List[int](1, 0)
	val list2 = List[int](...)	
	if (d == 2) return list2
	// d > 2
	// genereate all polinomials of degree d
	for(i = 0 to 2^(d-1) - 1){
		val t = i & ((2^d)-1)	// polynomial of P set, for testing
		val list = generate(d/2)
		if (check(t, list)) resultList.add(t)
	}
	return resultList
}

Функция \(check\) проверяет, делится ли входной полином \(p\) на любой полином из входящего списка \(list\). Операция \(polynomialMod\) производит взятие остатка от полиномиального деления. Функция \(generate\) генерирует все полиномы порядка \(d\), затем производит проверку на неприводимость используя рекурсивный вызов себя же для генерации неприводимых полиномов меньших порядков.

Нет комментариев



ru |  en