Построение алгоритма решателя CDH

Предполагать $C_k: (g, g^a, g^b) \mapsto g^{ab}$ ваш CDH-решатель, который решает его с вероятностью $1 - \frac{1}{2^k}$ и специальный символ в противном случае. Давайте построим их из $C_1$ рекурсивно.

Возведение $С_{к+1}$:

1. Рассчитать $C_k(г, г^а, г^б)$. Если он вернется $г^{аб}$, выведите его (вероятность этого $1 - \frac{1}{2^k}$). В противном случае перейдите ко второму шагу.
2. Сгенерировать два независимых случайных числа $х$ и $у$ равномерно распределены от 1 до $p-1$.
3. Рассчитать $ г ^ {акс} $ и $ г ^ {от} $. Обратите внимание, что они независимы от $г^а$ и $г^б$.
4. Рассчитать $C_1(г, г^{акс}, г^{по})$. Если он возвращает специальный символ, выведите его (вероятность этого $\frac{1}{2^{k+1}}$). В противном случае он вычислил $g^{abxy}$. Перейти к пятому шагу.
5. Используйте расширенный алгоритм Евклида, чтобы найти $z$, такой, что $xyz \эквив 1 (\mod p-1)$.
6. Рассчитать $g^{abxyz} = г^{ab}$ и выведите его (вероятность этого $\frac{1}{2^{k+1}}$).

Нетрудно заметить, что полная вероятность выхода $г^{аб}$ является $1 - \frac{1}{2^k}$ в настоящее время.