Учитывая безопасное простое число $P$ и генератор $г$ который генерирует все значения из $1$ к $P-1$ с
$$g^n \mod P$$
1.) Есть ли сейчас функция $f$ который присваивает уникальное значение диапазону членов
$$f(g^{ia_i},...,g^{i+b_i}) = f(g^i) = v_{ia_ib_i}$$
2.) Учитывая такое уникальное значение $v_{ia_ib_i}$ смещение к следующему $г^{q_i}$ и предыдущий $g^{-q'_i}$ может быть вычислено/аппроксимировано за довольно короткое время (часы)
Пример:
Пусть эти уникальные значения будут членами группы с $g^k \экв 0 \mod 10000$.
Присваивание (1.) будет просто ближайшим таким значением.
Есть ли способ вычислить наименьшее смещение $t$ чтобы найти следующее уникальное значение $g^r \экв 0 \mod 1000 $ с
$$g^k\cdot g^t = g^r$$
То же самое для предыдущего уникального значения (оба с $|т| \мин$)
Подробнее:
- количество уникальных значений будет намного меньше, чем $P$
- всегда будет даваться один случайный уникальный номер. Вычисление задания 1.) не нужно быть быстрым. (Я думаю, если есть какое-то решение, оно не может быть быстрым, иначе решить dlog будет легко)
- 2.) не должен быть точным расчетом.Какой-то поиск между небольшим набором возможных значений тоже подойдет. Но это всегда должно приводить к следующему/предыдущему уникальному значению.
- не всем членам группы нужно назначать такое уникальное значение
- длина интервала ($а+б+1$) должно быть разным (в большинстве случаев) навсегда уникальным значением
Таким образом, каждое значение, которое может быть сгенерировано с помощью $g^{i-a_i}$ к $г^{я+б_я}$
назначается $ф(г^я)$.
Если назначение не изменяет интервал ($а,б$) тоже меняется всего на единицу. Таким образом, для $г^{я+1}$:
$$a_{i+1} = a_i+1$$
$$b_{i+1} = b_i -1$$
($б = 0$ будет границей задания)
