Stack Overflow
Stack Overflow

Questions tagged [finite-field]

In algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains a finite number of elements.

In algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains a finite number of elements, called its order (the size of the underlying set). As with any field, a finite field is a set on which the operations of commutative multiplication, addition, subtraction and division (by anything except zero) have been defined.

Read more: http://en.wikipedia.org/wiki/Finite_field

78 questions
18
votes
1 answer

Exact Large Finite Field Linear Algebra Library (e.g. GF(2^128) / GF(2^256) )

General I'm looking for a library that is able to do exact calculations on large finite fields such as GF(2128)/2128 and GF(2256)/2256. I listed the features that I need and the features that would be cool below. Obviously, the library should be as…
Johannes Weiss
  • 52,533
  • 16
  • 102
  • 136
16
votes
1 answer

Python -- matplotlib elliptic curves

I'm teaching myself about matplotlib and Python and I'm having a difficult time plotting an equation for an elliptic curve. I have the equation down but I'm not doing the y^2 This is as much trouble as I was able to get myself into so far: from…
stackuser
  • 869
  • 16
  • 34
12
votes
1 answer

SymPy polynomials over finite fields

import sympy as S F = S.FiniteField(101) When I call f = S.poly(y ** 2 - x ** 3 - x - 1,F) I get the following error: 'FiniteField' object has no attribute 'is_commutative' But finite fields are commutative by definition! So I'm not really sure…
Kevin Johnson
  • 820
  • 11
  • 24
11
votes
1 answer

Solving sparse system over GF(q)

I am interested in solving large (n up to 10^5 or maybe even 10^6) rectangular (maybe 10% more columns than rows) sparse (< 10 nonzeros per row) systems Ax = b over a finite field GF(q) (q might be a prime near 1000 or so). From the literature, it…
Robert Israel
  • 173
  • 6
10
votes
1 answer

Finite Field Linear Algebra Library for Haskell

I'm searching for a finite field linear algebra library for Haskell. Something like FFLAS-FFPACK for Haskell would be great :-). Of course, I checked hmatrix, there seems to be some support for arbitrary matrix element types but I couldn't find any…
Johannes Weiss
  • 52,533
  • 16
  • 102
  • 136
9
votes
1 answer

Implementing FFT over finite fields

I would like to implement multiplication of polynomials using NTT. I followed Number-theoretic transform (integer DFT) and it seems to work. Now I would like to implement multiplication of polynomials over finite fields Z_p[x] where p is arbitrary…
minmax
  • 493
  • 3
  • 10
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
8
votes
1 answer

Finite Field (Galois Field) Linear Algebra Library for C (not C++)

I'm searching for a finite field/galois field exact linear algebra library for C (C++ is not acceptable because I need to be able to write a Haskell-binding to it and that's apparently difficult with C++). I found libraries for like FFLAS-FFPACK and…
Johannes Weiss
  • 52,533
  • 16
  • 102
  • 136
6
votes
1 answer

Solving a system of linear equations over the field F(2) with python

Is there a way that I can solve a system of linear equations over the field F2(i.e addition and multiplication modulo 2 - the binary field) using python? I've been trying to search for a useful package for a while but hadn't come up with…
MRm
  • 517
  • 2
  • 14
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

Binary field inversion using SAGE

I am quite frustrated about the SAGE documentations on Finite field operations. What I want to do is the following: In GF(2^8) with irreducible polynomial x^8+x^4+x^3+x+1, I would like to find the inverse of element x^8+1. How can I do that in SAGE?
drdot
  • 3,215
  • 9
  • 46
  • 81
5
votes
2 answers

Python -- Matplotlib for elliptic curve with sympy solve()

I have an elliptic curve plotted. I want to draw a line along a P,Q,R (where P and Q will be determined independent of this question). The main problem with the P is that sympy solve() returns another equation and it needs to instead return a value…
stackuser
  • 869
  • 16
  • 34
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
2 answers

Python linear algebra in a finite field

Is there a way to do linear algebra and matrix manipulation in a finite field in Python? I need to be able to find the null space of a non-square matrix in the finite field F2. I currently can't find a way to do this. I have tried the galois…
fran
  • 43
  • 4
1
2 3 4 5 6