Założenie decyzyjnej resztowości złożonej

Założenie decyzyjnej złożonej resztowości (DCRA) jest matematycznym założeniem stosowanym w kryptografii . W szczególności założenie to jest wykorzystywane w dowodzie kryptosystemu Pailliera .

Nieformalnie DCRA stwierdza, że ​​biorąc pod uwagę liczbę złożoną $n$ liczbę całkowitą , $trudno$ jest zdecydować, czy jest to ${\$ modulo ${\ displaystyle n ^ {2}}$$z$ . To znaczy , czy istnieje $,$ że

${\ Displaystyle z \ równoważnik y ^ {n} {\ pmod {n ^ {2}}}. \,}$

Zobacz też

• Kwadratowy problem resztkowy
• Wyższy problem resztkowy

• P. Paillier, Kryptosystemy klucza publicznego oparte na klasach pozostałości stopnia złożonego , Eurocrypt 1999.