【手続補正書】
【提出日】平成30年9月26日(2018.9.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
可換環において難読化された算術を実行するための電子計算装置であって、前記環は有限個の環要素をもち、環要素に対して環加算および環乗算が定義されており、当該計算装置は、環要素をエンコードする整数リストに対して作用し、前記整数リストは少なくとも二つ整数を有し、整数リストは、環要素を、該環要素が一つまたは複数の基本環要素の冪乗の線形結合に等しくなるようエンコードし、前記冪乗は該整数リストによって決定される指数をもち、当該計算装置は、
・増分環要素について定義された増分テーブルを記憶するよう構成された記憶部を有しており、
・前記増分テーブルは、出力環要素が増分環要素が入力環要素に環加算されたものに等しくなるよう入力環要素を出力環要素をエンコードする出力整数リストにマッピングし、
当該計算装置はさらに、環加算ユニットを有しており、前記環加算ユニットは、
・第一の加算入力環要素をエンコードする第一の加算入力整数リストおよび第二の加算入力環要素をエンコードする第二の加算入力整数リストを受領する段階であって、前記増分環要素は前記第一および第二の加算入力環要素から独立である、段階と、
・前記第一および第二の加算入力整数リストから決定される環要素に前記増分テーブルを適用することによって加算出力環要素をエンコードする加算出力整数リストを決定する段階であって、前記加算出力環要素は前記第一の加算入力環要素および前記第二の加算入力環要素の環加算に等しい、段階とを実行するよう構成されており、
前記加算出力整数リストを決定することが、
・一つまたは複数の基本元の冪乗の線形結合である環要素への前記増分テーブルの第一の適用によって、中間加算環要素をエンコードする中間加算整数リストを決定する段階であって、前記冪乗は前記第一および第二の加算入力整数リストから決定される、段階と、
・前記加算出力整数リストを決定する段階であって、前記中間加算整数リストから決定されるおよび前記第二の加算入力整数リストから決定される環要素への前記増分テーブルの第二の適用を含む、段階とを含む、
計算装置。
【請求項２】
環乗算ユニットをさらに有しており、前記環乗算ユニットは、
・第一の乗算入力環要素をエンコードする第一の乗算入力整数リストおよび第二の乗算入力環要素をエンコードする第二の乗算入力整数リストを受領する段階と、
・前記第一および第二の乗算入力整数リストから決定される環要素に前記増分テーブルを適用することによって乗算出力環要素をエンコードする乗算出力整数リストを決定する段階であって、前記乗算出力環要素は前記第一の乗算入力環要素および前記第二の乗算入力環要素の環乗算に等しい、段階とを実行するよう構成されている、
請求項１記載の計算装置。
【請求項３】
前記整数リストが環要素をエンコードする仕方は、
・前記環要素が、基本元を前記整数リストの第一の整数によって決定される冪乗にしたものから、前記基本元を前記整数リストの第二の整数によって決定される冪乗にしたものを引いたものに任意的に定数を乗算したものに等しくなるようにする、または
・前記環要素が、前記基本元を前記整数リストの第一の整数によって決定される冪乗にしたものに、前記基本元を前記整数リストの第二の整数によって決定される冪乗にしたものを足したものに任意的に定数を乗算したものに等しくなるようにする、または
・前記環要素が、前記基本元を前記整数リストの第一の整数によって決定される冪乗にしたもの、かける、前記基本元を前記整数リストの第二の整数によって決定される冪乗にしたものから、前記基本元を前記整数リストの第二の整数のマイナスによって決定される冪乗にしたものを引いたものに任意的に定数を乗算したものに等しくなるようにする、または
・前記環要素が、前記基本元を前記整数リストの第一の整数および第二の整数の第一の線形結合である冪乗にしたもの、足すまたは引く、前記基本元を前記第一の整数および前記第二の整数の第二の線形結合である冪乗にしたものに任意的に定数を乗算したものに等しくなるようにするものである、
請求項１または２記載の計算装置。
【請求項４】
前記中間加算整数リストを決定することがさらに、前記第一および第二の加算入力整数リストから決定された整数を、第一の適用から帰結する整数リスト中の整数に加算することを含む、請求項１記載の計算装置。
【請求項５】
・前記増分テーブルは、前記一つまたは複数の基本環要素を前記第一の整数リストの第一の整数から前記第二の整数リストの第一の整数を引いたもの乗したもの、足すまたは引く、ある基本環要素を前記第一の整数リストの第二の整数から前記第二の整数リストの第一の整数を引いたもの乗したもの、によって形成される環要素に適用される、および／または
・前記増分テーブルは、前記一つまたは複数の基本環要素を前記第一の整数リストの前記第一の整数から前記第一の整数リストの第二の整数を引いたもの乗したもの、足すまたは引く、ある基本環要素を前記第二の整数リストの第一の整数から前記第一の整数リストの前記第二の整数を引いたもの乗したもの、によって形成される環要素に適用される、および／または
・前記増分テーブルは、前記一つまたは複数の基本環要素を前記第一の整数リストの第二の整数から前記第一の整数リストの第一の整数を引いたもの乗したもの、足すまたは引く、ある基本環要素を前記第二の整数リストの第一の整数から前記第一の整数リストの前記第一の整数を引いたもの乗したもの、によって形成される環要素に適用される、
請求項１ないし４のうちいずれか一項記載の計算装置。
【請求項６】
・前記増分テーブルの前記第二の適用の前に、前記中間加算整数リストによって表わされる前記中間加算環要素が否定にされる、
請求項１ないし４のうちいずれか一項記載の計算装置。
【請求項７】
・整数リストによって表わされる環要素が、該整数リストを並べ替えることによって否定にされる、または
・整数リストによって表わされる環要素が、該整数リストの各整数に定数を加えるることによって否定にされる、または
・整数リストによって表わされる環要素が、該整数リストを並べ替え、該整数リストの一つまたは複数の整数に定数を乗算することによって否定にされる、
請求項１ないし６のうちいずれか一項記載の計算装置。
【請求項８】
前記増分テーブルが、前記入力環要素を表わす入力整数リストを入力として取る、請求項１ないし７のうちいずれか一項記載の計算装置。
【請求項９】
乗算出力整数リストを決定することが、
・前記第一および第二の乗算入力整数リストから、それぞれ第一および第二の中間乗算還要素をエンコードする第一の中間乗算整数リストおよび第二の中間乗算整数リストを決定し、
・前記第一および第二の中間乗算整数リストを前記環加算ユニットを通じて加算することを含む、
請求項２記載の計算装置。
【請求項１０】
・前記第一の中間乗算整数リストの第一の整数は、前記第一の乗算入力整数リストの第一の整数、足す、前記第二の乗算入力整数リストの第一の整数であり、
・前記第一の中間乗算整数リストの第二の整数は、前記第一の乗算入力整数リストの第一の整数、足す、前記第二の乗算入力整数リストの第二の整数であり、
・前記第二の中間乗算整数リストの第一の整数は、前記第一の乗算入力整数リストの第二の整数、足す、前記第二の乗算入力整数リストの第二の整数であり、
・前記第二の中間乗算整数リストの第二の整数は、前記第一の乗算入力整数リストの第二の整数、足す、前記第二の乗算入力整数リストの第一の整数である、
請求項９記載の計算装置。
【請求項１１】
・前記可換環が、ある整数を法とする整数によって形成される環である、または
・前記可換環が、ある整数多項式を法とする整数多項式によって形成される環である、
請求項１ないし１０のうちいずれか一項記載の計算装置。
【請求項１２】
環エンコード装置であって、当該環エンコード装置は、
・一つまたは複数の基本環要素について定義されたエンコード・テーブルを記憶するよう構成された記憶部を有しており、前記エンコード・テーブルは、環要素を、環要素が前記一つまたは複数の基本環要素の冪乗の線形結合に等しいように整数リストにマッピングするものであり、前記冪乗は前記整数リストによって決定される指数をもち、
当該環エンコード装置は、
・コンピュータ・ネットワークを通じて、エンコードされた情報を受領するよう構成されている請求項１記載の計算装置と一緒に使うために、可換環の環要素を整数リストとしてエンコードするよう構成されている、
環エンコード装置。
【請求項１３】
環デコード装置であって、当該環デコード装置は、
・コンピュータ・ネットワークを通じて、エンコードされた情報を受領するよう構成されている請求項１記載の計算装置と一緒に使うために、整数リストを可換環の環要素にデコードし、
・一つまたは複数の基本環要素について、前記環要素を、前記環要素が一つまたは複数の基本環要素の冪乗の線形結合に等しいように決定するよう構成されており、前記冪乗は前記整数リストによって決定される指数をもつ、
環デコード装置。
【請求項１４】
可換環において難読化された算術を実行するための計算装置において使うための増分テーブルを計算するテーブル計算装置であって、前記環は有限個の環要素をもち、環要素に対して環加算および環乗算が定義されており、前記計算装置は、環要素をエンコードする整数リストに対して作用し、前記整数リストは少なくとも二つ整数を有し、当該テーブル計算装置は、
・増分テーブルを構築するよう構成されたテーブル生成ユニットを有し、前記テーブル生成ユニットは、
・入力環要素を反復的に選択し、
・固定した増分環要素が前記入力環要素に環加算されたものに等しい出力環要素を決定し、
・前記出力環要素についてエンコードする出力整数リストを決定し、
・前記入力環要素を前記出力整数リストにマッピングするエントリーを増分テーブルに追加するよう構成されており、
当該テーブル計算装置は、構築された増分テーブルを前記計算装置内に記憶するよう構成されている、
テーブル計算装置。
【請求項１５】
可換環において難読化された算術を実行するための電子的な計算方法であって、前記環は有限個の環要素をもち、環要素に対して環加算および環乗算が定義されており、当該計算方法は、環要素をエンコードする整数リストに対して作用し、前記整数リストは少なくとも二つ整数を有し、整数リストは、環要素を、該環要素が一つまたは複数の基本環要素の冪乗の線形結合に等しくなるようエンコードし、前記冪乗は該整数リストによって決定される指数をもち、当該計算方法は、
・増分環要素について定義された増分テーブルを記憶する段階であって、前記増分テーブルは、出力環要素が固定した増分環要素が入力環要素に環加算されたものに等しくなるよう入力環要素を出力環要素をエンコードする出力整数リストにマッピングする、段階と、
・環加算する段階であって、前記環加算は、
・第一の加算入力環要素をエンコードする第一の加算入力整数リストおよび第二の加算入力環要素をエンコードする第二の加算入力整数リストを受領し、
・前記第一および第二の加算入力整数リストから決定される環要素に前記増分テーブルを適用することによって加算出力環要素をエンコードする加算出力整数リストを決定することを含み、前記加算出力環要素は前記第一の加算入力環要素および前記第二の加算入力環要素の環加算に等しく、
前記加算出力整数リストを決定することが、
・一つまたは複数の基本元の冪乗の線形結合である環要素への前記増分テーブルの第一の適用によって、中間加算環要素をエンコードする中間加算整数リストを決定する段階であって、前記冪乗は前記第一および第二の加算入力整数リストから決定される、段階と、
・前記加算出力整数リストを決定する段階であって、前記中間加算整数リストから決定されるおよび前記第二の加算入力整数リストから決定される環要素への前記増分テーブルの第二の適用を含む、段階とを含む、
電子的な計算方法。
【請求項１６】
環乗算する段階を含み、前記環乗算は、
・第一の乗算入力環要素をエンコードする第一の乗算入力整数リストおよび第二の乗算入力環要素をエンコードする第二の乗算入力整数リストを受領し、
・前記第一および第二の乗算入力整数リストから決定される環要素に前記増分テーブルを適用することによって乗算出力環要素をエンコードする乗算出力整数リストを決定することを含み、前記乗算出力環要素は前記第一の乗算入力環要素および前記第二の乗算入力環要素の環乗算に等しい、
請求項１５記載の電子的な計算方法。
【請求項１７】
プログラム可能な装置で実行されたときに請求項１５または１６記載の方法を実行するよう構成されているコンピュータ・プログラム命令を有するコンピュータ・プログラム。
【請求項１８】
・請求項１７記載のコンピュータ・プログラムを有する、
コンピュータ可読媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
環要素cは、第一の加算入力環要素aに、基本元uの、第二の加算入力整数リスト、特に第二の加算入力整数リストの最初の整数から決定される冪乗を加えたものであってもよい。この例では、c＝ua1−ua2＋ub1としてもよい。これを計算するには、c＝ua1−ua2＋ub1＝(ua1-b1−ua2-b1＋1)ub1であることを観察する。括弧内の項は、増分テーブルを使うエンコードにおいて書き直されてもよい。環要素ua1-b1−ua2-b1への増分テーブルの第一の適用を通じて、要素ud1−ud2＝ua1-b1−ua2-b1＋1が得られる。たとえば、T((a1−b1,a2−b1))＝(d1,d2)による。すると、c1＝d1＋b1およびc2＝d2＋b1が得られる。このように、中間加算整数リスト（(c1,c2)）を決定することはさらに、第二の加算入力整数リストから決定された整数を第一の適用から帰結する整数リストにおける整数に加算することを含んでいてもよい。ub1を整数リスト表現におけるある環要素に、この場合はaに加えることは、時に、正の還元（positive  reduction）ステップと称される。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００７２
【補正方法】変更
【補正の内容】
【００７２】
この例では、加算出力整数リストは、中間加算整数リストおよび第二の加算入力整数リストから決定された環要素への増分テーブルの第二の適用を通じて決定されてもよい。これは、中間加算環要素cと、基本元を第二の加算入力整数リスト、たとえば第二の加算入力整数リストの第二の整数b2から決定される冪乗にしたもののマイナスとの和を計算することを含んでいてもよい：c−ub2＝uc1−uc2−ub2。これは、増分テーブルの第二の適用前に、中間加算整数リストによって表わされる中間加算環要素を否定にすることによって達成されてもよい。cの否定は、上記のようになされてもよい。例として並べ替えを使うが、同じ動作は、指数に定数を加えることによって実行されてもよい。否定後は、前記和は、基本元を第二の加算入力整数リストから決定される冪乗にしたもののプラス（マイナスではなく）を使ってもよい：−c＋ub2＝uc2−uc1＋ub2。この演算は上記と同じ型であり、ub1を加えるのと同じ仕方でテーブル適用を通じて実行できる。この後は、結果が再び否定にされる。完全な加算は、二回の否定と同じ増分テーブルTの二回のテーブル適用を使ってもよい。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０１３５
【補正方法】変更
【補正の内容】
【０１３５】
請求項では、括弧内の参照符号は実施形態の図面における参照符号または実施形態の公式を指し、それにより請求項の理解しやすさを増す。これらの参照は網羅的ではなく、請求項を限定するものと解釈してはならない。
いくつかの態様を記載しておく。
〔態様１〕
可換環（Zn；Zn[x]/f(x)）において算術を実行するための電子計算装置であって、前記環は有限個の環要素をもち、環要素に対して環加算および環乗算が定義されており、当該計算装置は、環要素（ua1−ua2）をエンコードする整数リスト（(a1,a2)）に対して作用し、前記整数リストは少なくとも二つ整数を有し、整数リスト（(a1,a2)）は、環要素（a）を、該環要素が一つまたは複数の基本環要素（u；u,v）の冪乗の線形結合に等しくなる（a＝ua1−ua2；a＝ua1−va2）ようエンコードし、前記冪乗は該整数リストによって決定される指数をもち、当該計算装置は、
・増分環要素（1；ut）について定義された増分テーブル（T）を記憶するよう構成された記憶部を有しており、
・前記増分テーブルは、出力環要素が増分環要素が入力環要素に環加算されたものに等しくなる（l＝k＋1）よう入力環要素（k＝uk1−uk2）を出力環要素（l＝ul1−ul2）をエンコードする出力整数リストにマッピングし（T((k1,k2))＝(l1,l2)）、
当該計算装置はさらに、環加算ユニットを有しており、前記環加算ユニットは、
・第一の加算入力環要素をエンコードする第一の加算入力整数リスト（(a1,a2)）および第二の加算入力環要素をエンコードする第二の加算入力整数リスト（(b1,b2)）を受領する段階であって、前記増分環要素は前記第一および第二の加算入力環要素から独立である、段階と、
・前記第一および第二の加算入力整数リストから決定される環要素に前記増分テーブルを適用することによって加算出力環要素をエンコードする加算出力整数リストを決定する段階であって、前記加算出力環要素は前記第一の加算入力環要素および前記第二の加算入力環要素の環加算に等しい、段階とを実行するよう構成されている、
計算装置。
〔態様２〕
環乗算ユニットをさらに有しており、前記環乗算ユニットは、
・第一の乗算入力環要素をエンコードする第一の乗算入力整数リスト（(r1,r2)）および第二の乗算入力環要素をエンコードする第二の乗算入力整数リスト（(s1,s2)）を受領する段階と、
・前記第一および第二の乗算入力整数リストから決定される環要素に前記増分テーブルを適用することによって乗算出力環要素をエンコードする乗算出力整数リストを決定する段階であって、前記乗算出力環要素は前記第一の乗算入力環要素および前記第二の乗算入力環要素の環乗算に等しい、段階とを実行するよう構成されている、
態様１記載の計算装置。
〔態様３〕
前記整数リスト（(a1,a2)）が環要素（a）をエンコードする仕方は、
・前記環要素が、基本元を前記整数リストの第一の整数によって決定される冪乗にしたものから、前記基本元を前記整数リストの第二の整数によって決定される冪乗にしたものを引いたもの（a＝ua1−ua2）に任意的に定数を乗算したもの（a＝t(ua1−ua2)）に等しくなるようにする、または
・前記環要素が、前記基本元を前記整数リストの第一の整数によって決定される冪乗にしたものに、前記基本元を前記整数リストの第二の整数によって決定される冪乗にしたものを足したもの（a＝ua1＋ua2）に任意的に定数を乗算したものに等しくなるようにする、または
・前記環要素が、前記基本元を前記整数リストの第一の整数によって決定される冪乗にしたもの、かける、前記基本元を前記整数リストの第二の整数によって決定される冪乗にしたものから、前記基本元を前記整数リストの第二の整数のマイナスによって決定される冪乗にしたものを引いたもの（a＝ua1(ua2−u-a2)）に任意的に定数を乗算したもの（a＝ua1(ua2−u-a2)/2）に等しくなるようにする、または
・前記環要素が、前記基本元を前記整数リストの第一の整数および第二の整数の第一の線形結合である冪乗にしたもの、足すまたは引く、前記基本元を前記第一の整数および前記第二の整数の第二の線形結合である冪乗にしたもの（行列Mを与えられて
【数１１】
2017533458.tif 000001
となるようなx＝ub1＋ub2またはx＝ub1−ub2）に任意的に定数を乗算したものに等しくなるようにするものである、
態様１または２記載の計算装置。
〔態様４〕
前記加算出力整数リストを決定することが、
・一つまたは複数の基本元の冪乗の線形結合である環要素（ua1-b1−ua2-b1）への前記増分テーブルの第一の適用によって、中間加算環要素をエンコードする中間加算整数リスト（(c1,c2)）を決定する段階であって、前記冪乗は前記第一および第二の加算入力整数リストから決定される、段階（uc1−uc2＝ua1−ua2＋ub1）と、
・前記加算出力整数リストを決定する段階であって、前記中間加算整数リストから決定されるおよび前記第二の加算入力整数リストから決定される環要素への前記増分テーブルの第二の適用を含む、段階とを含む、
態様１または３記載の計算装置。
〔態様５〕
前記中間加算整数リスト（(c1,c2)）を決定することがさらに、前記第一および第二の加算入力整数リストから決定された整数を、第一の適用から帰結する整数リスト中の整数に加算することを含む、態様４記載の計算装置。
〔態様６〕
・前記増分テーブルは、前記一つまたは複数の基本環要素（u）を前記第一の整数リストの第一の整数（a1）から前記第二の整数リストの第一の整数（b1）を引いたもの乗したもの、足すまたは引く、ある基本環要素（u）を前記第一の整数リストの第二の整数（a2）から前記第二の整数リストの第一の整数（b1）を引いたもの乗したもの、によって形成される環要素（ua1-b1−ua2-b1；ua1-b1＋ua2-b1）に適用される、および／または
・前記増分テーブルは、前記一つまたは複数の基本環要素（u）を前記第一の整数リストの前記第一の整数（a1）から前記第一の整数リストの第二の整数（a2）を引いたもの乗したもの、足すまたは引く、ある基本環要素（u）を前記第二の整数リストの第一の整数（b1）から前記第一の整数リストの前記第二の整数（a2）を引いたもの乗したもの、によって形成される環要素（ua1-a2＋ub1-a2；ua1-a2＋ub1-a2）に適用される、および／または
・前記増分テーブルは、前記一つまたは複数の基本環要素（u）を前記第一の整数リストの第二の整数（a2）から前記第一の整数リストの第一の整数（a1）を引いたもの乗したもの、足すまたは引く、ある基本環要素（u）を前記第二の整数リストの第一の整数（b1）から前記第一の整数リストの前記第一の整数（a1）を引いたもの乗したもの、によって形成される環要素（ub1-a1−ua2-a1；ua2-a1＋ub1-a1）に適用される、
態様４または５記載の計算装置。
〔態様７〕
・前記増分テーブルの前記第二の適用の前に、前記中間加算整数リストによって表わされる前記中間加算環要素が否定にされる、
態様４ないし６のうちいずれか一項記載の計算装置。
〔態様８〕
・整数リストによって表わされる環要素が、該整数リストを並べ替えることによって否定にされる、および／または
・整数リストによって表わされる環要素が、該整数リストの各整数に定数を加えるることによって否定にされる、および／または
・整数リスト（(a1,a2)）によって表わされる環要素が、該整数リストを並べ替え、該整数リストの一つまたは複数の整数に定数を乗算する（(sa2,ta1)）ことによって否定にされる、
態様１ないし７のうちいずれか一項記載の計算装置。
〔態様９〕
前記増分テーブルが、前記入力環要素（k＝uk1−uk2）を表わす入力整数リスト（(k1,k2)）を入力として取る、態様１ないし８のうちいずれか一項記載の計算装置。
〔態様１０〕
乗算出力整数リストを決定することが、
・前記第一および第二の乗算入力整数リストから、それぞれ第一および第二の中間乗算還要素をエンコードする第一の中間乗算整数リスト（(t1,t2)）および第二の中間乗算整数リスト（(u1,u2)）を決定し、
・前記第一および第二の中間乗算整数リストを前記環加算ユニットを通じて加算することを含む、
態様２記載の計算装置。
〔態様１１〕
・前記第一の中間乗算整数リストの第一の整数（t1）は、前記第一の乗算入力整数リストの第一の整数（r1）、足す、前記第二の乗算入力整数リストの第一の整数（s1）であり、
・前記第一の中間乗算整数リストの第二の整数（t2）は、前記第一の乗算入力整数リストの第一の整数（r1）、足す、前記第二の乗算入力整数リストの第二の整数（s2）であり（t1＝r1＋s1、t2＝r1＋s2）、
・前記第二の中間乗算整数リストの第一の整数（u1）は、前記第一の乗算入力整数リストの第二の整数（r2）、足す、前記第二の乗算入力整数リストの第二の整数（s2）であり、
・前記第二の中間乗算整数リストの第二の整数（u2）は、前記第一の乗算入力整数リストの第二の整数（r2）、足す、前記第二の乗算入力整数リストの第一の整数（s1）である（u1＝r2＋s2、u2＝r2＋s1）、
態様１０記載の計算装置。
〔態様１２〕
・前記可換環が、ある整数を法とする整数によって形成される環（Zn）である、または
・前記可換環が、ある整数多項式を法とする整数多項式によって形成される環（Zn[x]/f(x)）である、
態様１ないし１１のうちいずれか一項記載の計算装置。
〔態様１３〕
態様１記載の計算装置と一緒に使うための、可換環（Zn；Zn[x]/f(x)）の環要素を整数リストとしてエンコードする環エンコード装置であって、当該環エンコード装置は、
・一つまたは複数の基本環要素（u）について定義されたエンコード・テーブルを記憶するよう構成された記憶部を有しており、前記エンコード・テーブルは、環要素（x）を、環要素が前記一つまたは複数の基本環要素の冪乗の線形結合に等しい（x＝ua−ub）ように整数リスト（(a,b)）にマッピングするものであり、前記冪乗は前記整数リストによって決定される指数をもつ、
環エンコード装置。
〔態様１４〕
態様１記載の計算装置と一緒に使うための、整数リスト（(a,b)）を可換環（Zn；Zn[x]/f(x)）の環要素（x）にデコードする環デコード装置であって、当該環デコード装置は、一つまたは複数の基本環要素（u）について、前記環要素（x）を、前記環要素が一つまたは複数の基本環要素の冪乗の線形結合に等しい（x＝ua−ub）ように決定するよう構成されており、前記冪乗は前記整数リストによって決定される指数をもつ、
環デコード装置。
〔態様１５〕
可換環（Zn；Zn[x]/f(x)）において算術を実行するための計算装置において使うための増分テーブルを計算するテーブル計算装置であって、前記環は有限個の環要素をもち、環要素に対して環加算および環乗算が定義されており、前記計算装置は、環要素（ua1−ua2）をエンコードする整数リスト（(a1,a2)）に対して作用し、前記整数リストは少なくとも二つ整数を有し、当該テーブル計算装置は、
・増分テーブルを構築するよう構成されたテーブル生成ユニットを有し、前記テーブル生成ユニットは、
・入力環要素を反復的に選択し、
・増分環要素が前記入力環要素に環加算されたものに等しい出力環要素を決定し、
・前記出力環要素についてエンコードする出力整数リストを決定し、
・前記入力環要素を前記出力整数リストにマッピングするエントリーを増分テーブルに追加するよう構成されている、
テーブル計算装置。
〔態様１６〕
可換環（Zn；Zn[x]/f(x)）において算術を実行するための電子的な計算方法であって、前記環は有限個の環要素をもち、環要素に対して環加算および環乗算が定義されており、当該計算方法は、環要素（ua1−ua2）をエンコードする整数リスト（(a1,a2)）に対して作用し、前記整数リストは少なくとも二つ整数を有し、整数リスト（(a1,a2)）は、環要素（a）を、該環要素が一つまたは複数の基本環要素（u；u,v）の冪乗の線形結合に等しくなる（a＝ua1−ua2；a＝ua1−va2）ようエンコードし、前記冪乗は該整数リストによって決定される指数をもち、当該計算方法は、
・増分環要素（1；ut）について定義された増分テーブル（T）を記憶する段階であって、前記増分テーブルは、出力環要素が増分環要素が入力環要素に環加算されたものに等しくなる（l＝k＋1）よう入力環要素（k＝uk1−uk2）を出力環要素（l＝ul1−ul2）をエンコードする出力整数リストにマッピングする（T((k1,k2))＝(l1,l2)）、段階と、
・環加算する段階であって、前記環加算は、
・第一の加算入力環要素をエンコードする第一の加算入力整数リスト（(a1,a2)）および第二の加算入力環要素をエンコードする第二の加算入力整数リスト（(b1,b2)）を受領し、
・前記第一および第二の加算入力整数リストから決定される環要素に前記増分テーブルを適用することによって加算出力環要素をエンコードする加算出力整数リストを決定することを含み、前記加算出力環要素は前記第一の加算入力環要素および前記第二の加算入力環要素の環加算に等しい、
電子的な計算方法。
〔態様１７〕
環乗算する段階を含み、前記環乗算は、
・第一の乗算入力環要素をエンコードする第一の乗算入力整数リスト（(r1,r2)）および第二の乗算入力環要素をエンコードする第二の乗算入力整数リスト（(s1,s2)）を受領し、
・前記第一および第二の乗算入力整数リストから決定される環要素に前記増分テーブルを適用することによって乗算出力環要素をエンコードする乗算出力整数リストを決定することを含み、前記乗算出力環要素は前記第一の乗算入力環要素および前記第二の乗算入力環要素の環乗算に等しい、
態様１６記載の電子的な計算方法。
〔態様１８〕
プログラム可能な装置で実行されたときに態様１６または１７記載の方法を実行するよう構成されているコンピュータ・プログラム命令を有するコンピュータ・プログラム。
〔態様１９〕
・態様１８記載のコンピュータ・プログラム、および／または
・態様１記載の電子計算装置によって使用される前記増分テーブルを有する、
コンピュータ可読媒体。