原始多項式の求め方

９段M系列の生成多項式となる原始多項式の求め方を教えてください。

今のところx^9+x^5+1やx^9+x^4+1が原始多項式であることがネットなどを調べていてわかりましたが、求め方はわかりません。
また、上記の２式が原始多項式であるかどうか判別するようなこともできるのでしょうか？

数学に関しては素人なので"何を勉強すればわかるか"だけでも教えていただけると助かります。

よろしくお願いします。

No.1 回答者： reiman 回答日時： 2009/07/30 06:47

位数2の素数体を係数とする9次多項式f(x)が原始多項式である条件:

（１）f(x)が規約多項式であること。
（２）x^31をf(x)で割ったあまりが1でないこと。

解説：
（１）はいうまでもない。
（２）によって
1=x^0,x=x^1,x^2,x^3,x^4,...,x^(2^10-2)
をf(x)で割った余りがすべて異なることが保証される。

注）2^10-1=3x11x31

No.2 回答者： reiman 回答日時： 2009/07/30 08:34

変換ミス：規約多項式→既約多項式

位数2の素数体を係数とする9次多項式f(x)が原始多項式である条件:
（１）f(x)が既約多項式であること。
（２）x^31をf(x)で割ったあまりが1でないこと。

解説：
（１）はいうまでもない。
（２）によって
1=x^0,x=x^1,x^2,x^3,x^4,...,x^(2^10-2)=x^1022
をf(x)で割った余りがすべて異なることが保証される。

この回答へのお礼

ご回答ありがとうございます。

「（２）x^31をf(x)で割ったあまりが1でないこと。」
はなぜx^31なのでしょうか？どう意味があるのですか？？

お礼日時：2009/07/30 20:14

No.3 回答者： reiman 回答日時： 2009/07/30 21:48

多項式をn-1次既約多項式g(x)で割った余りが同一のものを同一視するという多項式の集合を考えるとそれは位数2^nの有限体（ガロア体GF(2^n)）になる。

そしてGF(2^n)-{0}は乗法について有限群になる。
xのべき乗で生成される巡回群GはGF(2^n)-{0}の部分群なのでその位数
はGF(2^n)-{0}の位数2^n-1を割り切る。
もしg(f)が原始多項式でないならばGの位数は2^n-1以外の2^n-1の約数である。
従ってGの位数が「√(2^n-1)を上回らない2^n-1の最大の約数」の約数でなければg(x)は原始多項式ということになる。

n=10の場合：
「√(2^10-1)を上回らない2^10-1の最大の約数」は31なのでGの位数が31の約数でなければg(x)は原始多項式ということになる。
x^31をg(x)で割った余りが1でないならばGの位数は√(2^10-1)を越えることになり同時にGの位数は2^10-1の約数であるからGの位数は2^10-1=1023ということになりg(x)は原始多項式ということになる。

No.4 回答者： reiman 回答日時： 2009/07/30 22:22

間違いが有ったので修正

多項式をn-1次既約多項式g(x)で割った余りが同一のものを同一視するという多項式の集合を考えるとそれは位数2^nの有限体（ガロア体GF(2^n)）になる。
そしてGF(2^n)-{0}は乗法について有限群になる。
xのべき乗で生成される巡回群GはGF(2^n)-{0}の部分群なのでその位数
はGF(2^n)-{0}の位数2^n-1を割り切る。
もしg(x)が原始多項式でないならばGの位数は2^n-1以外の2^n-1の約数である。
従ってGの位数が「2^n-1でない2^n-1の最大の約数」の約数でなければg(x)は原始多項式ということになる。

n=10の場合：
「2^10-1でない2^10-1の最大の約数」は341なのでGの位数が341の約数でなければg(x)は原始多項式ということになる。
x^341をg(x)で割った余りが1でないならばGの位数は341を越えることになり同時にGの位数は2^10-1の約数であるからGの位数は2^10-1=1023ということになりg(x)は原始多項式ということになる。


従ってNo1,No2,No3は間違いで原始多項式の条件は

9次多項式f(x)が原始多項式である条件：
（１）既約多項式であること。
（２）x^341をf(x)で割った余りが1でないこと。

でした。

No.5 回答者： reiman 回答日時： 2009/07/31 17:51

またまた間違いが有ったので修正（n-1とnの取り違えと他にも）

