Некоторые вычислительные задачи в полях простого порядка

Пусть $\mathbb{Z}_p$ — поле вычетов по простому модулю $p$. Основное внимание будет сосредоточено на следующих задачах.
1. Дан многочлен над полем $\mathbb Z_p$. С помощью детерминированного алгоритма найти все корни многочлена в $\mathbb Z_p$ или какой-либо его корень.
2. Задано число $e$, делящее $p-1$. Имеется неизвестный элемент $s\in\mathbb Z_p$. Оракул для любого $x\in\mathbb Z_p$ сообщает $(x+s)^e$. Требуется определить $s$ с помощью детерминированного или случайного алгоритма, используя возможно меньшее число обращений к Оракулу и арифметических операций.
Доклад основан на готовящихся к печати совместных работах докладчика с Ж. Бургеном, М. З. Гараевым и И. Е. Шпарлинским.