Идентификация корня для любой пары простых чисел

b0 = xi MOD 2 и b1 = (xi MOD p) + (xi MOD q) MOD 2 ,
как следствие леммы 1. Бит b0 может быть вычислен на этапе шифрования, не зная ни p, ни q, в то время как b1 требует, чтобы в этом определении были известны p и q, и не может быть непосредственно вычислен, зная только N .
В принципе, способ получения b1 заключается в публикации предварительно вычисленного двоичного списка (или таблицы), в позиции i которого находится бит b1, относящийся к сообщению m = i. Этот список не раскрывает никакой полезной информации о факторизации N, потому что, даже если мы знаем, что остатки по модулю p и по модулю q имеют одинаковую четность, мы не знаем, какая четность, и если эти остатки имеют разные паритеты, мы не знаем, какая из них какая

. Хотя список делает задачу теоретически выполнимой, его размер имеет экспоненциальную сложность по отношению к N и , следовательно, практически нереализуем.
При поиске различных способов получения b1 или какой-либо другой идентифицирующей информации было исследовано несколько подходов:
определить полиномиальную функцию, которая принимает значения в вышеупомянутом списке в соответствующих целочисленных позициях; к сожалению, это решение непрактично, поскольку этот полином имеет степень, примерно равную N, и не является разреженным; таким образом, он сложнее, чем список:
распространить метод предыдущего раздела, основанный на квадратичных остатках, на любую пару простых чисел, используя степенные остатки более высокого порядка и более общие законы взаимности; в частности, четвертичная взаимность с целыми числами Гаусса будет участвовать в обеспечении аккуратного решения для простых чисел, конгруэнтных 5 по модулю 8.
использовать групповые изоморфизмы; это также может представлять практический интерес, хотя и не оптимальный, поскольку он зависит от сложности задачи дискретного логарифма и может потребовать передачи большего количества битов, чем теоретическая нижняя граница 2.
Полиномиальная функция
Мы можем построить идентифицирующий полином как интерполяционный полином, выбрав простое число P больше N