Currently, when GAP is calculating the minimum distance, it examines the weight of every possible linear combination of rows in . The following algorithm is much faster.

- After replacing by a permutation equivalent ,
one may assume the generator matrix has the following form
, for some
matrix .
- Find the minimum distance of the code spanned by the rows of . Call this
distance . Note that is equal to the
where
is some proper
^{2}linear combination of distinct rows of . - , where is as in step (2).

Though this is still an exponential time algorithm problem, the
vectors being compared are of length rather than length .
There was an increase in speed by a factor over
1000 in some examples^{3}. Additionally, this algorithm works for all
Galois fields of order .

The probabilistic algorithm used to reduce this to polynomial time was initially proposed by J. S. Leon [LEO] and later modified by F. Chabaud [CHA]. One iteration of the algorithm given in Chabaud's paper is as follows:

- (1)
- Find a generator matrix of .
- (2)
- Randomly permute the columns of .
- (3)
- Perform Gaussian elimination on the permuted matrix to obtain a
new matrix of the following form:
(3)

with a matrix. - (4)
- Search
for at most rows that lead to codewords of
weight less than .
- (5)
- For these codewords, compute the weight of the whole word.

However, sometimes step (3) is impossible because gaussian elimination does not always produce a matrix in standard form. For example, take any code with generator matrix in row reduced echelon form which is not of the form .

Here is a faster version of Leon's algorithm that was discovered jointly with my advisor in the process of working on this project.

- (1)
- Replace, if necessary, by a permutation equivalent code
with a generator matrix in standard form,
.
- (2)
- Select columns at random from the matrix and call
the resulting matrix .
- (3)
- For each
, find the linear combination of exactly
rows of
for vectors of smallest weight.
- (4)
- For these vectors, compute the weight of the associated codeword.
- (5)
- Find the minimum weight of the codewords from (4). Call this
.
- (6)
- Repeat this algorithm some multiple times and return the most commonly occurring value of .

Chabaud [CHA] and Barg [BARG] have discussed finding optimal values for , , and . We have selected to be , to be 3, and to be since those values seem optimal for codes of length less that .

To perform step (4), the row numbers and coefficients must be saved from step (3). However, the standard command in GAP (written in the C programming language and part of the GAP kernel) for searching through row combinations for a weight does not return this data. In the binary case, an algorithm for finding minimum weight is simply a matter of examining the sum of up to row combinations. A relatively fast implementation (in GAP) of this algorithm has been written in the binary case. However, for codes over , especially if is moderately large, a fast implementation of this algorithm requires modifying the standard GAP command. Since this command is part of the kernel, it will also be necessary to recompile GAP before it can be used in any implementation. This coding in the C programming language has not yet been implemented.