|
|
вернуться в форумEasy Accepted Послано Axmed 4 авг 2025 13:11 At first N = p * q, let's find this prime numbers p and q. Now we have x * x = x mod N. x * x - x = 0 mod N x * (x - 1) = 0 mod N Let's note that x != pq, because x < n. That means x mod p = 0, x - 1 mod q = 0 or x mod q = 0, x - 1 mod p = 0. Consider { x mod p = 0 x mod q = 1 } another case is symmetrical. x = k * p, because x mod p = 0. Now we have k * p mod q = 1 k = 1 / p mod q k = p ^ (-1) mod q Use Fermat's little theorem k = p ^ (q - 2) mod q. We find x = k * p, problem is solved. |
|
|