On improvements of ther-adding walk in a finite field of characteristic 2

DOI10.1080/09720529.2015.1084782zbMATH Open1498.11239arXiv1601.04134OpenAlexW2963889764MaRDI QIDQ5069758FDOQ5069758

Authors: Ansari Abdullah, Hardik Gajera, Ayan Mahalanobis 

Publication date: 19 April 2022

Published in: Journal of Discrete Mathematical Sciences and Cryptography (Search for Journal in Brave)

Abstract: It is currently known from the work of Shoup and Nechaev that a generic algorithm to solve the discrete logarithm problem in a group of prime order must have complexity at least $ksqrtN$ where $N$ is the order of the group. In many collision search algorithms this complexity is achieved. So with generic algorithms one can only hope to make the $k$ smaller. This $k$ depends on the complexity of the iterative step in the generic algorithms. The $sqrtN$ comes from the fact there is about $sqrtN$ iterations before a collision. So if we can find ways that can reduce the amount of work in one iteration then that is of great interest and probably the only possible modification of a generic algorithm. The modified $r$-adding walk allegedly does just that. It claims to reduce the amount of work done in one iteration of the original $r$-adding walk. In this paper we study this modified $r$-adding walk, we critically analyze it and we compare it with the original $r$-adding walk.

Full work available at URL: https://arxiv.org/abs/1601.04134

Recommendations

• An upper bound and finiteness criteria for the Galois group of weighted walks with rational coefficients in the quarter plane
• On finite field arithmetic in characteristic 2
• Additive combinatorics over finite fields: new results and applications
• A divisibility obstruction for certain walks on Gaussian integers
• An improved lower bound for finite additive 2-bases
• scientific article; zbMATH DE number 5015675
• Random multiplicative walks on the residues modulo n
• An improvement of an estimate for finite additive bases
• Riemann and Weierstrass walks revisited
• scientific article; zbMATH DE number 2247213

zbMATH Keywords

discrete logarithm problem\(r\)-adding walkgeneric algorithms

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Applications of graph theory to circuits and networks (94C15) Number-theoretic algorithms; complexity (11Y16)

Cites Work

• The Magma algebra system. I: The user language
• Monte Carlo Methods for Index Computation (mod p)
• On random walks for Pollard's rho method
• Probability Distributions Related to Random Mappings
• Title not available (Why is that?)
• Complexity of a determinate algorithm for the discrete logarithm
• Accelerating Pollard's rho algorithm on finite fields
• A random graph
• Period Lengths for Iterated Functions

Cited In (1)

• Recursive construction of normal polynomials over finite fields

Uses Software

• Magma
• R

This page was built for publication: On improvements of ther-adding walk in a finite field of characteristic 2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5069758)