YLL討論網

當今有個很有名的叫做 加密方法RSA
加密的主要概念是使用兩個巨大的質數相乘
例如兩個100位數的質數q,r相乘所得的數m有好幾百位數
但是此數m的因數必定只有原先那兩個100位的質數q,r
所以,有人可以想想看如何分辨一個巨大的數字 是否為質數呢

ex:20位數,看看此數是否為質數呢?

修改過了^^抱歉

tn606523 寫到:當今有個很有名的叫做 加密方法RSA
加密的主要概念是使用兩個巨大的質數相乘
例如兩個100位數的質數q,r相乘所得的數m有好幾百位數
但是此數m的因數必定只有原先那兩個100位的質數q,r
所以,有人可以想想看如何分辨一個巨大的數字

ex:20位數,看看此數是否為質數呢?

你的問題並不明確,請麻煩說清楚點!

用費爾馬小定理
a^(n-1) mod n =1 (n為質數,a為大於1,不等於n的整數)

取a=2,有99.997%準確