Đưa ra một số nguyên tố an toàn $P$ và một máy phát điện $g$ tạo ra tất cả các giá trị từ $1$ đến $P-1$ với
$$g^n \mod P$$
1.) Hiện tại có một chức năng $f$ trong đó gán một giá trị duy nhất cho một loạt các thành viên
$$f(g^{i-a_i},...,g^{i+b_i}) = f(g^i) = v_{ia_ib_i}$$
2.) Cho một giá trị duy nhất như vậy $v_{ia_ib_i}$ phần bù cho phần tiếp theo $g^{q_i}$ và trước đó $g^{-q'_i}$ có thể được tính toán/xấp xỉ trong thời gian khá nhanh (giờ)
Ví dụ:
Hãy để những giá trị duy nhất đó là thành viên nhóm với $g^k \equiv 0 \mod 10000$.
Phép gán (1.) sẽ chỉ là giá trị gần nhất như vậy.
Bây giờ có cách nào để tính phần bù nhỏ nhất không $t$ để tìm giá trị duy nhất tiếp theo $g^r \equiv 0 \mod 1000 $ với
$$g^k\cdot g^t = g^r$$
Tương tự cho giá trị duy nhất trước đó (cả với $|t| \min$)
Thêm chi tiết:
- số lượng các giá trị duy nhất sẽ nhỏ hơn nhiều so với $P$
- một số duy nhất ngẫu nhiên sẽ luôn được đưa ra. Tính bài tập 1.) không cần nhanh. (Tôi đoán nếu có một số giải pháp thì không thể nhanh được, nếu không thì việc giải quyết dlog sẽ dễ dàng)
- 2.) không cần phải là phép tính chính xác.Một số loại tìm kiếm giữa một tập hợp nhỏ các giá trị có thể cũng tốt. Nhưng nó luôn cần dẫn đến giá trị duy nhất tiếp theo/trước đó
- không phải tất cả các thành viên nhóm cần được gán cho một giá trị duy nhất như vậy
-độ dài khoảng ($a+b+1$) nên khác nhau (trong hầu hết các trường hợp) đối với giá trị duy nhất
Vì vậy, mọi giá trị có thể được tạo ra với $g^{i-a_i}$ đến $g^{i+b_i}$
được giao cho $f(g^i)$.
Trừ khi nhiệm vụ thay đổi khoảng thời gian ($a,b$) cũng thay đổi chỉ bởi một. Vì vậy đối với $g^{i+1}$:
$$a_{i+1} = a_i +1$$
$$b_{i+1} = b_i -1$$
($b = 0$ sẽ là biên giới của nhiệm vụ)
