これは、いくつかのインタビューの質問で尋ねられる質問です。
係数がバイナリである 3 つの多項式 f(x)、g(x)、h(x) が与えられます。[f(x)*g(x)] mod h(x) [バイナリ係数のすべての操作] を与える
多項式はこの形式で与えられます... x3 + x + 1 は「1011」として与えられます。多項式… (f*g) mod h を出力するプログラム char* multmod (char *f, char *g, char *h) を作成します。
どのようなアプローチが考えられますか? ビットレベルで何かできる？
動機
ここでの2進係数は、係数がフィールドZ_2の2を法とするか、値0と1を取り、ビットのように動作することを意味します。係数が2を底とする任意の整数であることを意味するものではありません。それらは、単に2進数システムで表現されるのではなく、2進数です（正確に2つの値を取ります）。
これをしっかりと念頭に置いて、この質問に答えるのはかなり簡単です。そうです、XORと（左）シフトのビット演算で十分です。この質問に答える必要はありませんが、この質問は暗号化によって動機付けられています。これは、ハッシュで一般的に使用されるいくつかのビット演算と、いくつかの暗号化スキームおよび抽象代数との間のリンクを示しているため、有限体上の多項式に関する結果を暗号解読で活用できます。別の多項式を法として積をとると、結果の次数が特定の制限を超えて大きくなるのを防ぐことができます。マシンレジスタの操作は、これをオーバーフローとして自然に実行します。
添加
まず、加算についてお話ししましょう。係数は2を法としてx + x = 2x = 0x = 0いるため、2 mod 2 = 0。したがって、同じ用語が2つある場合は常にキャンセルされ、1つしかない場合は持続します。これはと同じ動作XORです。たとえば、(x^4 + x^2 + 1) + (x^3 + x^2):
(1x^4+0x^3+1x^2+0x^1+1x^0)+(0x^4+1x^3+1x^2+0x^1+0x^0) = (1x^4+1x^3+0x^2+0x^1+1x^0)
または、コンパクト係数のみの表記を使用して、
10101 XOR 01100 = 11001
乗算
を掛けるxと、各項の累乗が1つ増えます。コンパクト表記では、これは左ビット単位のシフトに相当します。
(1x^4+0x^3+1x^2+0x^1+1x^0) * x = (1x^5+0x^4+1x^3+0x^2+1x^1+0x^0)
10101 << 1 = 101010
したがって、多項式f(x) * g(x)を乗算f(x)するには、の各項をg(x)個別に乗算します。各項はシフトに相当し、次に加算します。加算はXORに相当します。掛けましょう(x^4 + x^2 + 1) * (x^3 + x^2)
(x^4 + x^2 + 1) * (x^3 + x^2) = (x^4 + x^2 + 1)*x^3 + (x^4 + x^2 + 1) *x^2
(10101 << 3) XOR (10101 << 2) = 10101000 XOR 01010100 = 11111100
だから、答えはx^7 + x^6 + x^5 + x^4 + x^3 + x^2です。
モジュロ削減
モジュロ除算h(x)もかなり簡単です。筆算の仕方を覚えておく必要はありません。掛け算のように、私たちはそれを用語ごとに行います。同じ例を続けて、モジュロで取りましょうh(x) = x^5 + x
(x^7 + ... + x^2) mod (x^5+x) = [x^7 mod (x^5+x)] + ... + [x^2 mod (x^5+x)]
さて、の次数が、ここnでは5の次数x^nよりも小さい場合、除算されないh(x)ため、何もする必要はありません。h(x)x^n
[x^2 mod (x^5+x)] = x^2 or 00000100
[x^3 mod (x^5+x)] = x^3 or 00001000
[x^4 mod (x^5+x)] = x^4 or 00010000
h(x)そのとき度が等しい場合、1回の除算と言うことができx^n、の残りの項によってオーバーシュートしましたh(x)。アンダーシュートではなくオーバーシュートしたことはほとんど問題ではなく、以降のサインオンも重要ではありません-1 mod 2 = 1。ここ、
x^5 = (x^5 + x) – x, so
[x^5 mod (x^5+x)] = x, or 00000010
一般に、[x ^ n mod h（x）] = [h（x）-x^n]の場合n = degree(h)。コンパクトな形式では、これはthビットをオフにすることと同じです。これは、の表現を次のn表現とXOR演算することで実行できます。h(x)x^n
00100010 XOR 00100000 = 00000010.
の次数が、次数を一致させるために乗算できるよりも大きい場合は、前の場合と同じように続行しx^nます。h(x)h(x)x^k
x ^ 6 =（x ^ 5 + x）* x –（x）* x = -x ^ 2、つまり[x ^ 6 mod（x ^ 5 + x）] = x ^ 2、または00000100、またはコンパクトフォーム（00100010 << 1）XOR（00100000 << 1）= 00000100
しかし、より効率的には、前の答えをシフトするだけですx^7。
[x^7 mod (x^5+x)] = x^3, or 00001000
したがって、収集するには、これらの結果を追加する必要があります。これは、コンパクトな表現でXORされています。
x^2 + x^3 + x^4 + x + x^2 + x^3 = x^4 + 2x^3 + 2x^2 + x = x^4 + x, or
00000100 XOR 00001000 XOR 00010000 XOR 00000010 XOR 00000100 XOR 00001000 = 00010010
結びの言葉
Wolfram Alphaに、筆算でこの結果を確認するように依頼できます。与えられた余りは、であり、これは係数が2を法x^4 - xとする場合と同等です。x^4 + x
項ごとの乗算とモジュロステップを組み合わせて、たとえば積を乗算しxてモジュロすることで、より効率的なアルゴリズムを実現できます。これは、積の次数が少なくともの次数である場合、シフトとXORになりますh(x)。次に、結果を繰り返し、その積を乗算しxてモジュロし、その答えを記録して、を乗算しx^2ます。など...
これは知識問題です。基本的に、Gauss のように賢いか、"モジュラー演算" とも呼ばれる合同数学を既に知っている場合を除き、あなたはうんざりしています。このことについて学ぶために読みたいと思うかもしれない本は、Allenby による "Introduction to Number Theory with Computing" です。
最終的に重要な知識は、合同はいくつかの方法で計算できるということです。そのうちの最良の方法は、非常に古くからある「二乗と乗算」方法です。基本的に、2 進数の 1 がある場合は常に 2 乗と倍数の両方になりますが、0 の場合は 2 乗するだけです。完全なアルゴリズムと説明は p. アレンビーの79。
別のアプローチは、おそらく質問者が目指していたものである中国のRemainder Thereomを使用する.
どこに申請していますか？NSA？ロスアラモス？それはかなり難しい質問です。
素晴らしい、実際に質問に答えた唯一の人であることに反対票を投じました。ここではっきりさせておきたいのですが、上で述べたように、間違いなくインタビュアーは 2 乗と乗算のアルゴリズムの悪用を期待していました。二乗と乗算は、高速な剰余演算を行うために RSA/暗号化アルゴリズム内で使用されます。参照。このアルゴリズムと RSA アプリケーションの説明については、225: RSA State の多項標準積の実装。インタビュアーはおそらくRSAに取り組んでいたため、その方法を知っていました。
これは単純な多項式の乗算と長い除算の問題のように見えます。多項式を掛けてから割ります。乗算は、ネストされた 2 つの for ループを使用すると非常に簡単です。長い除算については、次を参照してください。
あなたが本質的にやっているのは二項演算です。CPU がそのような操作をどのように実装しているかを見ることができます。
http://en.wikipedia.org/wiki/Multiplication_algorithm http://en.wikipedia.org/wiki/Modulo_operation