This problem involves number theory???

> This problem involves number theory???

yes, you can refer to chapter 33 of Introduction to Algorithms,
MIT Press, there covers enough knowledge you need to solve the
problem.

suppose d is multiplicative inverse of e, modulo (p - 1)(q - 1),
where p * q = n

then the answer should be c^d (mod n)

> > This problem involves number theory???
>
> yes, you can refer to chapter 33 of Introduction to Algorithms,
> MIT Press, there covers enough knowledge you need to solve the
> problem.
>
> suppose d is multiplicative inverse of e, modulo (p - 1)(q - 1),
> where p * q = n
>
> then the answer should be c^d (mod n)

Thanks!

Но ведь ответ не всегда верен! Контрпример:
e=3
n=15 (p=3,q=5)
c=3

GCD(e,(p-1)(q-1))=GCD(3,8)=1
e<(p-1)(q-1)

e*d=1 modulo (2*4) => d=3
m=c^d (modulo n)=3^3 mod (15)=(15+12) modulo (15)=12 (modulo 15) != 3 modulo (15)=c modulo (15)

Проблема возникает в случае GCD(c,n)>1 (p or q (if pq then c=0 mod (n))). Автор забыл упомянуть, что GCD(c,n)=1 или мне повезло с АС?

Edited by author 17.08.2016 14:41