一个数学问题 关于RSA中的模n大数幂乘算法

Question

在RSA中计算m的e次方mod n 有一个快速算法 如下例 用a^b表示a的b次方
  3^22 mod 12
= 9^11 mod 12
= 9×(9^10) mod 12
= 9×(9^5) mod 12
= (9^2)×(9^4) mod 12
= 9×(9^2) mod 12
= 9×9 mod 12
= 9
这里9的2a次方mod12 为什么会等于9的a次方mod12呢？用的什么定理？

Answer 1

Lz　 应是3的2a次方mod12   =  9的a次方mod12
 3^2a=(3^2)^a=9^a

Answer 2

是的 但是消解过程中一个在把9的偶数次方变成他的一半次方  比如9的10次方mod12就能消解成9的5次方mod12 不知道是怎么得出来的

Answer 3

...不是在一楼说了吗?9^2a%12=(9*8 + 9)^a%12
(9*8 + 9)^a除了最后一项是9^a,其它的项都有9*8,模12的结果就是9^a%12

Answer 4

哈，偶看错题了．．．．．
  3^22   mod   12 
=   9^11   mod   12 1L正解
　　　　

Answer 5

From Fermat's Little Theorem, we know that
an mod n = a
for any integer a and any prime n. This means that if n is prime then an mod n = a for any integer a. The contrapositive of this statement says that if an mod n != a for some integer a then n is NOT prime.
Unfortunately, the converse of the theorem is not true. This means that if an mod n = a, we cannot be sure whether n is prime. However, we can make use of the contrapositive to determine if n is composite. In other words, if there exists an integer a such that an mod n != a, then n is not prime. By testing out sufficient numbers of a's, we can exclude numbers that are composite and retain numbers that are probably prime. The following source code illustrates this.
// confidence determines the number of times to test.for(int round = 0; round < confidence; round++)
{
    // generate random a < n
    a.genRandomBits(testBits, rand);    // calculate a^(n) mod n, where thisVal = n
    BigInteger expResult = a.modPow(thisVal, thisVal);    // is NOT prime if a^(p) mod p != a
    if(expResult != a)
        return false;
}return true;
There is a class of composite integer known as Carmichael number that cannot be differentiated from real primes using this test. Such integers satisfy an mod n = a for all positive integers a with gcd(a,n) = 1.