Large mathematical operation c++

Question

I want large mathematical operation in c++.

long long h= 4294967295;
long long d=7910266469;
long long n=10021211227;
long long result;

I am need calculate this is:

h^d mod n

result=pow(h,d) % n;

I dont know which type using.Please help me for choose type numbers.. Thanks

you should do the maths first. Maybe there is a number type that allows you to do `pow(h,d)` but given that you need the result only mod `n` you dont really need `pow(h,d)`. For sure there are identities that you can use to make the calculation doable with `long long`, I just dont know them by heart ;) — 463035818_is_not_an_ai, Dec 15 '16 at 14:59
Don't reinvent RSA, use a crypto library ;) Or read up on the [Barrett reduction](https://en.wikipedia.org/wiki/Barrett_reduction). — Seva Alekseyev, Dec 15 '16 at 15:02
What you need is *fast modular exponentiation*. Google it and you'll find a lot! — lisyarus, Dec 15 '16 at 15:05
I am suggesting you to find a better representation of your result **before** starting to write the code. You can for example take a look [here](https://en.wikipedia.org/wiki/Modular_exponentiation) — 463035818_is_not_an_ai, Dec 15 '16 at 15:07

izlin · Answer 1 · 2016-12-15T16:05:21.017

1

Look at this wikipedia article. There is a pretty nice example with the following memory-efficient pseudo code:

function modular_pow(base, exponent, modulus)
    if modulus = 1 then return 0 
    c := 1
    for e_prime = 1 to exponent 
        c := (c * base) mod modulus
    return c

There is even a example for beeing memory-efficient and using less operations. I think getting the c++ code out of it should be possible.

If you use this method, long long for your solution should be fine.

Not tested but a simple 1:1 translation from the pseudo code from above...

long long result = 1; 
int i;
for( i=0; i<d;i++){
    result = (result * h) % n;
}

edited Dec 15 '16 at 16:05

answered Dec 15 '16 at 15:09

izlin

2,129
24
30

This code other programming language i am bad converting to c++. – TaGi Asadullazadeh Dec 15 '16 at 15:20
Maybe i should note that for large `d` the calculation will take really really really long – izlin Dec 15 '16 at 16:11

Large mathematical operation c++

1 Answers1