How to make this function faster?

[Idontownaplanet]

inline long long cryption(long long msg, long long n, int DorE) //Encryption with two keys
{
    long long msgcl = 1;
    for(int i = 0; i < DorE; ++i)
    {
        msgcl = msgcl * msg % n;
    }
    msgcl = msgcl % n;
    return msgcl;
}

It replicates the formula C = P^e % n where 'msg' is P, e is 'DorE' and n is 'n'. C is the return parameter.

Yes this is for encryption. I've noticed that the bigger the numbers, the slower it gets. So slow that it takes more than a minute to fully break down a number in the millions.

Sadly I do not know of any better algorithms or assembly to make it faster. If anyone knows how to make it faster please let me know

[Yay295]

Have you been getting the right answers with your code? It looks wrong to me.

long long cryption ( const long long msg, const long long n, const int DorE ) // Encryption with two keys.
{
    long long Ptte = msg; // Ptte = P to the e
	
    for ( int i = 0; i < DorE - 1; ++i )
        Ptte *= msg; // ( a = a * b ) == ( a *= b )
		
    return Ptte % n;
}

Inlining a function doesn't really do much. If you have a good compiler it will be able to figure that out itself.

Making the variables you pass constant could help your compiler speed things up, possibly.

You don't need to calculate and store Ptte % n before returning it, you can just return it.


I don't know why you need long long's, but if you don't need them, smaller variables will be faster (on 32bit computers).

[Idontownaplanet]

I implemented your code and I am not getting the right answers. My code works fine but when using your code the numbers get mixed up.

If you want I can post the whole file here.

[Yay295]

Hmm, I guess I'm not understanding the math then. Sorry I couldn't help.

[Idontownaplanet]

That's fine, thanks anyway.

[Idontownaplanet]

Sweet, I found something someone posted.

There is an actual algorithm behind it.

template <typename T>
T modpow(T base, T exp, T modulus)
{
    base %= modulus;
    T result = 1;
    while (exp > 0)
    {
        if(exp & 1) result = (result * base) % modulus;
        base = (base * base) % modulus;
        exp >>= 1;
    }
    return result;
}

so i used it;

long long cryption(long long msg, long long n, long long de) //Decryption with two different keys
{
    long long crypted = modpow(msg, de, n);
    /*for(int i = 0; i < de; ++i)
    {
        crypted = crypted * msg % n;
    }
    crypted = crypted % n;*/
    return crypted;
}

and it works so much faster even with larger numbers.