modexp.h

RSA的最重要特色在于双密钥

/*
    modexp.h
    handle the Modexp calculation ((a^p)%m) using Montgomery algorithm (O(logn))
*/

#ifndef _MODEXP_H
#define _MODEXP_H

#define BIGINT unsigned long long

BIGINT modexp(BIGINT a, BIGINT p, BIGINT m){
    if(p==0) return 1;
    BIGINT r=a%m;
    BIGINT k=1;
    while (p>1){
        if ((p&1)!=0)
            k=(k*r)%m;
        r=(r*r)%m;
        p>>=1;
    }
    return (r*k)%m;
}

#endif /*_MODEXP_H*/