b431. 中國餘數 - 高中生程式解題系統

內容

背景

中國餘數定理 (Chinese Remainder Theorem，簡稱 CRT) 經常是工程學裡面常用的一種轉換域，很多人不知道當初在大學離散數學中學這個做什麼，但是在不少計算的設計都會運用到 CRT。由於電腦 CPU 架構中的運算單位是 32-bits 或者 64-bits (也許在未來會更長)，但值域高達 128-bits 或者 512-bits 以上模擬運算成了麻煩之處。

回顧中國餘數定理 CRT

$(S) : {\begin{matrix} x \equiv a_{1} \mod m_{1} \\ x \equiv a_{2} \mod m_{2} \\ ⋮ \\ x \equiv a_{n} \mod m_{n} \end{matrix}$

$m_{1}, m_{2}, \dots, m_{n}$ 任兩數互質，意即 $\forall i \neq j, g c d (m_{i}, m_{j}) = 1$
對於任意整數 $a_{1}, a_{2}, \dots, a_{n}$ 方程組 $(S)$ 均有解，意即找得到一個 $x$ 的參數解。

構造法解 CRT

設 $M = m_{1} \times m_{2} \times \dots \times m_{n} = \prod_{i = 1}^{n} m_{i}$
設 $M_{i} = M / m_{i}$
設 $t_{i} = M_{i}^{- 1} \mod m_{i}$ ，意即 $t_{i} M_{i} \equiv 1 \mod m_{i}$
方程組 $(S)$ 的通解形式為：
$x = a_{1} t_{1} M_{1} + a_{2} t_{2} M_{2} + \dots + a_{n} t_{n} M_{n} + k M = k M + \sum_{i = 1}^{n} a_{i} t_{i} M_{i}, k \in Z$
若限定 $0 \leq x < M$ ，則 $x$ 只有一解。

很多人會納悶通解為什麼長那樣，原因很簡單，要滿足方程組每一條式子，勢必對於 $a_{i} t_{i} M_{i}$ 要滿足 $x \equiv a_{i} \mod m_{i}$ ，因此 $a_{i} t_{i} M_{i} \equiv a_{i} (t_{i} M_{i}) \mod m_{i} \equiv a_{i} \mod m_{i}$ 成立，但是 $\forall i \neq j$ ，滿足 $a_{i} t_{i} M_{i} \equiv a_{i} (t_{i} M_{i}) \mod m_{j} \equiv 0 \mod m_{j}$

問題描述

來個簡單運用，來計算簡單的 RSA 加解密，特化其中的數學運算。

$M \equiv C^{d} \mod n$

$n = p \times q$ ，其中 $p, q$ 是兩個不同的質數，已知 $C, d, p, q$ ，請求出 $M$ 。

輸入說明

有多組測資，每一組測資一行四個整數

C, d, p, q

，其中

2 \leq p, q \leq 10^{9}

0 \leq C \leq p \times q, 0 \leq d \leq (p - 1) (q - 1)

。保證

p, q

是兩個不同的質數。

輸出說明

對於每一組測資輸出一行，

M \equiv C^{d} \mod n

的結果。

範例輸入 #1

88 7 17 11
11 23 17 11

範例輸出 #1

11
88

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (100%): 1.0s , <10M

提示：

使用中國餘數定理加快計算，至少快 400% 倍，直接計算會拿到 TLE。

標籤:

數論基礎

出處:

[管理者：

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
37303	s014052@stu. ... (112屆金手3鄭宇夆)	b431	python pow很好用	210	2023-08-31 09:07