拡大か縮小か？
【 拡大か縮小か？】
ある整数nを整数qで割った余りをrとします。nをrと同一視することで得られる集合を、整数Zのqによる剰余類と呼び、Z_qで表します。
qで割った余りは、{0, 1, … , q−1}のq個しかないので、Z_qは q個の要素からなります。また、どんな整数もこのq個の類のどれかに属することになります。
今回は、これまで整数Z上で定義されてきたラティスを、整数の剰余類Z_q上に拡大したラティスの話をします。
「拡大」と書きましたが、実際は「縮小」なんです。正確には「制限」と言ったほうがいいかもしれません。
整数Z上で定義されたラティスは、基底ベクトルの整数倍のベクトルの和として定義されます。それは無限の広がりを持ちます。整数は無限に存在しますから。
Z_q上のラティスは、基底ベクトルのZ_qの要素倍のベクトルの和として定義されます。例えば、Z_3は、3 で割った余りの集合ですから、0, 1, 2 の三つの要素しか持ちません。ですから、Z_3上のラティスは、基底ベクトルの 0倍か1倍か2倍のベクトルの和でできてることになります。
二次元のラティスなら基底ベクトルは二つ、それとZ_3の三つの要素の組み合わせは、3^2で、9通りしかありません。二次元のZ_3上のラティスは、9個の格子点しか持ちません。
Z_q上のラティスは、有限個の格子点から構成されます。それは、無限個の格子点を持つZ上のラティスとの大きな違いです。
ラティスの大きさを「縮小」あるいは「制限」することには、実際的な意味があります。
コンピューターでは、我々は無限の大きさを持ちうる整数をハンドルできません。我々が扱えるのは、有限の大きさ、例えば、128bitで表現される整数のみです。
コンピューターで処理することが前提の「ラティス暗号」の実装の世界では、Z上のラティスではなく、Z_q上のラティスが用いられます。
-------------------
動画「ZのラティスとZ_qのラティス」を公開しました。ご利用ください。
この動画のpdf は、こちらからアクセスできます。
「ラティス暗号入門」のまとめページはこちらです。
blog 「拡大か縮小か？」のURLはこちらです。
コメント
コメントを投稿