すべて1つの多項式

数学において、全1多項式（All One Polynomial、AOP）とは、すべての係数が1である多項式である。2 次の有限体上では、AOPが既約となる条件が既知であり、この多項式を用いて、標数2の有限体における乗算のための効率的なアルゴリズムや回路を定義することができる。^[¹^] AOPは1-等間隔多項式である。^[²^]

意味

m次のAOPはx ^mからx ⁰までのすべての項の係数が1であり、次のように表される。

AOP_{m}(x)=\sum _{i=0}^{m}x^{i}

または

AOP_{m}(x)=x^{m}+x^{m-1}+\cdots +x+1

または

AOP_{m}(x)={x^{m+1}-1 \over {x-1}}.}

したがって、m次のすべて 1 の多項式の根は、1 自体以外のすべて ( m +1) 次 1 の根です。

GF(2)上でAOPは多くの興味深い性質を持ちます。

AOPのハミング重みはm + 1であり、その次数で可能な最大値である^{[ 3 ]}
AOPは、m + 1が素数であり、2がm + 1を法とする原始根である場合に限り既約である^[¹^] （ pを素数とするGF( p )上では、 m + 1が素数であり、pがm + 1を法とする原始根である場合に限り既約である）
原始多項式である唯一の AOPはx ² + x + 1です。

ハミング重みは大きいにもかかわらず、表現の容易さやその他の改良により、符号理論や暗号などの分野で効率的な実装がなされている。^{[ 1 ]}

において、 m + 1が素数pであるときはいつでもAOPは既約であり、したがってこれらの場合、p番目の円分多項式は既約である。^[⁴^] $\mathbb {Q}$

^ ^a ^b ^cコーエン、アンリ; フレイ、ゲルハルト; アヴァンジ、ロベルト; ドッシュ、クリストフ;ランゲ、タニャ; グエン、キム; ヴェルカウテレン、フレデリック (2005)、『楕円曲線暗号と超楕円曲線暗号ハンドブック』、離散数学とその応用、CRC プレス、p. 215、ISBN 9781420034981。
^伊藤俊也; 辻井茂雄 (1989)、「GF(2 ^m )体のクラスに対する並列乗算器の構造」、情報計算、83 (1): 21– 40、doi : 10.1016/0890-5401(89)90045-X。
^ Reyhani-Masoleh, Arash; Hasan, M. Anwar (2003)、「低複雑度のビット並列多項式基底乗算器について」、Cryptographic Hardware and Embedded Systems - CHES 2003、Lecture Notes in Computer Science、vol. 2779、Springer、pp. 189– 202、doi : 10.1007/978-3-540-45238-6_16、ISBN 978-3-540-40833-8。
^杉村達夫; 末次康則 (1991)、「既約円分多項式に関する考察」、電子情報通信学会誌、74 (4): 106–113 , doi : 10.1002/ecjc.4430740412 , MR 1136200 。