申論題

Part II (10%) Pleasc answer the following question.

31.對公開金鑰加密器RSA而言,選擇一個隨機的大質數一直是基本的問題,在過去是先選擇一個隨機大整數,然後使用Miller-Rabin primalitytesting 演算法去測試此整數是否為質數。在2002年Agrawal, Kayal, and Saxena 提出了另一個演算法(簡稱 AKS演算法)for primality testing 請問若有兩個隨機大整數各自通過這兩個質數測試演算法,在意義上有何不(請說明理由)?(5分)。另請寫出 Miller-Rabinprimaltstng 演算法(Pseudocode)(5分)