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

DOI10.1080/09720529.2015.1084782MaRDI QIDQ5069758zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

\(r\)-adding walkdiscrete logarithm problemgeneric algorithms

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(1)

• Recursive construction of normal polynomials over finite fields

Describes a project that uses

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)