b429: 離散對數
Tags : 同餘 數論基礎
Accepted rate : 39人/47人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-07-06 18:16

Content

背景

高中時上過對數,了解 $a^x = b$,則 $x = \log_{a}{b}$。這個問題很簡單,但是 log() 又是怎麼運作,當時是用查表法,不久在大學就會學到泰勒級數,藉由電腦運算,計算越多次就能更逼近真正的結果。

離散對數的形式如下:

$$a^x \equiv b \mod n$$

已知 $a, b, n$,通常會設定 $0 \le a, b < n$。這問題的難處在於要怎麼解出 $x$,沒有 log() 可以這麼迅速得知。

為什麼需要離散對數?不少的近代加密算法的安全強度由這個問題的難度決定,例如 RSA 加密、Diffie-Hellman 金鑰交換 ... 等,實際運用需要套用許多數論原理。然而,加密機制要保證解得回來,通常會保證 $gcd(a, n) = 1$,讓乘法反元素 (逆元) 存在。

問題描述

$$a^x \equiv b \mod n$$

已知 $a, b, n$,解出最小的 $x$,若不存在解則輸出 "NOT FOUND"。

Input
多組測資,每一組測資一行有三個整數 $a, b, n$,其中 $1 \le a, b \le 10^9, 2 \le n \le 10^9$,滿足 $gcd(a, n) = 1$。
Output
對於每一組測資輸出一行,若存在一個 $x$ 符合解輸出最小的那一個,反之輸出 "NOT FOUND"。
Sample Input #1
2 1 5
2 2 5
3 5 17
4 2 17
Sample Output #1
0
1
5
NOT FOUND
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 3.0s , <1M
Hint :
Tags:
同餘 數論基礎
出處:
[管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」