Improving the Gaudry-Schost algorithm for multi-dimensional discrete logarithm calculations: implementations relevant to electronic voting and cash schemes
Abstract
We focus on improving the Gaudry-Schost algorithm, which solves multi-dimensional discrete logarithm problem. We have proposed a modified algorithm that reduces the cost of each iteration of Gaudry-Schost algorithm by a factor of $\frac{\frac{D-1}{\Delta}+\frac{1}{l}+\frac{C_{\overline{s}_{D}}}{C_f}}{\frac{D-1}{\Delta}+1}$ where $D$ is the dimension of the problem, $l$ a specially designed quantity, $C_g$ is the cost of computing any function $g$, $\overline{s}_D,f$ are functions and $(\frac{1}{l}+\frac{C_{\overline{s}_{D}}}{C_f})
Fields of Study & Subjects
Matrix Theory and Algorithms
Mathematical Approximation and Integration
Publication details
- Journal / source
- Cryptologia
- Publisher
- Informa UK Limited
- Pages
- 1–36
- Publication date
- 8 May 2026
- Language
- EN