多項式をn次既約多項式g(x)で割った余りが同一のものを同一視するという多項式の集合を考えるとそれは位数2^nの有限体（ガロア体GF(2^n)）になる。
そしてGF(2^n)-{0}は乗法について有限群になる。
前記有限体上においてxのべき乗からなる巡回群GはGF(2^n)-{0}の部分群なのでその位数はGF(2^n)-{0}の位数2^n-1の約数である。
もしg(x)が原始多項式でないならばGの位数は2^n-1未満であって2^n-1の約数である。
従ってGの位数が2^n-1未満の2^n-1の約数でなければGの位数はg(x)は2^n-1であり原始多項式ということになる。

n=9の場合：
「2^9-1未満の2^9-1の約数」は1,7,73なのでGの位数が1,7,73の約数でなければg(x)は原始多項式ということになる。
x^1をg(x)で割った余りが1でなく（これは当たり前なので不要）
x^7をg(x)で割った余りが1でなく（これは当たり前なので不要）
x^73をg(x)で割った余りが1でない
ならばGの位数は2^9-1=511ということになりg(x)は原始多項式ということになる。
(2^9-1=511=7x73)

従ってNo1,No2,No3,No4は間違いで原始多項式の条件は

9次多項式f(x)が原始多項式である条件：
（１）既約多項式であること。
（２）x^73をf(x)で割った余りが1でないこと。

でした。
いいわけとしては簡単な問題なので余り考えずに回答してしまいました。
教訓としては簡単な問題であってもよく考えるべきだとこうことです。

No.6 回答者： reiman 回答日時： 2009/07/31 18:01

間違いではないのですがゴミがついています。

1,7,73の約数→1,7,73
直さなくてもたまたま間違いではないですがゴミがあると分かりにくいので削除すべきだと思いました。

位数2素数体係数多項式を位数2素数体係数n次既約多項式g(x)で割った余りが同一のものを同一視するという位数2素数体係数多項式の集合を考えるとそれは位数2^nの有限体（ガロア体GF(2^n)）になる。
そしてGF(2^n)-{0}は乗法について有限群になる。
前記有限体上においてxのべき乗からなる巡回群GはGF(2^n)-{0}の部分群なのでその位数はGF(2^n)-{0}の位数2^n-1の約数である。
もしg(x)が原始多項式でないならばGの位数は2^n-1未満であって2^n-1の約数である。
従ってGの位数が2^n-1未満の2^n-1の約数でなければGの位数はg(x)は2^n-1であり原始多項式ということになる。

n=9の場合：
「2^9-1未満の2^9-1の約数」は1,7,73なのでGの位数が1,7,73の約数でなければg(x)は原始多項式ということになる。
x^1をg(x)で割った余りが1でなく（これは当たり前なので不要）
x^7をg(x)で割った余りが1でなく（これは当たり前なので不要）
x^73をg(x)で割った余りが1でない
ならばGの位数は2^9-1=511ということになりg(x)は原始多項式ということになる。
(2^9-1=511=7x73)

従ってNo1,No2,No3,No4は間違いで原始多項式の条件は

9次多項式f(x)が原始多項式である条件：
（１）既約多項式であること。
（２）x^73をf(x)で割った余りが1でないこと。

この回答へのお礼

ご回答ありがとうございます。

専門用語でけっこうわからないところがあるので、
とりあえず一つずつ解決していこうと思います！

