問題タブ [finite-field]

Haskell 用の有限体線形代数ライブラリを探しています。

Haskell 用の FFLAS-FFPACKのようなものは素晴らしいでしょう :-)。

もちろん、hmatrixをチェックしました。任意の行列要素タイプがサポートされているようですが、hmatrix で動作する有限体ライブラリが見つかりませんでした。そして確かに私はパフォーマンスの高いソリューションに感謝します:-)

_{特に、 p} ^n×1および_p ^1×m行列 (ベクトル) を_p ^n×m行列に乗算できるようにしたいと考えています。

Cの有限体/ガロア体の正確な線形代数ライブラリを探しています（C ++にはHaskellバインディングを記述できる必要があるため、C ++は受け入れられません。これは、C ++では明らかに困難です）。

FFLAS-FFPACKやGivaroなどのライブラリを見つけましたが、これらはC++テンプレートライブラリです:-(

_{特に、 pn} ^×1と_p1 ^×mの行列（ベクトル）を_pn ^×mの行列に乗算できるようにしたいと思います。

それで、誰かが適切なCまたは「外部C」ライブラリを知っていますか？

PS：これが同じ問題についての私のHaskellの質問です。

計算できるようになりたい

ここで、gは有限体GF（2 ^ m）にあります。ここで、mはかなり大きく、m = 256、384、512などであるため、ルックアップテーブルは解決策ではありません。同様のアイデア、Z / nZ用のmodpow（ HACの619〜620ページを参照）には非常に高速なアルゴリズムがあることを私は知っています。

1. サイクル（つまりg ^ x）を計算するための高速で非テーブルベースの方法は何ですか？
2. これは間違いなく希望に満ちた質問ですが、ここに来ます。モンゴメリの乗算/べき乗のアイデアをガロア体に「リサイクル」できるでしょうか。同型性があるのでそう思いたいのですが、よくわかりません。

備考：これはmath.stackoverflow.comへの私の投稿からのものです。これがこの質問をするのに最適なコミュニティだと思います。

全般的

^{GF(2 128} )/ _{2 ¹²⁸}や GF(2 ²⁵⁶ )/ _{2 ²⁵⁶}などの大きな有限体で正確な計算を実行できるライブラリを探しています。以下に、必要な機能とクールな機能をリストしました。明らかに、ライブラリは可能な限り高速であるべきです:-)。ああ、私は C++ の達人ではないので (そしておそらくほとんどのライブラリは C++ です)、ランダムな要素/定数を生成し、それを乗法逆数に乗算するサンプル コードです。

必須機能

• フィールド要素の追加
• 体の元のかけ算
• 体の元の乗法逆数を求める

機能があると便利

• ベクトル/行列のサポート
• ランダム要素のサポート

私がすでに見たライブラリはおそらく機能しないでしょう

• FFLAS/FFPACKは、そのような大きな有限フィールドでは機能しないようです
• Givaroは、そのような大きな有限フィールドでは機能しないようです

私がすでに見たライブラリは機能する可能性があります（ただし、使用できませんでした）

• NTL、要素を反転することはできませんでしたが、GF(2^256) を定義するときにSAGEがこのライブラリを使用しているようで、要素を使用して反転できるため、実際には機能するはずです。x^(-1)
• PARI/GP、ドキュメントで必要なものをすべて見つけることができませんでしたが、SAGEドキュメントには、それが機能するはずだと書かれています

その他の注意事項

• 私はHaskellプログラムを書いており、後でそのライブラリとインターフェースする予定なので、Haskellインターフェースはより簡単です:-)

私は C# で AES を実装していますが、ある時点 (MixColumns 関数) で、GF(2^8) 有限体で 2 バイトを乗算する必要があります。

したがって、次の 3 つのオプションがあります。

• dotNet が持っているデフォルトの関数を使用します (そのようなものはありますか?)
• それを行うカスタム関数を書く
• ルックアップ テーブルを使用する

カスタム関数については、C# 用に書き直そうとした C コードの一部を見つけましたが、機能しません (間違った結果が得られます)。(*)

元の C コード ( source ) は次のとおりです。

そして、これは私が書き直したものです：

また、いくつかのルックアップ テーブルを見つけました ここ、それは単純で優れたアプローチのように見えましたが、私はそれらを使用する方法をよく知りません。(**)

