0

I have a c struct as

typedef struct u128b {
    uint64_t hi, 
    uint64_t lo
} u128b

How would I perform a modulo expression x^e mod m when all 3 variables, x, ė, and m are all u128b structs?

I've attempted to run the code from https://stackoverflow.com/a/20114154/11667622

u128b mul_mod(u128b a, u128b b, u128b m)
{
    if (m == 0)
        return a * b;

    u128b r = {0, 0};

    while(a > 0)
    {
        if (a & 1)
            if ((r += b) > m) r %= m;
        a >>= 1;
        if ((b <<= 1) > m) b %= m;
    }
    return r;
}

//https://stackoverflow.com/questions/20111827/various-questions-about-rsa-encryption/20114154#20114154
u128b pow_mod(u128b base, u128b expon, u128b mod)
{
    u128b remainder = {0, 1};

    while (expon > 0) {
        if (expon & 1)
            remainder = mul_mod(r, base, mod);
        base = mul_mod(base, base, mod);
        expon >>= 1;
    }
    return remainder;
}

This works when all the parameters and variables are uint64_t but how would I apply this to two separate 64 bit variables hi and low for all 3 variables? shifting bits across hi and lo? and how would the modulo work with the hi and lo bits?

Mark
  • 1
  • 2
  • 3
    Have you written _anything_ so far? – Tanveer Badar Jun 19 '19 at 02:25
  • I've attempted the code from https://stackoverflow.com/a/20114154/11667622 but I couldn't figure out how to change the variables to structs and apply the shift logic to all 3 variables – Mark Jun 19 '19 at 02:41
  • 1
    It seems to me you have not attempted anything yourself so far but continued scavenging code off of SO. So let's turn to another avenue. Do you understand how to go about implementing the two mod operations between given 3 numbers? – Tanveer Badar Jun 19 '19 at 02:44
  • 1
    "Perform a modulo expression x^e mod m when all 3 variables, x, ė, and m are all u128b structs" --> [Modular exponentiation without range restriction](https://codereview.stackexchange.com/q/187257/29485) uses C code and lays out how to do that without a wider type. – chux - Reinstate Monica Jun 19 '19 at 03:08
  • So i know there's multiple ways - just Modulo exponentiation formula can help separate it out A^B mod C = ( (A mod C)^B ) mod C which might be easier to calculate, but with the sheer size of the bits and the structs cause a problem. Even reducing it down to 2 struct variables A mod C you have A.hi and A.lo and C.hi and C.lo. I wrote code that modulo'd one side A.lo and just right shift bit by bit so A.hi would trickle right to A.lo but that was with the assumption C was uint64_t. I'm not sure how to mod even a simple number by a large number 3 mod [128b struct] – Mark Jun 19 '19 at 03:10
  • "shifting bits across hi and lo?" - well I guess you'll have to write a 128-bit shift function won't you? – user253751 Jun 19 '19 at 05:08
  • https://www.google.com/search?q=github+128bit+opeartions https://github.com/davidminor/uint128 https://github.com/calccrypto/uint128_t And [this](https://github.com/maxwellsayles/liboptarith/blob/master/u128_c.h#L171) looks ready to use library. – KamilCuk Jun 19 '19 at 06:01

0 Answers0