「デジタル・セキュア・パズル 第3章 （2023/03/18)」








なぜ、

int mod = 17021;
for (int m=0;m<mod;m++)
{
　　var x = m;
　　x = (x * 4402) % mod;
　　x = (x * 483) % mod;
　　x = (x * 58) % mod;
　　x = (x * 8070) % mod;

　　ASSERT(x == m);
}

//一例： (2023*4402*483*58*8070)
// == 2013235500853080
// == 118279507717 * 17021 + 2023


が成立するか。


種明かしをすると
58 * 4402
　= 255316
　= 17021 * 15 + 1
　= 1 mod 17021

483 * 8070
　= 3897810
　= 17021 * 229 + 1
　= 1 mod 16021

便宜上は
58 = 1/4402 (mod 17021)
8070 = 1/384 (mod 17021)
と書ける。


なので。

m × 4402 × 483 × 1/4402 × 1/483 (mod 17021)
　= m × (4402 × 1/4402) × (483 × 1/483) (mod 17021)
　= m × 1 × 1 (mod 17021)
　= m (mod 17021)

だから・・・です！