Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2020

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: jumping distance set

Sortuj według:

Ogranicz wyniki do:

Computing Interval Discrete Logarithm Problem with Restricted Jump Method

Qi Bin, Ma Jie, Lv Kewei

Fundamenta Informaticae

2020

Vol. 177, nr 2

189--201

The interval discrete logarithm problem(IDLP) is to find a solution n such that gn = h in a finite cyclic group G = 〈g 〉, where h ∈ G and n belongs to a given interval. To accelerate solving IDLP, a restricted jump method is given to speed up Pollard’s kangaroo algorithm in this paper. Since the Pollard’ kangaroo-like method need to compute the intermediate value during every iteration, the restricted jump method gives another way to reuse the intermediate value so that each iteration is speeded up at least 10 times. Actually, there are some variants of kangaroo method pre-compute the intermediate value and reuse the pre-computed value in each iteration. Different from the pre-compute method that reuse the pre-computed value, the restricted jump method reuse the value naturally arised in pervious iteration, so that the improved algorithm not only avoids precomputation, but also speeds up the efficiency of each iteration. So only two or three large integer multiplications are needed in each iteration of the restricted jump method. And the average large integer multiplication times is (1.633 + o (1))√N in restricted jump method, which is verified in the experiment.