Bibliothèque d'algèbre linéaire exacte à grand champ fini (par exemple GF(2^128) / GF(2^256) )

Question

General

Je cherche une bibliothèque capable d'effectuer des calculs exacts sur de grands champs finis tels que GF(2). 128 )/ _{2 ¹²⁸} et GF(2 256 )/ _{2 ²⁵⁶} . J'ai listé ci-dessous les fonctionnalités dont j'ai besoin et celles qui seraient cool. Évidemment, la bibliothèque doit être aussi rapide que possible :-). Ah, puisque je ne suis pas un maître du C++ (et que probablement la plupart des bibliothèques sont en C++), un exemple de code de disons générer un élément aléatoire/une constante et le multiplier par son inverse multiplicatif

Caractéristiques indispensables

• Ajout d'éléments de terrain
• Multiplication de l'élément de champ
• Trouver l'inverse multiplicatif d'un élément de champ

Caractéristiques utiles

• Support des vecteurs/matrices
• Support des éléments aléatoires

Les bibliothèques que j'ai déjà regardées et qui seront probablement no travail

• FFLAS/FFPACK semble ne pas fonctionner avec des champs finis aussi grands.
• Givaro semble ne pas fonctionner sur des champs finis aussi grands.

Les bibliothèques, j'ai déjà regardé ça pourrait fonctionnent (mais je n'ai pas pu les utiliser)

• NTL je n'ai pas réussi à inverser un élément, mais cela devrait fonctionner puisque SAGE semble utiliser cette bibliothèque lors de la définition de GF(2^256) et là, un élément peut être inversé en utilisant x^(-1)
• PARI/GP Je n'ai pas réussi à trouver tout ce dont j'ai besoin dans la documentation, mais la documentation de SAGE indique que cela devrait fonctionner.

Autres notes

• J'écris un programme Haskell et j'interfacerai cette bibliothèque plus tard, donc un interfaçage Haskell plus facile est préférable :-)

Answer 1

La bibliothèque NTL semble fonctionner, en utilisant ce code (désolé, je suis incapable de programmer en C++)

#include <NTL/GF2E.h>
#include <NTL/GF2EX.h>
#include <NTL/GF2X.h>
#include <NTL/GF2XFactoring.h>

NTL_CLIENT

int main()
{
    GF2X P = BuildIrred_GF2X(256);
    GF2E::init(P);

    GF2E zero = GF2E::zero();
    GF2E one;
    GF2E r = random_GF2E();
    GF2E r2 = random_GF2E();
    conv(one, 1L);
    cout << "Cardinality: " << GF2E::cardinality() << endl;
    cout << "ZERO: " << zero << " --> " << IsZero(zero) << endl;
    cout << "ONE:  " << one  << " --> " << IsOne(one)   << endl;
    cout << "1/r:  " << 1/r  << ", r * (1/r): " << (r * (1/r)) << endl;
    cout << "1/r2:  " << 1/r2  << ", r2 * (1/r2): " << (r2 * (1/r2)) << endl;
}

cela semble fonctionner, la preuve (sortie de ce programme) :

Cardinality: 115792089237316195423570985008687907853269984665640564039457584007913129639936
ZERO: [] --> 1
ONE:  [1] --> 1
1/r:  [0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 1 0 1 0 1 0 0 0 0 1 1 0 0 1 1 1 0 1], r * (1/r): [1]
1/r2:  [1 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1 0 1 0 0 1 1], r2 * (1/r2): [1]

Même l'inversion semble fonctionner (défilement le plus à droite possible dans l'exemple de sortie ci-dessus) :-)