Pollard Method

This probabilistic method is based on the following fact. If on a certain finite set M we define a random mapping f and apply it alternately to all elements of M and match the edges y = f (x) for x, yH M. Since the set M is finite, then this graph must contain trees whose roots are connected in cycles. For a random mapping f, the cycle length is O (C # M) and the height of the tree is on average O (C # M).

To find a key, for example, in a cryptoalgorithm based on the logarithm problem on a certain group, it suffices to solve the problem of meeting a random map graph. For this, from two different starting points x0 |, x0 | | a trajectory is built before entering the cycle. Then one of the two end points lying in the cycle is fixed, and the trajectory of the other continues until the meeting with a fixed point. For the function f and the entry point x0, the length of the trajectory is O (C # M) steps. A typical form of this trajectory contains a limit cycle of length O (C # M) and a segment before entering the cycle of approximately the same length. As an indicator of the closure of the trajectory, Pollard proposed to use the equation xi = x2i, where xi is the i-th point of the trajectory for the input x0. This equality will always hold. The index value i does not exceed the sum of the length of the path to the entrance to the loop.

On average, the difficulty of finding the equality xi = x2i is equal to 3C (p / 8) # M. The complexity of the meeting, when both points lie in the cycle, is equal to 0.5C (p / 8) # M. Thus, the final difficulty is 6.5C (p / 8) # M.

Pollard's method is used to solve the logarithm problem on a cyclic group, search for partially equivalent keys (collisions), to find two arguments giving the same hash function, and in some other cases. Applied to the problem of logarithmization, this method eliminates the use of a large amount of memory compared with the method of meeting in the middle. In addition, there is no need to sort the database. As a result, the time complexity is reduced by the factor O (log # M) as compared with the method of the meeting in the middle. The complexity of this method in this case is O (C # M) steps and requires memory of O (1) block size. However, a small memory is not always required.

Consider, as an illustration of the Pollard method, an algorithm for finding a collision (two arguments giving the same hash function value) for a computational model with a memory O (v). Such arguments are the elements of the set M, the arrows from which under the action of
The hash functions of f lead to the entry point into the loop. In practice, the algorithm is reduced to finding the entry point into the cycle.
1. Enter the cycle using the equation xi = x2i = t.
2. Measure the length of the cycle m by successively applying the mapping f to the element t to obtain the equality fm (t) = t.
3. Split the cycle m into v intervals of the same or close length and create a database, remembering and arranging the starting points of the intervals.
4. For the starting vertex of step 1, perform single steps before meeting with any point from the database of step 3. Mark the start and end point of the interval at which the meeting occurred.
5. Delete the previous one and create a new database from v points, dividing the interval at which the meeting took place into equal parts, remembering and sorting the initial points of the intervals.
6. Repeat the procedure of paragraphs.4.5 until the length of the interval is equal to 1. Calculate the meeting point in the loop, calculate the collision as a pair of vertices, one of which lies in the loop, but the other is not.

This algorithm requires repeated O (C # M) steps to enter the loop and perform database sorting. At each stage when creating a new database, the interval length is reduced by v times, that is, the number of repetitions is O (logv # M). If v << C # M, then the complexity of database sorting can be neglected. Then the complexity of the algorithm is O (C # M logv # M).

Consider the possibility of improving the assessment of the complexity of this method by increasing the available memory. Recall that almost all the vertices of the random mapping graph lie on the same tree. Therefore, we will solve the meeting problem on a randomly oriented tree. With increasing depth h, the width of the tree b (h) decreases, that is, the random mapping has compressive properties. Therefore, with increasing depth of the vertex, on the one hand, the complexity of the meeting increases due to repeated use of the display, on the other hand, the probability of meeting increases due to the compressive properties. The proportion of vertices with a depth of at least h is equal to O (1 / h).

Consider two algorithms for solving the meeting problem. The first algorithm involves selecting a set of m random initial vertices, applying mappings to them at times, sorting the set of finite vertices, and searching for equal ones among them. The second algorithm involves memorizing the entire descent trajectory for each vertex, sorting the set of vertices that make up the trajectories, and searching among equals. The second algorithm is no less complex than the first, due to the compressive properties of the random mapping.

The complexity of the first algorithm is km (log m). The log m factor takes into account the complexity of sorting. Due to the paradox of birthdays, m = O (# M / h) 0.5. For one step, the complexity of the algorithm is O (C #M log # M), that is, this algorithm is more efficient than the meeting algorithm in the middle.

After the first step from the sheet, the depth becomes O (log # M). However, further growth of depth with each step slows down. This is explained by the essentially discontinuous character of the conditional probability p (h | H) of obtaining depth h at the initial depth H. Indeed, from the definition of depth it follows that each vertex with depth H + 1 is connected by an edge with vertex with depth H. From each vertex there is a single edge . Therefore, by virtue of quantitative estimates of the width of the graph
p (H + 1 | H) = [O (H-2 - (H + 1) -2)] / O (H-2) = 1-O (H-1).

The numerator of this expression is equal to the difference of the width of the graph at the depths H and H + 1, the denominator takes into account that the initial depth is equal to N. The probability to get to the depth h> H + 1 is determined by the probability of missing the depth H + 1 and the width of the graph,
p (h | H) = O (H-1h-2).

Let us compare the probability pk (h) of obtaining depth h after k steps when descending from the sheet and the probability pk (h | Mk-1) of depth h after k steps, provided that at step k-1 the depth was equal to the mathematical expectation. The estimate pk (h) e pk (h | Mk-1) holds. Therefore, the location of the probability of a complex event pk (h) can be considered the probability of a simple event pk (h | Mk-1).

Let the starting vertex lie at the depth H = O (log # M). What will be the depth after the next step? Direct calculations show that the mathematical expectation of depth is H + 1 + O (1), that is, the second and subsequent steps increase the depth of descent to O (1). Substituting the initial depth of the mathematical expectation of the descent depth in the previous step gives an estimate of the mathematical expectation of the descent depth after to the steps:
h = O (log # M) + O (k).

Since the optimal number of steps during the descent to the algorithm is determined by the equality of the difficulty of descent mk and the complexity of sorting m log m, then Copt = O (log # M). It follows that the task of meeting on a randomly oriented tree is no less complicated than the problem of meeting in a cycle, that is, we do not improve the Pollard algorithm by increasing the available memory.