Показать сообщение отдельно
Старый 10.02.2011, 10:31   #3
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

Цитата:
Сообщение от phys2010 Посмотреть сообщение
таблицы неприводимых многочленов
Спасибо Но там неприводимые полиномы только для небольших степеней:
для GF(2) до m = 100. У меня до m = 512, хотя и не все подряд степени.
для GF(3) до m = 18. У меня до m = 256, хотя и не все подряд степени.
для GF(5) до m = 12. У меня до m = 128, хотя и не все подряд степени.
для GF(7) до m = 10. У меня до m = 128, хотя и не все подряд степени.
для GF(11) до m = 8. У меня до m = 64, хотя и не все подряд степени.
для GF(13) до m = 8. У меня до m = 64, хотя и не все подряд степени.

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

# Исходный код скриптов поиска неприводимых
# полиномов в математическом пакете Maple v.9

# Составил PavelAR.

p:= 7; m:= 5;

# Поиск примитивных неприводимых трехчленов

res:= 0: c1:= false: c2:= false:
for d1 from 1 to m - 1 while(not(c1 and c2)) do
for k1 from 1 to p - 1 while(not(c1 and c2)) do
for k0 from 1 to p - 1 while(not(c1 and c2)) do
pol:= x^m + k1*x^d1 + k0:
irp:= modp1(ConvertIn(pol,x),p):
c1:= modp1(Irreduc(irp),p):
if c1 then
GFtest:= GF(p,m,pol):
c2:= GFtest[isPrimitiveElement](GFtest[input](p)):
if c2 then res:= GFtest[extension] end if:
end if:
end do:
end do:
end do:
res;

# Поиск примитивных неприводимых четырехчленов

res:= 0: c1:= false: c2:= false:
for d2 from 2 to m - 1 while(not(c1 and c2)) do
for d1 from 1 to d2 - 1 while(not(c1 and c2)) do
for k2 from 1 to p - 1 while(not(c1 and c2)) do
for k1 from 1 to p - 1 while(not(c1 and c2)) do
for k0 from 1 to p - 1 while(not(c1 and c2)) do
pol:= x^m + k2*x^d2 + k1*x^d1 + k0:
irp:= modp1(ConvertIn(pol,x),p):
c1:= modp1(Irreduc(irp),p):
if c1 then
GFtest:= GF(p,m,pol):
c2:= GFtest[isPrimitiveElement](GFtest[input](p)):
if c2 then res:= GFtest[extension] end if:
end if:
end do:
end do:
end do:
end do:
end do:
res;

# Поиск примитивных неприводимых пятичленов

res:= 0: c1:= false: c2:= false:
for d3 from 3 to m - 1 while(not(c1 and c2)) do
for d2 from 2 to d3 - 1 while(not(c1 and c2)) do
for d1 from 1 to d2 - 1 while(not(c1 and c2)) do
for k3 from 1 to p - 1 while(not(c1 and c2)) do
for k2 from 1 to p - 1 while(not(c1 and c2)) do
for k1 from 1 to p - 1 while(not(c1 and c2)) do
for k0 from 1 to p - 1 while(not(c1 and c2)) do
pol:= x^m + k3*x^d3 + k2*x^d2 + k1*x^d1 + k0:
irp:= modp1(ConvertIn(pol,x),p):
c1:= modp1(Irreduc(irp),p):
if c1 then
GFtest:= GF(p,m,pol):
c2:= GFtest[isPrimitiveElement](GFtest[input](p)):
if c2 then res:= GFtest[extension] end if:
end if:
end do:
end do:
end do:
end do:
end do:
end do:
end do:
res;

# Обновленный список найденных на досуге полиномов:

# Примитивные неприводимые многочлены над полем GF(2)

GF(2^2) x^2+x+1
GF(2^3) x^3+x+1
GF(2^4) x^4+x+1
GF(2^5) x^5+x^2+1
GF(2^6) x^6+x+1
GF(2^7) x^7+x^3+1
GF(2^8) x^8+x^4+x^3+x^2+1
GF(2^9) x^9+x^4+1
GF(2^10) x^10+x^3+1
GF(2^11) x^11+x^2+1
GF(2^12) x^12+x^6+x^4+x+1
GF(2^13) x^13+x^4+x^3+x+1
GF(2^14) x^14+x^10+x^6+x+1
GF(2^15) x^15+x+1
GF(2^16) x^16+x^12+x^3+x+1
GF(2^17) x^17+x^3+1
GF(2^18) x^18+x^7+1
GF(2^19) x^19+x^5+x^2+x+1
GF(2^20) x^20+x^3+1
GF(2^21) x^21+x^2+1
GF(2^22) x^22+x+1
GF(2^23) x^23+x^5+1
GF(2^24) x^24+x^7+x^2+x+1
GF(2^25) x^25+x^3+1
GF(2^26) x^26+x^6+x^2+x+1
GF(2^27) x^27+x^5+x^2+x+1
GF(2^28) x^28+x^3+1
GF(2^29) x^29+x^2+1
GF(2^30) x^30+x^23+x^2+x+1
GF(2^31) x^31+x^3+1
GF(2^32) x^32+x^22+x^2+x+1
GF(2^36) x^36+x^11+1
GF(2^40) x^40+x^5+x^4+x^3+1
GF(2^48) x^48+x^9+x^7+x^4+1
GF(2^56) x^56+x^7+x^4+x^2+1
GF(2^64) x^64+x^4+x^3+x+1
GF(2^72) x^72+x^10+x^9+x^3+1
GF(2^80) x^80+x^9+x^4+x^2+1
GF(2^96) x^96+x^10+x^9+x^6+1
GF(2^128) x^128+x^7+x^2+x+1
GF(2^160) x^160+x^5+x^3+x^2+1
GF(2^192) x^192+x^15+x^11+x^5+1
GF(2^256) x^256+x^10+x^5+x^2+1
GF(2^384) x^384+x^16+x^15+x^6+1
GF(2^512) x^512+x^8+x^5+x^2+1

