當(dāng)p是質(zhì)數(shù)時(shí),
已知m、k、p求n是一個(gè)離散對(duì)數(shù)問題,當(dāng)p較大時(shí),目前為止還沒有有效算法,很多公鑰密碼 系統(tǒng)就是根據(jù)這個(gè)原理設(shè)計(jì)的
當(dāng)p較小時(shí),可以通過制表,逐步排除,算出n
當(dāng)p不是質(zhì)數(shù)時(shí),
可以將上述同余式分解成一組模p的素因子的同余式方程組,然后分別求解,再根據(jù)孫子定理使用各方程的解計(jì)算出原方程的解還是有些不明白，當(dāng)時(shí)別人講解的時(shí)候涉及到了好多什么原根，指標(biāo)之類的東西……給定一個(gè)大素?cái)?shù)p，及相應(yīng)的有限域Zp，若已知Zp的原根為g，給定一個(gè)數(shù)b，求x使其滿足g^x=b mod p。上述問題就是離散對(duì)數(shù)問題，目前還沒有有效地算法解決這個(gè)問題。若p不是很大，則有一些方法可以加速計(jì)算，如大步小步法、蒙特卡洛方法、指數(shù)方法等，這些方法也只是能加速計(jì)算，當(dāng)p很大時(shí)也無能為力?？蓞⒖肌洞鷶?shù)學(xué)基礎(chǔ)與有限域》、《算法數(shù)論》等書。