Stack Overflow
Stack Overflow

Questions tagged [galois-field]

Galois field also knows as finite field in abstract algebra is a field that contains a finite number of elements.

A Galois field, also knows as finite field in abstract algebra, is a field that contains a finite number of elements.

A field is an algebraic structure with multiplication and addition, where every element has a multiplicative inverse, and all elements commute with each other.

84 questions
26
votes
3 answers

Errata (erasures+errors) Berlekamp-Massey for Reed-Solomon decoding

I am trying to implement a Reed-Solomon encoder-decoder in Python supporting the decoding of both erasures and errors, and that's driving me crazy. The implementation currently supports decoding only errors or only erasures, but not both at the same…
gaborous
  • 15,832
  • 10
  • 83
  • 102
14
votes
2 answers

Addition and multiplication in a Galois Field

I am attempting to generate QR codes on an extremely limited embedded platform. Everything in the specification seems fairly straightforward except for generating the error correction codewords. I have looked at a bunch of existing implementations,…
captncraig
  • 22,118
  • 17
  • 108
  • 151
11
votes
3 answers

What are the AVX-512 Galois-field-related instructions for?

One of the AVX-512 instruction set extensions is AVX-512 + GFNI, " Galois Field New Instructions". Galois theory is about field extensions. What does that have to do with processing vectorized integer or floating-point values? The instructions…
einpoklum
  • 118,144
  • 57
  • 340
  • 684
9
votes
4 answers

Implementation of Galois field arithmetic

Do you know of an implementation of Galois field arithmetic in C++? At least cases like GF(216) and GF(232) should be covered. Performance is a concern, so the implementation should have given some thought to optimizing its operations. I'd prefer a…
MvG
  • 57,380
  • 22
  • 148
  • 276
6
votes
1 answer

Python multiplicative inverse in GF(2) finite field

These 2 functions perform Extended Euclidean Algorithm, and then find the multiplicative inverse. The order seems right, but it's not coming back with what I'm expecting as per this tool from U of Sydney http://magma.maths.usyd.edu.au/calc/ and…
stackuser
  • 869
  • 16
  • 34
5
votes
2 answers

Interpolate polynomial over a finite field

I want to use python interpolate polynomial on points from a finite-field and get a polynomial with coefficients in that field. Currently I'm trying to use SymPy and specifically interpolate (from sympy.polys.polyfuncs), but I don't know how to…
Avihu28
  • 177
  • 2
  • 8
5
votes
1 answer

How to calculate numpy arrays on galois field?

I want to use numpy array on galois field (GF4). so, I set GF4 class to array elements. It works on array + integer calculation but it dosen't works on array + array calculation. import numpy class GF4(object): """class for galois field""" …
Ryoji Ishii
  • 303
  • 1
  • 4
  • 14
5
votes
6 answers

GCM Multiplication Implementation

I am puting up a C code for the Multiplication of block (Alogrithm 1) in the GCM SP-800-38D document here. Page 11-12. Having completed the code, I want to see if there are any way I can test the code. You can find attached below the code I have put…
Paul A.
  • 449
  • 1
  • 4
  • 22
4
votes
1 answer

What could be the benefit of such a complicated function to test if variable is not zero?

I'm working on my master's thesis (computer science) on code which is written for post-quantum-secure signatures. The whole thing can be found here but is not important here. For my thesis I tried to explain a 'simple' function, which is not so…
linderd
  • 43
  • 4
4
votes
1 answer

How to perform polynomial subtraction and division in galois field

For my Crypto course, I'm given with two polynomials, in compact form and an irreducible polynomial and am asked to perform the 4 basic arithmetic operations in GF(2^8). Accomplished addition and multiplication, I'm now wondering how to approach…
Saf
  • 125
  • 2
  • 10
4
votes
1 answer

Performing matrix-operations (e.g. product and inverse) over GF(2^6) in C++

I want to implement some matrix operations such as product and inverse computation over a Galois Field GF(64) in C++ language. I have normally used Eigen library to perform such operations in double type. In Matlab it is possible to convert a…
DragHenry
  • 41
  • 1
4
votes
2 answers

Data type for finite fields in Haskell?

I'm trying to learn a bit of Haskell by writing a small set of functions for computations over finite (Galois) fields. Years ago I wrote the first version of a similar library for the computer algebra system GNU Maxima (see here) and I thought I'd…
Alasdair
  • 1,300
  • 4
  • 16
  • 28
4
votes
1 answer

Fast Exponentiation for galois fields

I want to be able to compute g^x = g * g * g * ... * g (x times) where g is in a finite field GF(2^m). Here m is rather large, m = 256, 384, 512, etc. so lookup tables are not the solution. I know that there are really fast algorithms for a…
torrho
  • 1,823
  • 4
  • 16
  • 21
3
votes
1 answer

Fast sparse matrix dot multiplication in GF(256) with Scipy.Sparse

I need to enhance the speed of my algorithm. The method takes the two matrices as argument and performs the dot multiplication. The only issue is that the elements have to be multiplied as octets in GF(256) and then added as XOR. Since I'm dealing…
Alessandro
  • 31
  • 2
3
votes
5 answers

Decrypt binary sequence with random binary key. What's wrong with my script?

(Updated Below) Attempting a problem from linear-algebra text Coding the Matrix by Philip Klein. Running into problems brute-forcing the ciphertext binary sequence against all possible keys. Problem 1.5.1, page 57: An 11-symbol message has been…
Duomi
  • 33
  • 4
1
2 3 4 5 6