Papers for

cryptography software engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Probabilistic method speeds up main step in F4 algorithm

Probably correct row echelon form in the F4 algorithm

Abstract: The computation of row echelon form is one of the main bottlenecks in the F4 algorithm. Several state of the art implementations use a probabilistic algorithm attributed to Monagan, Pearce, and Steel to accelerate this computation. Despite this, no bound on the probability that the algorithm returns an incorrect result appears to be available. In this paper, we provide such a bound. Furthermore, building on this result, we propose a Las-Vegas variant of the F4 algorithm and show experimentally that it can outperform deterministic F4 on some classical examples.

Sun 13 SeptSymbolic ComputationData Structures and Algorithms
The gist
One tough step in the F4 algorithm is changing matrices into row echelon form, which can take a lot of time. Some current fast versions use a chance-based method but didn’t say how often it might mess up. The authors figured out a bound on the chance of error for this method. They also created a version of the F4 that uses randomness but checks its work to avoid mistakes, and showed it can run faster on standard problems.
Open → 2609.14433v1