# Примитивные неприводимые многочлены над полем GF(3)

GF(3^2) x^2+x+2
GF(3^3) x^3+2*x+1
GF(3^4) x^4+x+2
GF(3^5) x^5+2*x+1
GF(3^6) x^6+x+2
GF(3^7) x^7+2*x^2+1
GF(3^8) x^8+x^3+2
GF(3^12) x^12+x^5+x+2
GF(3^16) x^16+x^7+2
GF(3^24) x^24+x^13+x^5+2
GF(3^32) x^32+x^5+2
GF(3^48) x^48+x^11+x^6+2*x^4+2
GF(3^64) x^64+x^3+2
GF(3^96) x^96+x^7+x^6+2*x^4+2
GF(3^128) x^128+x^5+2*x^3+x^2+2
GF(3^192) x^192+x^5+2*x^4+x^2+2
GF(3^256) x^256+x^7+2*x^3+x^2+2

# Примитивные неприводимые многочлены над полем GF(5)

GF(5^2) x^2+x+2
GF(5^3) x^3+3*x+2
GF(5^4) x^4+x^2+2*x+2
GF(5^5) x^5+x^2+2
GF(5^6) x^6+x+2
GF(5^7) x^7+3*x+2
GF(5^8) x^8+x^2+2*x+3
GF(5^12) x^12+x^3+2*x+3
GF(5^16) x^16+x^3+3*x+2
GF(5^24) x^24+x^3+2*x^2+2
GF(5^32) x^32+x^5+2*x^3+3
GF(5^48) x^48+x^7+4*x^6+3
GF(5^64) x^64+x^7+2*x^4+2
GF(5^96) x^96+x^3+4*x^2+2
GF(5^128) x^128+x^3+x+3

# Примитивные неприводимые многочлены над полем GF(7)

GF(7^2) x^2+x+3
GF(7^3) x^3+3*x+2
GF(7^4) x^4+x^2+3*x+5
GF(7^5) x^5+x+4
GF(7^6) x^6+x^3+x+5
GF(7^7) x^7+x^4+2
GF(7^8) x^8+x+3
GF(7^12) x^12+x^5+3*x+5
GF(7^16) x^16+2*x+3
GF(7^24) x^24+x^5+6*x+3
GF(7^32) x^32+x^7+3
GF(7^48) x^48+x^5+3*x+5
GF(7^64) x^64+2*x+3
GF(7^96) x^96+x^7+x^3+5
GF(7^128) x^128+x^6+3*x^3+3

# Примитивные неприводимые многочлены над полем GF(11)

GF(11^2) x^2+x+7
GF(11^3) x^3+x+4
GF(11^4) x^4+x+2
GF(11^5) x^5+2*x^2+9
GF(11^6) x^6+x^2+2*x+8
GF(11^7) x^7+x+4
GF(11^8) x^8+x^2+2*x+6
GF(11^12) x^12+x+7
GF(11^16) x^16+x^7+7
GF(11^24) x^24+x+2
GF(11^32) x^32+x^11+7
GF(11^48) x^48+x^11+8
GF(11^64) x^64+x^3+8

# Примитивные неприводимые многочлены над полем GF(13)

GF(13^2) x^2+x+2
GF(13^3) x^3+x+6
GF(13^4) x^4+x^2+x+2
GF(13^5) x^5+3*x^2+2
GF(13^6) x^6+x^2+2*x+2
GF(13^7) x^7+x^4+2
GF(13^8) x^8+x^3+x+2
GF(13^12) x^12+x^2+x+2
GF(13^16) x^16+x^3+6
GF(13^24) x^24+x^2+6*x+2
GF(13^32) x^32+x^4+2*x+11
GF(13^48) x^48+x^2+2*x+6
GF(13^64) x^64+x^3+x+11

Последний раз редактировалось Paul Kellerman; 10.02.2011 в 14:44.
Paul Kellerman вне форума   Ответить с цитированием
Реклама