また質問するかもしれないです(^0^;

お礼日時：2009/08/01 15:01

No.7 回答者： reiman 回答日時： 2009/08/01 10:16

素数体2上の原始多項式を求めるプログラムをphpで作ってみたのですが

作る過程でプログラムを作るのに都合のよい条件は既に述べたものではなく
次の方がプログラム作成上いいという結論に達しました。

素数体2上のN次原始多項式f(x)の条件：
(1) x^(2^N-1)≡1 (mod f(x))　であること
(2) 0<n<2^N-1 なる整数nにおいて x^n≡1 (mod f(x))　でないこと

この条件だと既約多項式である必要がないのでプログラミングが楽でした。

プログラムはPHPで作成しました。
なお、結果の原始多項式は左詰めで
高次から低次に向かって各次数の係数のみを並べて
1行1原始多項式で表示しました。

<?php
$N=8;
$c=pow(2,$N);
for($p=1;$p<$c;$p++)
{
$f=$c^$p;
$a=1;
for($i=1;$i<$c;$i++)
{
$a<<=1;
if(($a & $c)==$c)$a^=$f;
if($a==1)break;
}
if($i==($c-1))
{
$s=sprintf("%b (%d xor %d)",$f,$c,$p);
echo"{$s}<br/>";
}
}
?>

結果：
1000010001 (512 xor 17)
1000011011 (512 xor 27)
1000100001 (512 xor 33)
1000101101 (512 xor 45)
1000110011 (512 xor 51)
1001011001 (512 xor 89)
1001011111 (512 xor 95)
1001101001 (512 xor 105)
1001101111 (512 xor 111)
1001110111 (512 xor 119)
1001111101 (512 xor 125)
1010000111 (512 xor 135)
1010010101 (512 xor 149)
1010100011 (512 xor 163)
1010100101 (512 xor 165)
1010101111 (512 xor 175)
1010110111 (512 xor 183)
1010111101 (512 xor 189)
1011001111 (512 xor 207)
1011010001 (512 xor 209)
1011011011 (512 xor 219)
1011110101 (512 xor 245)
1011111001 (512 xor 249)
1100010011 (512 xor 275)
1100010101 (512 xor 277)
1100011111 (512 xor 287)
1100100011 (512 xor 291)
1100110001 (512 xor 305)
1100111011 (512 xor 315)
1101001111 (512 xor 335)
1101011011 (512 xor 347)
1101100001 (512 xor 353)
1101101011 (512 xor 363)
1101101101 (512 xor 365)
1101110011 (512 xor 371)
1101111111 (512 xor 383)
1110000101 (512 xor 389)
1110001111 (512 xor 399)
1110110101 (512 xor 437)
1110111001 (512 xor 441)
1111000111 (512 xor 455)
1111001011 (512 xor 459)
1111001101 (512 xor 461)
1111010101 (512 xor 469)
1111011001 (512 xor 473)
1111100011 (512 xor 483)
1111101001 (512 xor 489)
1111111011 (512 xor 507)

No.8 回答者： reiman 回答日時： 2009/08/01 10:48

N=8となっていましたがこちらの方で8次の原始多項式も見ていたので

結果とリストが食い違っていました。
結果はもちろん9次ですからN=9の結果です。
訂正します。

素数体2上の原始多項式を求めるプログラムをphpで作ってみたのですが
作る過程でプログラムを作るのに都合のよい条件は既に述べたものではなく次の方がいいという結論に達しました。

素数体2上のN次原始多項式f(x)の条件：
(1) x^(2^N-1)≡1 (mod f(x))　であること
(2) 0<n<2^N-1 なる整数nにおいて x^n≡1 (mod f(x))　でないこと

この条件だと既約多項式であることを要求する必要がないのでプログラミングが楽でした。
もちろん原始多項式は既約多項式であることに変わりはありません。
なお、既約多項式表と原始多項式表を同時に求める場合には先の条件の方が良いのです。

プログラムはPHPで作成しました。
なお、結果の原始多項式は左詰めで
高次から低次に向かって各次数の係数のみを並べて
1行1原始多項式で表示しました。

<?php
$N=9;
$c=pow(2,$N);
echo"{$N} 次原始多項式：<br/>";
for($p=1;$p<$c;$p++)
{
$f=$c^$p;
$a=1;
for($i=1;$i<$c;$i++)
{
$a<<=1;
if(($a & $c)==$c)$a^=$f;
if($a==1)break;
}
if($i==($c-1))
{
$s=sprintf("%b (%d xor %d)",$f,$c,$p);
echo"{$s}<br/>";
}
}
?>

結果：
9 次原始多項式：
1000010001 (512 xor 17)
1000011011 (512 xor 27)
1000100001 (512 xor 33)
1000101101 (512 xor 45)
1000110011 (512 xor 51)
1001011001 (512 xor 89)
1001011111 (512 xor 95)
1001101001 (512 xor 105)
1001101111 (512 xor 111)
1001110111 (512 xor 119)
1001111101 (512 xor 125)
1010000111 (512 xor 135)
1010010101 (512 xor 149)
1010100011 (512 xor 163)
1010100101 (512 xor 165)
1010101111 (512 xor 175)
1010110111 (512 xor 183)
1010111101 (512 xor 189)
1011001111 (512 xor 207)
1011010001 (512 xor 209)
1011011011 (512 xor 219)
1011110101 (512 xor 245)
1011111001 (512 xor 249)
1100010011 (512 xor 275)
1100010101 (512 xor 277)
1100011111 (512 xor 287)
1100100011 (512 xor 291)
1100110001 (512 xor 305)
1100111011 (512 xor 315)
1101001111 (512 xor 335)
1101011011 (512 xor 347)
1101100001 (512 xor 353)
1101101011 (512 xor 363)
1101101101 (512 xor 365)
1101110011 (512 xor 371)
1101111111 (512 xor 383)
1110000101 (512 xor 389)
1110001111 (512 xor 399)
1110110101 (512 xor 437)
1110111001 (512 xor 441)
1111000111 (512 xor 455)
1111001011 (512 xor 459)
1111001101 (512 xor 461)
1111010101 (512 xor 469)
1111011001 (512 xor 473)
1111100011 (512 xor 483)
1111101001 (512 xor 489)
1111111011 (512 xor 507)

N=8の場合の結果：
8 次原始多項式：
100011101 (256 xor 29)
100101011 (256 xor 43)
100101101 (256 xor 45)
101001101 (256 xor 77)
101011111 (256 xor 95)
101100011 (256 xor 99)
101100101 (256 xor 101)
101101001 (256 xor 105)
101110001 (256 xor 113)
110000111 (256 xor 135)
110001101 (256 xor 141)
110101001 (256 xor 169)
111000011 (256 xor 195)
111001111 (256 xor 207)
111100111 (256 xor 231)
111110101 (256 xor 245)

No.9 回答者： reiman 回答日時： 2009/08/01 11:25

ついでに

x^kがどうなるかを示します。
右辺は位数2の素数体上多項式であって係数の並びで表現しています。

<?php
$N=9;
$p=32+1;
$c=pow(2,$N);
$f=$c^$p;
$a=1;
for($i=0;$i<$c;$i++)
{
$s=sprintf("x^(%03d) = %010b",$i,$a);
$color=($a==1)?"red":"blue";
print<<<EOL
<div style="color:{$color}">{$s}</div>
EOL;
$a<<=1;
if(($a & $c)==$c)$a^=$f;
}
?>

結果：
x^(000) = 0000000001
x^(001) = 0000000010
x^(002) = 0000000100
x^(003) = 0000001000
x^(004) = 0000010000
x^(005) = 0000100000
x^(006) = 0001000000
x^(007) = 0010000000
x^(008) = 0100000000
x^(009) = 0000100001
x^(010) = 0001000010
x^(011) = 0010000100
x^(012) = 0100001000
x^(013) = 0000110001
x^(014) = 0001100010
x^(015) = 0011000100
x^(016) = 0110001000
x^(017) = 0100110001
x^(018) = 0001000011
x^(019) = 0010000110
x^(020) = 0100001100
x^(021) = 0000111001
x^(022) = 0001110010
x^(023) = 0011100100
x^(024) = 0111001000
x^(025) = 0110110001
x^(026) = 0101000011
x^(027) = 0010100111
x^(028) = 0101001110
x^(029) = 0010111101
x^(030) = 0101111010
x^(031) = 0011010101
x^(032) = 0110101010
x^(033) = 0101110101
x^(034) = 0011001011
x^(035) = 0110010110
x^(036) = 0100001101
x^(037) = 0000111011
x^(038) = 0001110110
x^(039) = 0011101100
x^(040) = 0111011000
x^(041) = 0110010001
x^(042) = 0100000011
x^(043) = 0000100111
x^(044) = 0001001110
x^(045) = 0010011100
x^(046) = 0100111000
x^(047) = 0001010001
x^(048) = 0010100010
x^(049) = 0101000100
x^(050) = 0010101001
x^(051) = 0101010010
x^(052) = 0010000101
x^(053) = 0100001010
x^(054) = 0000110101
x^(055) = 0001101010
x^(056) = 0011010100
x^(057) = 0110101000
x^(058) = 0101110001
x^(059) = 0011000011
x^(060) = 0110000110
x^(061) = 0100101101
x^(062) = 0001111011
x^(063) = 0011110110
x^(064) = 0111101100
x^(065) = 0111111001
x^(066) = 0111010011
x^(067) = 0110000111
x^(068) = 0100101111
x^(069) = 0001111111
x^(070) = 0011111110
x^(071) = 0111111100
x^(072) = 0111011001
x^(073) = 0110010011
x^(074) = 0100000111
x^(075) = 0000101111
x^(076) = 0001011110
x^(077) = 0010111100
x^(078) = 0101111000
x^(079) = 0011010001
x^(080) = 0110100010
x^(081) = 0101100101
x^(082) = 0011101011
x^(083) = 0111010110
x^(084) = 0110001101
x^(085) = 0100111011
x^(086) = 0001010111
x^(087) = 0010101110
x^(088) = 0101011100
x^(089) = 0010011001
x^(090) = 0100110010
x^(091) = 0001000101
x^(092) = 0010001010
x^(093) = 0100010100
x^(094) = 0000001001
x^(095) = 0000010010
x^(096) = 0000100100
x^(097) = 0001001000
x^(098) = 0010010000
x^(099) = 0100100000
x^(100) = 0001100001
x^(101) = 0011000010
x^(102) = 0110000100
x^(103) = 0100101001
x^(104) = 0001110011
x^(105) = 0011100110
x^(106) = 0111001100
x^(107) = 0110111001
x^(108) = 0101010011
x^(109) = 0010000111
x^(110) = 0100001110
x^(111) = 0000111101
x^(112) = 0001111010
x^(113) = 0011110100
x^(114) = 0111101000
x^(115) = 0111110001
x^(116) = 0111000011
x^(117) = 0110100111
x^(118) = 0101101111
x^(119) = 0011111111
x^(120) = 0111111110
x^(121) = 0111011101
x^(122) = 0110011011
x^(123) = 0100010111
x^(124) = 0000001111
x^(125) = 0000011110
x^(126) = 0000111100
x^(127) = 0001111000
x^(128) = 0011110000
x^(129) = 0111100000
x^(130) = 0111100001
x^(131) = 0111100011
x^(132) = 0111100111
x^(133) = 0111101111
x^(134) = 0111111111
x^(135) = 0111011111
x^(136) = 0110011111
x^(137) = 0100011111
x^(138) = 0000011111
x^(139) = 0000111110
x^(140) = 0001111100
x^(141) = 0011111000
x^(142) = 0111110000
x^(143) = 0111000001
x^(144) = 0110100011
x^(145) = 0101100111
x^(146) = 0011101111
x^(147) = 0111011110
x^(148) = 0110011101
x^(149) = 0100011011
x^(150) = 0000010111
x^(151) = 0000101110
x^(152) = 0001011100
x^(153) = 0010111000
x^(154) = 0101110000
x^(155) = 0011000001
x^(156) = 0110000010
x^(157) = 0100100101
x^(158) = 0001101011
x^(159) = 0011010110
x^(160) = 0110101100
x^(161) = 0101111001
x^(162) = 0011010011
x^(163) = 0110100110
x^(164) = 0101101101
x^(165) = 0011111011
x^(166) = 0111110110
x^(167) = 0111001101
x^(168) = 0110111011
x^(169) = 0101010111
x^(170) = 0010001111
x^(171) = 0100011110
x^(172) = 0000011101
x^(173) = 0000111010
x^(174) = 0001110100
x^(175) = 0011101000
x^(176) = 0111010000
x^(177) = 0110000001
x^(178) = 0100100011
x^(179) = 0001100111
x^(180) = 0011001110
x^(181) = 0110011100
x^(182) = 0100011001
x^(183) = 0000010011
x^(184) = 0000100110
x^(185) = 0001001100
x^(186) = 0010011000
x^(187) = 0100110000
x^(188) = 0001000001
x^(189) = 0010000010
x^(190) = 0100000100
x^(191) = 0000101001
x^(192) = 0001010010
x^(193) = 0010100100
x^(194) = 0101001000
x^(195) = 0010110001
x^(196) = 0101100010
x^(197) = 0011100101
x^(198) = 0111001010
x^(199) = 0110110101
x^(200) = 0101001011
x^(201) = 0010110111
x^(202) = 0101101110
x^(203) = 0011111101
x^(204) = 0111111010
x^(205) = 0111010101
x^(206) = 0110001011
x^(207) = 0100110111
x^(208) = 0001001111
x^(209) = 0010011110
x^(210) = 0100111100
x^(211) = 0001011001
x^(212) = 0010110010
x^(213) = 0101100100
x^(214) = 0011101001
x^(215) = 0111010010
x^(216) = 0110000101
x^(217) = 0100101011
x^(218) = 0001110111
x^(219) = 0011101110
x^(220) = 0111011100
x^(221) = 0110011001
x^(222) = 0100010011
x^(223) = 0000000111
x^(224) = 0000001110
x^(225) = 0000011100
x^(226) = 0000111000
x^(227) = 0001110000
x^(228) = 0011100000
x^(229) = 0111000000
x^(230) = 0110100001
x^(231) = 0101100011
x^(232) = 0011100111
x^(233) = 0111001110
x^(234) = 0110111101
x^(235) = 0101011011
x^(236) = 0010010111
x^(237) = 0100101110
x^(238) = 0001111101
x^(239) = 0011111010
x^(240) = 0111110100
x^(241) = 0111001001
x^(242) = 0110110011
x^(243) = 0101000111
x^(244) = 0010101111
x^(245) = 0101011110
x^(246) = 0010011101
x^(247) = 0100111010
x^(248) = 0001010101
x^(249) = 0010101010
x^(250) = 0101010100
x^(251) = 0010001001
x^(252) = 0100010010
x^(253) = 0000000101
x^(254) = 0000001010
x^(255) = 0000010100
x^(256) = 0000101000
x^(257) = 0001010000
x^(258) = 0010100000
x^(259) = 0101000000
x^(260) = 0010100001
x^(261) = 0101000010
x^(262) = 0010100101
x^(263) = 0101001010
x^(264) = 0010110101
x^(265) = 0101101010
x^(266) = 0011110101
x^(267) = 0111101010
x^(268) = 0111110101
x^(269) = 0111001011
x^(270) = 0110110111
x^(271) = 0101001111
x^(272) = 0010111111
x^(273) = 0101111110
x^(274) = 0011011101
x^(275) = 0110111010
x^(276) = 0101010101
x^(277) = 0010001011
x^(278) = 0100010110
x^(279) = 0000001101
x^(280) = 0000011010
x^(281) = 0000110100
x^(282) = 0001101000
x^(283) = 0011010000
x^(284) = 0110100000
x^(285) = 0101100001
x^(286) = 0011100011
x^(287) = 0111000110
x^(288) = 0110101101
x^(289) = 0101111011
x^(290) = 0011010111
x^(291) = 0110101110
x^(292) = 0101111101
x^(293) = 0011011011
x^(294) = 0110110110
x^(295) = 0101001101
x^(296) = 0010111011
x^(297) = 0101110110
x^(298) = 0011001101
x^(299) = 0110011010
x^(300) = 0100010101
x^(301) = 0000001011
x^(302) = 0000010110
x^(303) = 0000101100
x^(304) = 0001011000
x^(305) = 0010110000
x^(306) = 0101100000
x^(307) = 0011100001
x^(308) = 0111000010
x^(309) = 0110100101
x^(310) = 0101101011
x^(311) = 0011110111
x^(312) = 0111101110
x^(313) = 0111111101
x^(314) = 0111011011
x^(315) = 0110010111
x^(316) = 0100001111
x^(317) = 0000111111
x^(318) = 0001111110
x^(319) = 0011111100
x^(320) = 0111111000
x^(321) = 0111010001
x^(322) = 0110000011
x^(323) = 0100100111
x^(324) = 0001101111
x^(325) = 0011011110
x^(326) = 0110111100
x^(327) = 0101011001
x^(328) = 0010010011
x^(329) = 0100100110
x^(330) = 0001101101
x^(331) = 0011011010
x^(332) = 0110110100
x^(333) = 0101001001
x^(334) = 0010110011
x^(335) = 0101100110
x^(336) = 0011101101
x^(337) = 0111011010
x^(338) = 0110010101
x^(339) = 0100001011
x^(340) = 0000110111
x^(341) = 0001101110
x^(342) = 0011011100
x^(343) = 0110111000
x^(344) = 0101010001
x^(345) = 0010000011
x^(346) = 0100000110
x^(347) = 0000101101
x^(348) = 0001011010
x^(349) = 0010110100
x^(350) = 0101101000
x^(351) = 0011110001
x^(352) = 0111100010
x^(353) = 0111100101
x^(354) = 0111101011
x^(355) = 0111110111
x^(356) = 0111001111
x^(357) = 0110111111
x^(358) = 0101011111
x^(359) = 0010011111
x^(360) = 0100111110
x^(361) = 0001011101
x^(362) = 0010111010
x^(363) = 0101110100
x^(364) = 0011001001
x^(365) = 0110010010
x^(366) = 0100000101
x^(367) = 0000101011
x^(368) = 0001010110
x^(369) = 0010101100
x^(370) = 0101011000
x^(371) = 0010010001
x^(372) = 0100100010
x^(373) = 0001100101
x^(374) = 0011001010
x^(375) = 0110010100
x^(376) = 0100001001
x^(377) = 0000110011
x^(378) = 0001100110
x^(379) = 0011001100
x^(380) = 0110011000
x^(381) = 0100010001
x^(382) = 0000000011
x^(383) = 0000000110
x^(384) = 0000001100
x^(385) = 0000011000
x^(386) = 0000110000
x^(387) = 0001100000
x^(388) = 0011000000
x^(389) = 0110000000
x^(390) = 0100100001
x^(391) = 0001100011
x^(392) = 0011000110
x^(393) = 0110001100
x^(394) = 0100111001
x^(395) = 0001010011
x^(396) = 0010100110
x^(397) = 0101001100
x^(398) = 0010111001
x^(399) = 0101110010
x^(400) = 0011000101
x^(401) = 0110001010
x^(402) = 0100110101
x^(403) = 0001001011
x^(404) = 0010010110
x^(405) = 0100101100
x^(406) = 0001111001
x^(407) = 0011110010
x^(408) = 0111100100
x^(409) = 0111101001
x^(410) = 0111110011
x^(411) = 0111000111
x^(412) = 0110101111
x^(413) = 0101111111
x^(414) = 0011011111
x^(415) = 0110111110
x^(416) = 0101011101
x^(417) = 0010011011
x^(418) = 0100110110
x^(419) = 0001001101
x^(420) = 0010011010
x^(421) = 0100110100
x^(422) = 0001001001
x^(423) = 0010010010
x^(424) = 0100100100
x^(425) = 0001101001
x^(426) = 0011010010
x^(427) = 0110100100
x^(428) = 0101101001
x^(429) = 0011110011
x^(430) = 0111100110
x^(431) = 0111101101
x^(432) = 0111111011
x^(433) = 0111010111
x^(434) = 0110001111
x^(435) = 0100111111
x^(436) = 0001011111
x^(437) = 0010111110
x^(438) = 0101111100
x^(439) = 0011011001
x^(440) = 0110110010
x^(441) = 0101000101
x^(442) = 0010101011
x^(443) = 0101010110
x^(444) = 0010001101
x^(445) = 0100011010
x^(446) = 0000010101
x^(447) = 0000101010
x^(448) = 0001010100
x^(449) = 0010101000
x^(450) = 0101010000
x^(451) = 0010000001
x^(452) = 0100000010
x^(453) = 0000100101
x^(454) = 0001001010
x^(455) = 0010010100
x^(456) = 0100101000
x^(457) = 0001110001
x^(458) = 0011100010
x^(459) = 0111000100
x^(460) = 0110101001
x^(461) = 0101110011
x^(462) = 0011000111
x^(463) = 0110001110
x^(464) = 0100111101
x^(465) = 0001011011
x^(466) = 0010110110
x^(467) = 0101101100
x^(468) = 0011111001
x^(469) = 0111110010
x^(470) = 0111000101
x^(471) = 0110101011
x^(472) = 0101110111
x^(473) = 0011001111
x^(474) = 0110011110
x^(475) = 0100011101
x^(476) = 0000011011
x^(477) = 0000110110
x^(478) = 0001101100
x^(479) = 0011011000
x^(480) = 0110110000
x^(481) = 0101000001
x^(482) = 0010100011
x^(483) = 0101000110
x^(484) = 0010101101
x^(485) = 0101011010
x^(486) = 0010010101
x^(487) = 0100101010
x^(488) = 0001110101
x^(489) = 0011101010
x^(490) = 0111010100
x^(491) = 0110001001
x^(492) = 0100110011
x^(493) = 0001000111
x^(494) = 0010001110
x^(495) = 0100011100
x^(496) = 0000011001
x^(497) = 0000110010
x^(498) = 0001100100
x^(499) = 0011001000
x^(500) = 0110010000
x^(501) = 0100000001
x^(502) = 0000100011
x^(503) = 0001000110
x^(504) = 0010001100
x^(505) = 0100011000
x^(506) = 0000010001
x^(507) = 0000100010
x^(508) = 0001000100
x^(509) = 0010001000
x^(510) = 0100010000
x^(511) = 0000000001