要するに、どのオプションを選択する必要があり、どのように機能させることができるかということです.これまでに書いたことがすべてであり、数学の知識を深く掘り下げたいとは思っていません.

アップデート：

*)その間、C# で書き直したコードが正しい答えを生成していることに気付きました。それは、検証時に失敗したため、私のせいでした。

**)テーブルは Byte[256] 配列として使用できます。たとえば、テーブル配列のインデックスとして使用するx*3とtable_3[x]、xHEX から DECIMAL に変換されます。

C++でのガロア体演算の実装を知っていますか? 少なくとも GF(2 ¹⁶ ) と GF(2 ³² ) のようなケースをカバーする必要があります。パフォーマンスが懸念されるため、実装では操作の最適化を検討する必要があります。

一般的な計算ライブラリか、このタスク専用の小さなライブラリの方がいいと思います。これらが不足しているため、読み取り可能なソース コードも歓迎します。

m * nのバイナリ行列A、m * pのバイナリ行列Bが与えられます。ここで、n> m AX=BとなるようにXを計算するための効率的なアルゴリズムは何ですか。

例えば：

私がバイナリ行列と言うとき、私は体Z_2で定義された行列を意味することに注意してください。つまり、すべての算術はmod2です。

興味がある場合、これはランダムエラー訂正コードに適した行列を生成する際に私が直面している問題です。

vbaでQRコードを生成する関数に取り組んでいます。私はこのチュートリアルに従っています。私は現在、このステップで誤り訂正語を生成する作業を行っています。これには GF(256) ログ/アンチログ テーブルが必要です。こちらを参照してください。テーブル全体を入力する必要はありません。これらのテーブルを生成するために使用される関数を誰かが知っているので、それらを配列に格納できますか? チュートリアルには、テーブルの生成方法へのリンクがありましたが、壊れていました。

先に言っておきますが、これはアクセスで実行するので、エクセルへの貼り付けがうまくいきません。しかし、これを書いているときに、アクセス テーブルを使用できることに気づきました。私はそれをすべてコードで行うことを好みますが。

16 ビット CPU で有限素体の多項式を解く必要があります。GF((2^16)+1), GF((2^16)-15)フィールド、およびを使用している人々を見てきましたGF((2^32)-5)。これらの選択は、いくつかの最適化があるという事実から生じていると思います。ただし、「mod」の使用を除けば、それ以上の最適化はわかりません。誰かが私に良いリソースを教えてくれたり、コード スニペットをくれたり、人々がなぜこれらの奇妙な素数をGF((2^16)-1).

編集: GF((2^16)+1) の % フリー モジュロ:

編集: GF(2^16-15) の % フリー モジュロ:

更新: MSP430 でパフォーマンスを測定しました: 上位バージョンは下位バージョンよりも 4 倍高速です。下位バージョンは、単純に % :/ を使用するのと同じくらい高速です。下位バージョンを高速化するためのその他の提案はありますか?

乾杯コンラッド

GF(2) 有限体の多項式を読み取ろうとしていますが、これは基本的に係数または定数に対して 1 または 0 のみであり、多項式の 1 つの部分を他の部分と実際に区別する唯一の数値は指数です。しかし、指数は、結果のリスト内の場所の「場所」またはインデックスのみをマークすることになり、1 としてのみマークされます。結果のリスト内の他のすべての位置は 0 です。

例を含むいくつかのコード:

ご覧のとおり、次のように出力されます。

ただし、リストの先頭に 1 を出力する必要があります (多項式の次数は左から右に高から低になり、リストも同様です)。それが最高度なので、長さは正しいです。私は今、独学で Python を学んでいるので、プロの Python 関係者は私のコードにうんざりしていると思います。プロの方には、初心者の習慣をできるだけ早く取り除こうとしているので、より Pythonic な解決策や建設的な何かを提案してください。後でこれを関数に入れます (実際には、クラス内の関数に入ります)。これは、基本的な考え方を理解するためのものです。

編集：

以下の回答から（コードの一部だけのアイデアを信用していません）、Pythonicのように見えますが、正規表現を使用して抽出してintに変換するコードを最適に統合する方法がわかりません（cリスト内） ):

このコードを合理化し、より Pythonic にする方法を考えています。