4

最終学年の大学プロジェクトの一環として、NTRU 公開鍵暗号システムを実装する必要があります。再帰を介して長い多項式を乗算するアルゴリズムを実装しようとしていますが、疑似コードを理解しようとしてかなり行き詰まっています。

Algorithm PolyMult(c, b, a, n, N)
Require: N, n, and the polynomial operands, b and c.
PolyMult returns the product polynomial a through the argument list
PolyMult(a,b,c,n,N)
{
1. if(...)
2. {
3.    ...
4.    ...
5.    ...
6.    ...
7. }
8. else
9. {
10.   n1 = n/2;
11.   n2 = n-n1;
12.   b = b1+b2*X^(n1);
13.   c = c1+c2*X^(n1);
14.   B = b1+b2;
15.   C = c1+c2;
16.   PolyMult(a1,b1,c1,n1,N);// a1 = b1*c1
17.   PolyMult(a2,b2,c2,n2,N);// a2=b2*c2
18.   PolyMult(a3,B,C,n2,N);// a3 = B*C=(b1+b2)*(c1+c2)
19.   a = a1 + (a3-a1-a2)*X^(n1) + a2*X^(2*n1);
20.}
}

N、n、n1、n2 はすべて int 型であることに注意してください。a,a1,a2,b,b1,b2,c,c1,c2,B,C はすべて多項式であり、配列として表されます。

行 16、17、および 18 で、関数 PolyMult がそれぞれ a1、b1、c1、n1、N、次に a2、b2、c2、n2、N、最後に a3、B、C、n2、N の引数で呼び出されます。配列 a1,b1,c1 を 16 行目より前に初期化し、それらを PolyMult 自体に渡し (ここから再帰が開始されます!)、応答を返し、それを一時配列に格納します。たとえば、16 行目を次のように実装します。

int z[] = PolyMult(a1,b1,c1,n1,N);

ここで私の質問は次のとおりです。配列 z[] に格納された多項式がプログラムで再び使用されるのはいつですか。疑似コードから再び使用される兆候は見られませんが、配列 z[] がプログラムで再び使用されない場合プログラム、16行目と再帰をまとめたポイントは何ですか? 16 行目から 18 行目はどのように実装すればよいですか?

繰り返しになりますが、配列 z に格納された多項式は、いつ、どのようにプログラムで再び使用されるのでしょうか? そして、16行目から18行目を実装するにはどうすればよいですか?

詳細については、この記事の 3 ページ目に疑似コードの完全な説明があります: http://www.ntru.com/cryptolab/pdf/NTRUTech010.pdf。

4

2 に答える 2

3

a[]擬似コードでは、結果は、パラメーターとして指定された配列に格納することによって「返されます」。PolyMult(a1, b1, c1, n1, N)はその結果を に格納しa1[]ます。

その乗算手法は、多項式に適用される単純なカラツバ乗算です (多項式にはキャリーがないため、さらに簡単になります)。ポインターについては、このウィキペディアの記事を参照してください。

個人的には、疑似コードをたどるよりも、数学だけで理解しやすいと思います。

于 2010-03-06T22:24:18.903 に答える
0

私は NTRU で働いているので、この関心を見て嬉しく思います。

どのパラメータ セットを使用しているかはわかりませんが、多くの NTRU パラメータ セットでは、カラツバの実装に伴うオーバーヘッドに見合う価値がないことがわかりました。A と B を乗算しているとします。NTRUEncrypt 畳み込み演算の場合、関係する多項式の 1 つは常に 2 進または 3 進です。それを A とします。結果の各係数は、B の係数のサブセットの合計です。A を 1 と 0 の配列として格納するのではなく、ゼロ以外の係数のインデックスの配列として格納する場合であり、A があまり密集していない場合は、カラツバを実行するよりもインデックスの配列を処理する方が高速です。コードも小さくてシンプルです。

あなたが勉強している大学を聞いてもいいですか？

于 2010-03-08T20:26:59.257 に答える