Some algorithms for RSA

1. Euclid Algorithm: GCD(a, b) = GCD(b, a % b)

  1.1 a fast gcd implimetation:

  1.2 calculate d for equation: (e*d)%( (p-1)(q-1) ) == 1
 e * d = 1 (mod R) // (pre-condition gcd(e, R) = 1)
 ==> e * d = R * k + 1
 ==> e * d - R * k = e * d + R * K = 1 = gcd(e, R)
 ==> R * d1 + (e%R) * K1 = gcd(R, e%R) // (replace: e=>R, R=> e%R)
 ==> e * d + R * K = R * d1 + (e%R) * K1 // ( gcd(e, R) == gcd(R, e%R)
 ==> e * d + R * K = R * d1 + (e - [e/R]*R) * K1 = R * d1 + e * K1 - [e/R]*R * K1 = e * K1 + R * (d1 - [e/R]) * K1
 ==> d = K1, K = d1 - [e/R] * K1

 
#include < iostream >

bool Euclid(unsigned long& d, unsigned long   e, unsigned long R)
{
    unsigned long   m=R, t1,t2;
    unsigned long   k=1,k1=0;
    d = 0;
    
    while(e!=1)
    {
        if(e==0)   return false;
        t1=R/e;
        t2=R%e;
        
        if( d < t1*k ) {
            k1 = (t1*k - d) % m;
            if(k1 > 0) { k1 = m - k1; }
        } else {
            k1 = d - t1*k;
        }
            k1= (d>=t1*k) ? (d - t1*k) : (d + m - t1*k);
        d=k;
        k=k1;
        
        R=e;
        e=t2;
    }
    d = k;
    return   true;
}
main()
{
    unsigned long   a,b,c;
    
    std::cout << "Input a:";
    std::cin >> a;
    std::cout << "Input b:";
    std::cin >> b;
    
    if(Euclid(c, a,b))
        std::cout << "( " << a << " * " << c << ") % " << b  << " == 1 " << std::endl;
    else
        std::cout << "gcd(" << a << ", " << b << ") != 1" << std::endl;
}
 

2. Prime detect

  Fermat小定理:
    若n是素数，则对所有1≤a≤n-1的整数a，有a^(n-1)mod n=1;
    该定理的逆否命题也成立,即a^(n-1)mod n!=1,则n为合数;
    该定理的逆命题不一定成立, 如当a=4,n=15时,4^14mod15=1,但是4不是素数而是合数。

  如果满足a^(n-1)mod n=1,则n较大概率为素数。我们把那些使得n原本为合数而被看成素数的a叫做伪证据,n为伪素数。

  强伪素数：
    设n是一个大于4的奇整数，s和t是使得(n-1)=(2^s)*t的正整数，其中t为奇数，设B(n)是如下定义的整数集合：
    a属于集合B(n)当且仅当2≤a≤n-2且
      1: a^tmodn=1，或
      2: 存在整数i，0 <= i < s 满足a^((2^i)*t) mod n=n-1

    当n为素数时， 任意a在2和n-1中，均有a属于集合B(n);
    当n为合数时，若a属于集合B(n)，则称n为一个以a为底(基)的强伪素数，称a为n素性的强伪证据。
    n为素数，说明它对所有底均为强伪素数

typedef unsigned long T1;
typedef unsigned long long  T2;

bool btest(const T1 a, const T1 n)
{
        if( !(n&0x01) ) return false;  // n is a Odd

        // (n-1)= t*(2^s), t is a odd
        T1 s = 0, t = n-1;
        do {
                ++s;
                t >>= 1;
        } while( !(t&0x01) );

        // a^t mod n = 1
        T2 tmp = 1;
        for(unsigned int i=0; i < t; i++) {
                tmp = (tmp * a) % n;
        }

        if(tmp == 1 || tmp == n - 1) return true;

        //a^((2^i)*t) mod n = n-1
        T1 i = 1;
        for(; i < s; ++i) {
                tmp *= tmp;
                tmp %= n;
                if(tmp == n - 1) return true;
        }

        return false;
}