How can I speed up gfmul for large fields?

I would like to do some arithmetic, like find inverses and do multiplication in the Galois field GF(29^4). The commands gfmul works well for this task for GF(29^3):

p=29;
m=3;
conway = [27 2 0 1]; % conway poly
field = gftuple([-1:p^m-2]',conway,p); % 7072801x4 double
g_e = 28*29^2+29; % exponential form of test case poly
unit=0; % exponential form of unit
tic
ginv_e = gfdiv(unit,g_e,field); % calculate g inverse
toc % 0.29s on my machine
tic
gfmul(ginv_e,g_e,field) % test: answer should be 0 
toc % 0.37s on my machine

But when I try the same thing for p=29 and m=3 it is MUCH slower

p=29;
m=4;
conway = [2 15 2 0 1]; 
field = gftuple([-1:p^m-2]',conway,p);
g_e = 28*29^3+29^2;
unit=0;  
tic
ginv_e = gfdiv(0,g_e,field); 
toc % 7.4s on my machine
tic
gfmul(ginv_e,g_e,field) 
toc % *** 344s on my machine!! ****
% try to mult using coefficients and convolution
g_c = gftuple(g_e,conway,p) % coefficient form of g
ginv_c = gftuple(ginv_e,conway,p) 
tic 
prod = gfconv(ginv_c,g_c,p); % convolution mod p
gftuple(prod,conway,p) % reduce mod conway poly, answer should be 1 0 0 0
toc % 1.2s on my machine

1. Any way to get "gmul(ginv_e,g_e,field)" to go faster? Is it something about the size of the "field" array and how Matlab moves that around in memory?
2. Ideally I'd get gmul to go faster, but there are two work arounds (a) I can perform an equivalent calculation using gfconv, and it's 1.2s. (b) I can work all the way around and use "deconv" followed by reducing modulo p, followed by reducing modulo the conway polynomial, and then reducing mod p again, and the result is 0.017s.

Answer 1

[arushi]

Hi Ethan,

Your observation about the performance issues with "gfmul" for larger field sizes is correct. MATLAB's "gftuple" operation generates a full representation of the Galois field elements, which can become very large and memory-intensive as the field size increases. This can lead to significant computational overhead, especially when performing arithmetic operations like multiplication or inversion.

For Galois fields of size GF(p^m) where m is large, it's often more efficient to use polynomial arithmetic rather than the tuple representation. The "gf" object in MATLAB's Communications Toolbox provides a more memory-efficient way to represent elements of a Galois field and perform arithmetic operations.

By using "gf" objects, MATLAB can handle the arithmetic in a more optimized way, which should be faster than using “gftuple” and “gfmul” for large fields.

Regarding your workaround using “gfconv”, that's a valid approach too, but be aware that it relies on manual polynomial reduction, which can be error-prone if not done carefully. The "gf" object handles all these operations internally and ensures correctness.

Hope this helps.

[Ethan Duckworth]

Thanks for the reply. Unless I'm missing something, the gf tool only generates Galois fields with p=2, and I need p=29.

Also, I know the array is much larger but there's something really dramatic about the slow down, and it really doesn't make sense. Matlab can generate the whole field array, in 1.3 seconds, and it's a 707281 x 4 array, which isn't so large. Finally, once that array is generated, multiplication should be rather trivial: the exponential encoding means that multiplying two elements is the same as adding their row numbers.