Я думаю, что все должно быть возможно при условии, что вероятности независимы/некоррелированы со старшими битами дискретного логарифма.
Рассмотрим оракул алгоритма типа 1, где вероятность успеха составляет, скажем, около 1 на миллион. Дана задача дискретного логарифмирования $у=г^х$ (данный $у$ найти $0\le x<\ell$) мы можем сделать предположение, скажем, о младших 4 битах $х$ повторив 16 раз. Это сделает нашу задачу эквивалентной решению $y'=g^{[x/16]}$ и кусочки $[x/16]$ являются кусочками $х$ сдвинут вниз на 4. Как обычно, восстанавливаем дискретный логарифм побитово и сдвигаем. Чтобы восстановить младший бит $[x/16]$ мы выбираем несколько миллионов случайных $г$ В диапазоне $[0,\ell-\ell/16]$ и запускаем наш алгоритм на $y'g^r$ (который имеет дискретный логарифм $0\le [x/16]+r<\ell$. Мы рассчитываем добиться успеха хотя бы один раз, и $[x/16]$ будет бит, возвращаемый нашим алгоритмом XOR с младшим значащим битом $г$. Смывать; повторение.
Точно так же для алгоритма типа 2 с вероятностью, скажем, 0,501 мы строим то же самое. $y'$ и снова проба, скажем 100 миллионов $г$. Мы получаем 100 миллионов предсказаний для наименее значащей части $[x/16]$ из которых около 50 100 000 верны и около 49 900 000 неверны, шанс получить больше неверных прогнозов, чем верных, очень мал. Смывать; повторение.
В обоих случаях входные данные предполагаемого алгоритма равномерно выбираются из большого набора элементов (покрывающих большую часть нашей группы), чьи дискретные логарифмы лежат в определенном интервале. Если мощность нашего алгоритма не сосредоточена на элементах вне таких наборов, мы должны быть в состоянии восстановить полный дискретный логарифм.
