5.8. Квадраты и псевдоквадраты.

Пусть n – модуль RSA, то есть n=pq, p, q – различные большие простые числа.

Возьмем произвольное число a: (a,n)=1. Возможны следующие случаи:

1) . Тогда числоa является квадратичным вычетом, или квадратом, по модулю n.

2) ,, или ,.Тогда , иa не является квадратом по модулю n. То есть, не зная разложения модуля RSA на простые сомножители и получив отрицательное значение символа Якоби, можем с определенностью сказать, что a – не квадрат по модулю n.

3) , тогдаa не является квадратом по модулю n, но символ Якоби, как и для квадрата по модулю n, равен единице: . То есть, не зная разложения модуляn на простые сомножители и получив положительное значение символа Якоби, не можем наверняка определить, является ли a квадратом по модулю n. Числа a: называютсяпсевдоквадратами по модулю n=pq. Множество псевдоквадратов по модулю n обозначается .

Утверждение (о мощности множеств квадратов и псевдоквадратов по модулю RSA).

n=pq, p, q – различные простые числа |Q(n)|=||=φ(n)/4.

Доказательство:

Согласно доказанной в п.1. теореме о числе кавдратичных вычетов, |Q(p)|=||=(p—1)/2, |Q(q)|=||=(q—1)/2. В силу взаимной простоты чисел p и q, среди чисел 0,1, 2, … , n—1 окажется ровно |Q(p)|·|Q(q)|=φ(n)/4 квадратов и ||·||=φ(n)/4 псевдоквадратов.

□

Задача различения квадратов и псевдоквадратов не сложнее задачи факторизации, так как, зная разложение n на простые сомножители, сможем вычислить ис помощью полиномиального алгоритма.

На момент написания этого пособия не имелось никакой информации о том, проще ли задача различения квадратов и псевдоквадратов, чем задача факторизации.