English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The interval discrete logarithm problem is defined as follows: Given some$g,h$ in a group $G$, and some $N \in \mathbb{N}$ such that $g^z=h$ for some$z$ where $0 \leq z < N$, find $z$. At the moment, kangaroo methods are thebest low memory algorithm to solve the interval discrete logarithm problem. Thefastest non parallelised kangaroo methods to solve this problem are the threekangaroo method, and the four kangaroo method. These respectively have expectedaverage running times of $\big(1.818+o(1)\big)\sqrt{N}$, and $\big(1.714 +o(1)\big)\sqrt{N}$ group operations. It is currently an open question as towhether it is possible to improve kangaroo methods by using more than fourkangaroos. Before this dissertation, the fastest kangaroo method that used morethan four kangaroos required at least $2\sqrt{N}$ group operations to solve theinterval discrete logarithm problem. In this thesis, I improve the running timeof methods that use more than four kangaroos significantly, and almost beat thefastest kangaroo algorithm, by presenting a seven kangaroo method with anexpected average running time of $\big(1.7195 + o(1)\big)\sqrt{N} \pm O(1)$group operations. The question, 'Are five kangaroos worse than three?' is alsoanswered in this thesis, as I propose a five kangaroo algorithm that requireson average $\big(1.737+o(1)\big)\sqrt{N}$ group operations to solve theinterval discrete logarithm problem.

Kangaroo Methods for Solving the Interval Discrete Logarithm Problem