java - Modulus of Product of two integers -

i have find c,

c = (a*b) mod m

a,b,c,m 32-bit integers. (a*b) can more 32 bits. trying figure out way compute c, without using long or data type > 32 bit.

any ideas?

what if m prime number, can things simplified?

note: based on few comments,

c = ((a mod m) * (b mod m)) mod m, in case multiplication overflow

i happen have 256 128 bit division code random-based test , i'm sure can reduce trivially 128 64 bit division , 64 32:

#include <limits.h> #include <stdio.h> #include <stdlib.h> #include <time.h>  typedef unsigned long long uint64;  #define c_assert(expr) extern char cassertextern[(expr)?1:-1] c_assert(sizeof(uint64) * char_bit == 64);  void mul64full(uint64 prod[2], uint64 a, uint64 b) {   uint64 p0, p1, p2, p3;    p0 = (a & 0xffffffff) *        (b & 0xffffffff);    p1 = (a & 0xffffffff) *        (b >> 32);    p2 = (b & 0xffffffff) *        (a >> 32);    p3 = (a >> 32) *        (b >> 32);    prod[0] = p0;   prod[1] = p3;    if ((p1 << 32) > 0xffffffffffffffffull - prod[0])     prod[1]++;   prod[0] += p1 << 32;   prod[1] += p1 >> 32;    if ((p2 << 32) > 0xffffffffffffffffull - prod[0])     prod[1]++;   prod[0] += p2 << 32;   prod[1] += p2 >> 32; }  void mul128short(uint64 prod[2], const uint64 a[2], const uint64 b[2]) {   uint64 p0[2], p1[2], p2[2];    mul64full(p0, a[0], b[0]);   mul64full(p1, a[0], b[1]);   mul64full(p2, a[1], b[0]);    prod[0] = p0[0];   prod[1] = p0[1] + p1[0] + p2[0]; }  int lessthan128(const uint64 a[2], const uint64 b[2]) {   return (a[1] < b[1]) || ((a[1] == b[1]) && (a[0] < b[0])); }  int div256x128(uint64 qr[4], const uint64 dividend[4], const uint64 divisor[2]) {   int i;    if (!lessthan128(dividend + 2, divisor))     return 0; // overflow    qr[0] = dividend[0];   qr[1] = dividend[1];   qr[2] = dividend[2];   qr[3] = dividend[3];    (i = 0; < 128; i++)   {     if (qr[3] >= 0x8000000000000000ull)     {       qr[3] = (qr[3] << 1) | (qr[2] >> 63);       qr[2] = (qr[2] << 1) | (qr[1] >> 63);       qr[1] = (qr[1] << 1) | (qr[0] >> 63);       qr[0] <<= 1;        if (qr[2] < divisor[0])         qr[3]--;       qr[2] -= divisor[0];       qr[3] -= divisor[1];        qr[0] |= 1;     }     else     {       qr[3] = (qr[3] << 1) | (qr[2] >> 63);       qr[2] = (qr[2] << 1) | (qr[1] >> 63);       qr[1] = (qr[1] << 1) | (qr[0] >> 63);       qr[0] <<= 1;        if (!lessthan128(qr + 2, divisor))       {         if (qr[2] < divisor[0])           qr[3]--;         qr[2] -= divisor[0];         qr[3] -= divisor[1];          qr[0] |= 1;       }     }   }    return 1; }  void randfill(void* p, size_t s) {   unsigned char* pc = p;   while (s--)     *pc++ = rand(); }  int main(void) {   int i;    srand(time(null));    (i = 0; < 10000; i++)   {     uint64 qr[4], dividend[4], divisor[2];      // divisor, 64 bits     randfill(&divisor[0], sizeof(divisor[0]));     divisor[1] = 0;      if (divisor[0] != 0)     {       uint64 dividend2[2];        // dividend, 128 bits       randfill(&dividend[0], sizeof(dividend[0]) * 2);       dividend[3] = dividend[2] = 0;        // divide       div256x128(qr, dividend, divisor);        // test via multiplication , addition       mul128short(dividend2, qr, divisor);       if (dividend2[0] + qr[2] < dividend2[0])         dividend2[1]++;       dividend2[0] += qr[2];       dividend2[1] += qr[3];        printf("0x%016llx%016llx / 0x%016llx = 0x%016llx%016llx:0x%016llx%016llx\n",              dividend[1], dividend[0], divisor[0], qr[1], qr[0], qr[3], qr[2]);        if (dividend[0] != dividend2[0] ||           dividend[1] != dividend2[1])       {         printf("0x%016llx%016llx - restored dividend - error\n",                dividend2[1], dividend2[0]);         exit(-1);       }     }   }    return 0; } 

output reduced 100 iterations (ideone):

0x72238cb3a1a9f5656a1e0f3567e6ce0e / 0xc7f98f34bba0fad9 = 0x0000000000000000921dba985b7ab177:0x000000000000000060d9c93d34382a2f 0xa05f7d3bf45f2cbff745f1e97ef75a4a / 0x3cba50635a5a27a9 = 0x0000000000000002a40ec5297059e69f:0x0000000000000000290f7f44a795e253 0xd48c5015950a24ac8c2c5242f098f28c / 0x3d98659426410873 = 0x0000000000000003736258d9691352d7:0x000000000000000005e859d02fbd03f7 0x985ca6eccf7a9a8d8a029afdc4029830 / 0xdc572869b7c9eb7c = 0x0000000000000000b10519e30a95b186:0x0000000000000000454594e80d549948 0x13609b86d699ecd9d5ea40a50ee97da5 / 0x32b4b9b6df2d66ca = 0x000000000000000061d4b3346f3c56fa:0x00000000000000000c0857d82eb34061 0x91d63db80153785c458edfa05c2be6a5 / 0x4bb93f8121e3da35 = 0x0000000000000001ed086e53a490eba9:0x00000000000000000154dc2121a232a8 0xd5e77579a2e69a028a6f1be52462a6a3 / 0x40c3c80baf686f29 = 0x00000000000000034d8356e4fa79eae5:0x00000000000000002a4acfad31fabcf6 0xe7289ee59d2ec9b80a671267274f9f1c / 0xa037ac77a5d63aed = 0x0000000000000001715a12bd82c8d05a:0x00000000000000002762b55566f657ca 0xdb5eb523534d10ec26c14d0a21165eaa / 0x70877083b2890e38 = 0x0000000000000001f30f41b77230648f:0x00000000000000003b161dac42798d62 0xf22bcf06050eb9faeda39c433315d3af / 0x634aa12a63798c7e = 0x00000000000000027061b6cfbdc47cac:0x00000000000000002ca1b7eee6e66707 0x6a5f7e6f71dbd32ea8be5af85b105730 / 0xacdea42e034679e0 = 0x00000000000000009d86b0889208f92c:0x0000000000000000a900572aaf6884b0 0x86f664584ea6fe564beefe1b41207713 / 0x1d319a3d3e6f6d38 = 0x00000000000000049f7c4b1ac30cb248:0x00000000000000000bdeba5d7138cf53 0x93d55d3d896f3e6e2e1ef71a01c680c4 / 0x88115750a7f8d137 = 0x00000000000000011622de3aea8d6745:0x00000000000000005f3fef0a1e3dfbf1 0xae986e3f6a4f484f4e81cf89f9be32a9 / 0x173ad8e0b4e17b5b = 0x00000000000000078417c63dc58b3e77:0x0000000000000000141d123d47a4d15c 0x5db95a0d6bd93ee1df7faf3668745e88 / 0xc07c0c65e93707ac = 0x00000000000000007ca699c204812c1c:0x0000000000000000bffbd2c9e371f7b8 0x91fc43af1dc400e75c8c89d4cb0cc766 / 0x23905f76e2c708a2 = 0x00000000000000041ad8bd6e95b77c6b:0x00000000000000000167c96223dfb3b0 0xd33cd0ece044630c7857441234b4b3bd / 0xd2ecb5308ffcd581 = 0x000000000000000100613a50243cc975:0x0000000000000000bf01143ab448d6c8 0xca7d0abe05b379f37fc540c2f2540dc2 / 0xc511ed4380f000d0 = 0x00000000000000010709e7b22b442d2e:0x0000000000000000a454f0746fcf5862 0x75418582c2c04200ceeef30b29e21ee6 / 0x622ee6915aaac16e = 0x000000000000000131bacd4a53406179:0x0000000000000000527dddc9966203e8 0x82ee158220268f14fdadf6174bc831b9 / 0x6d87f8ffbd7af5ff = 0x00000000000000013203a1ee685f58f4:0x0000000000000000619862918c6512ad 0xbabc73a5bfc6afa87be777c27af0ca7a / 0x334f8534da44ae57 = 0x0000000000000003a3aaec85949b00f6:0x00000000000000001720d365e24442e0 0xec80ac4404c4cd424add78d0aa294a76 / 0x4f06c8f784dae202 = 0x0000000000000002fe219872df7c4b95:0x00000000000000001c7f230aff95294c 0x74ac5b32627eb992d390475d4141954a / 0xbcbb67ba01ab465b = 0x00000000000000009e420c0580d7dbc7:0x000000000000000050fed88bd9810b8d 0xd0fa893e26f8f7c9b7b6346df979053f / 0x785af91d6d797129 = 0x0000000000000001bc813a285aa730ee:0x000000000000000029780222319b2121 0x5ded4a9336945fc99ae5c45b6d6a6250 / 0xfce9dfd374327842 = 0x00000000000000005f12ba510f26c8df:0x0000000000000000952062f60fb410d2 0xbd6604f3cc1e2f71b1c50f61c92682f5 / 0xb1507d6f7f83e641 = 0x0000000000000001117252ca7ec0a65f:0x0000000000000000076726c74125ead6 0x8dead81c39130dd74ae755543605d7c7 / 0x8553e144f6f3fa63 = 0x0000000000000001107e30eae9ee45d4:0x00000000000000002c281d730e73cecb 0xb62f71dee58a89915484ba8dff66acba / 0x70b8c00dfb590908 = 0x00000000000000019dc1ede4447ff324:0x00000000000000001ed8a84f8856cf9a 0x1164808010fcc683fd5fd742ef1e82e2 / 0x2329d91b9bef427f = 0x00000000000000007e9f79392cd015f6:0x000000000000000001894bd59b9031d8 0x1f65989c6839c52549a6a367837a8d68 / 0xde9e265fe8f6ee0a = 0x0000000000000000241adbd0fb260f42:0x0000000000000000c9b279dbd86298d4 0x01b09edc67f8390074bf720ce0d4e681 / 0xebef93e1de2f615e = 0x000000000000000001d569310fe86723:0x000000000000000036910723b0fdc4a7 0x43150143a042d09461fcaee011bf4d2f / 0xe01ece82ff69e963 = 0x00000000000000004c9fc0d605116cee:0x000000000000000076790cfc803f8f25 0xa8bc8c145b90657a7fa62d4fc60e8144 / 0x0f175aab16aa0d3a = 0x000000000000000b2e5c8870d0e697ea:0x0000000000000000076d41a7beb53440 0xdbb6986137f134e82b2567e7164f8d6b / 0x39e35effa049fe5d = 0x0000000000000003cba4704c8552b329:0x00000000000000000652776ce2d0c986 0xc95308e127e27a40cc2ab361f1d003f1 / 0x30baf3d3113646fd = 0x000000000000000421a383f06b1dd66e:0x0000000000000000039bd74b637d053b 0xc3d5af830984d0a89300a5a2d0ebaffd / 0xda78b7dc9d00443c = 0x0000000000000000e57983384327721c:0x0000000000000000c4e3ad916d5d816d 0x72f659ca625824c08839118a5f99d382 / 0xfcd33ec00aebb829 = 0x00000000000000007467eb48186a84b8:0x0000000000000000c6a5e47ae23e520a 0x3015b4708d7b5e031cc52f99c95c5b09 / 0x52705129ad7c7a29 = 0x00000000000000009551c5b192977b2f:0x00000000000000001d95ed27b0a13a82 0x0e1f7b0b03b5dc69ec7f0ee22d9d9103 / 0xf01589c7a2936ed8 = 0x00000000000000000f0f29462804fe9e:0x0000000000000000d04177ae1344d7b3 0xec3d468251c6746f99d7de96e6c90d1f / 0x267ab14e499c9ad9 = 0x000000000000000623af464370a3b267:0x00000000000000000e79d9a7dcf0ddd0 0x324766c3ae8fe518a91c0b89f691d8a8 / 0x473c0e6e2deff322 = 0x0000000000000000b4b0b8770b975d14:0x0000000000000000278c077555718000 0x1eea010641e4fbb7ee6adf4622a338b4 / 0x7649c1545d840edb = 0x000000000000000042e78bdeefa2d348:0x00000000000000001a6fb41e21aa8a1c 0x26cf636ee1f98f9ad6eb622275186021 / 0xbbdc13e0aacc79e6 = 0x000000000000000034e32521d0410ab4:0x00000000000000002fa92be28d29ae69 0x7a7be4e0a4f87e8283652261aa454eca / 0x9b8251b56467b45e = 0x0000000000000000c9a2458fdd775882:0x0000000000000000311b005509e9670e 0x194d9a97ca3475698a2f1bbf94996edf / 0x35072bd7e15b7473 = 0x00000000000000007a27854605b3de17:0x0000000000000000012503425afd3e8a 0xd63e9b6db46c52f4d8b986f9847ecead / 0x9d72392af8be4618 = 0x00000000000000015c59f8c79ac088ba:0x00000000000000005d586814b303213d 0xf42ea2ff56e9795d65fb8fb85e1c7f34 / 0x24c1ee0ca7a07210 = 0x0000000000000006a49ef0579168219c:0x000000000000000017b3212d2322ed74 0x924a5235e557a62df989aec565edd758 / 0x4637e63561a89af4 = 0x0000000000000002155744f31100089e:0x00000000000000002f3bd6dfa70694c0 0xf5f894c7fe0b1939a62b614de52a67b0 / 0xc9bf16d5cbe833cc = 0x0000000000000001381e0fef42ec23e6:0x00000000000000006dfa7b799b66fa68 0xbc54c083ae952260aff7f9ff2e39e958 / 0x6e0125a26fda4f3a = 0x0000000000000001b647a71af0d7d071:0x000000000000000053a8e5e784c7d0be 0xa5371345881c4c88ee129f95a49d7002 / 0x2e96b3f3a1bb5fd9 = 0x00000000000000038bd711431bff2be4:0x0000000000000000163d12e3c47b9fbe 0xed919d64a38ac50ee6289de3fa073006 / 0x6675a78db953cc35 = 0x000000000000000251939cafffb1c284:0x00000000000000001bc552caee6cbab2 0x1f1ff71139cf7455d56c25ce06af2779 / 0xf6d3acc12e75ade9 = 0x0000000000000000204816c1394b681e:0x00000000000000001d4c796ef1fb1e2b 0xe3fb1b8e26ae6958a8b9312fc35d8302 / 0x2f0e544621c3a9bc = 0x0000000000000004d84a89285f567516:0x00000000000000000e22d0a2a6d200da 0x410856e95f9cb830d95badd72b9f83e5 / 0x7ec03bc1a01cca8f = 0x00000000000000008358ce856d657b0a:0x00000000000000005c76947347c1e54f 0xe9f5f4b91b990c446d6dc188ef014d2e / 0x603063d14d68b6bf = 0x00000000000000026eab5a279b04df98:0x000000000000000021d3917341a86ac6 0x3f672efbf9c03a71d13924a3d9f33f07 / 0xa6d751e7964991ac = 0x0000000000000000614908842cc78070:0x000000000000000030ae8f43843983c7 0xf8c19187f058634d7f6f0e77c93626e1 / 0xa0dd50f4f45b003a = 0x00000000000000018bdeee39534edfd1:0x00000000000000009899a7ea260c7187 0x7fd9cc315a5c23e293edbcb24cde6258 / 0xea0758b0c7f182cc = 0x00000000000000008bda913f184cade0:0x0000000000000000ca19eebb2f9813d8 0xca048ae8719d2cbf504d5df863569fb3 / 0x8eae31c2b66f312f = 0x00000000000000016a76d09445883b90:0x00000000000000000c53fde6587d2043 0xf1a862325714d55fb17fc0fef112cd2e / 0x5c5efd2ddf2461ad = 0x00000000000000029dbcdff6149e9460:0x000000000000000059ac2b766e30284e 0x82370123858263879151b962f55b65c8 / 0x7c4067cf7662458e = 0x00000000000000010c494e7de774e5a7:0x00000000000000006bf1e0862cb00026 0xae4ad227b9816e578c12f2c496b15dc7 / 0x3bfb82ad09da4bd7 = 0x0000000000000002e7dd4bd12e902d85:0x00000000000000001a49f830ce032c14 0x9a58a643cb945107fe9fa93764aeb5b6 / 0xa5db6bce5834cc35 = 0x0000000000000000ee3baa824701f858:0x000000000000000093dbd3146d802b7e 0x3cff433501a48cca40dd1589383a1e6a / 0xe1ea9eac3c53d914 = 0x0000000000000000451e9fb6be32f4b4:0x00000000000000002a779739a4766c5a 0xe05ce3161c060193cdc77463e58ac539 / 0x4e716039d7089394 = 0x0000000000000002dc36829f6dea09fe:0x00000000000000002cfdecd854902461 0x8c172ff9496884e683fa2149acb0e973 / 0xd8e1e044a5e1006f = 0x0000000000000000a55b999b02b5b8b5:0x00000000000000001e4d953b7fd0d2f8 0xdaac01f32907d2e05a22f6e749150705 / 0x7026050046a81d30 = 0x0000000000000001f328dbbbe708e51c:0x00000000000000001e77e203f315e5c5 0xb32b29d3d107dde9bec8e2b858bbb357 / 0x750b3a447f231586 = 0x000000000000000187e150d9948eb8d0:0x0000000000000000580c63326c6de677 0xdf6e9ef5b0d613f77e584427e339ec9e / 0xbac98934efdd32fb = 0x000000000000000132392eb5cdd7ab7a:0x000000000000000085abcaa502f4f800 0x70e4427966ea353f07fc52694289df0e / 0x9a02db9f4fb0757b = 0x0000000000000000bba681f9a127cd04:0x00000000000000003b17f3b474f78a22 0x587602196f06c706c43d26b6a324da04 / 0xd52a8e594b20bb56 = 0x00000000000000006a3c831f9c1dba1a:0x00000000000000004b9caac798f75748 0xddc4b4d70076b04ad38c6fcfb745415e / 0xf920a3a3b0be6137 = 0x0000000000000000e3e2dacc13655973:0x00000000000000004d3fdaadb24076a9 0xbfb7f075e4640514acc0d34ec7b3ab23 / 0x03edc2cc944cca7b = 0x0000000000000030cc7efac33315fe5b:0x000000000000000002ddc91dc26aa76a 0xb7850ea2d84ecf8a871cde6319f1a14d / 0x5d5583e278bf2ea1 = 0x0000000000000001f75d58f861aad829:0x0000000000000000104585a47c115184 0x19d30c8f4cf0b1e8d7bf478a62f20780 / 0x7a4852d9899be914 = 0x0000000000000000361050bba6a2e574:0x000000000000000038ff75771a258670 0xd67cc4eea505a61ba2b4142239cccf60 / 0x4334772f7df221db = 0x00000000000000033108e073fa69488d:0x00000000000000002e9320cd011791c1 0x8699d56af72156d5e789058746d11016 / 0x531ef57805226c75 = 0x00000000000000019e8cf4e75d4c2521:0x000000000000000046269f1eeff82c01 0x8c7b3eb794b4b10c6ee0fc588ddd6214 / 0xd840a863692b9e7b = 0x0000000000000000a64d52f5f26edeff:0x000000000000000093cf8dd99921db8f 0xdcbfdad051f9d4f96cf696581e56b0bb / 0xed841c71fe839c94 = 0x0000000000000000ededb656cbf05c2e:0x00000000000000002ac3b820efab5e23 0xcd3d3dd4d1473d7929e7c96efa445188 / 0x46ceecb24270748b = 0x0000000000000002e6055d0fb8ccca0b:0x000000000000000032ccdcd39cb5a18f 0xd09684576d9d8effa349ad1a03df2e51 / 0x9cbedd11e11e3711 = 0x000000000000000154ab87f3f19cf5ea:0x00000000000000002c5ba1ecc43193c7 0x4eb7fc4f14b3a2faafc3cb5e260d8015 / 0x2c62de1a95a1ddc1 = 0x0000000000000001c603bfd8ac6e84de:0x0000000000000000074354c5f869aeb7 0x4820304e706d821246759231492f522e / 0x9ab151d8e1bb548a = 0x0000000000000000775c480c24c7798d:0x0000000000000000579f64114ac6882c 0xafb7699c70f40a3fabdbed7d413b2b68 / 0x5a7014cf215cd3d2 = 0x0000000000000001f165630d7bc529b0:0x0000000000000000279134df8ce2e908 0xa40b7764609c77e35b3cb7f2e247de12 / 0x26823f543a1f24ec = 0x0000000000000004428aec3f73053fc3:0x000000000000000022c3fa3735dcaa4e 0x4b3d5c68e220b1f03e69112c438fecef / 0x55cdcb691e140081 = 0x0000000000000000e07b315ed33f95df:0x000000000000000008abee64f9196790 0x07145917d5ef05a9ac76bdbc20f0f1b7 / 0xd2dcb75038abd9d4 = 0x000000000000000008984e14ed4515f5:0x0000000000000000576fbdc4d17715d3 0x79d36ed027f8136bd7237a20519d6900 / 0x65be279172e9340a = 0x00000000000000013288389b33b93e78:0x00000000000000005686822b60789850 0x10b816a5e0f32bc0a28d56a228987b97 / 0x2691631c8a4fc373 = 0x00000000000000006ef9b0e3683a6778:0x000000000000000002ea49293b8398af 0xbf6d72ffcae5a828bc10ad25ea1cc2ce / 0x91730b1ef937b029 = 0x000000000000000150eca60e96e99786:0x000000000000000085ffe8ca42bd5e58 0xa9b05d80f44dd3cf63b70d95259a8a07 / 0xa0525777429f609d = 0x00000000000000010ef523d97e6167af:0x000000000000000083b23b3a994b53b4 0xcebc9eff59e7f2c4c2583abab8e86341 / 0xa5c3e00804739505 = 0x00000000000000013f46555cc330626e:0x00000000000000007b23ce99d042711b 0x9d1340d851e89e9730b634ef10700e08 / 0x6c9b7366f2c20971 = 0x0000000000000001723ea5f3b133dff1:0x000000000000000043da931b7f08bba7 0xcac50533954fffa63f8f983623fdc3bc / 0x0b01b39932f6fb33 = 0x00000000000000126c26f2199d49c968:0x000000000000000004c39a7e9be1ac04 0x0a8d31644ea2cc187fcf54c2c4530f2a / 0x21192fee7c1cada3 = 0x0000000000000000519c6b55f4bd6eeb:0x0000000000000000054e1cb7f60ca089 0xe26c37caed68752aa4221b7a01024a13 / 0x862e65e264a0dd30 = 0x0000000000000001affc08c0c0fc6210:0x00000000000000005d17fa9067081713 0x4b6bad20c68b054c8a0302777dd3129b / 0x6f72be3f67300e03 = 0x0000000000000000ad3e5477e997550c:0x0000000000000000237cf0bdb4266b77 0x82fcd93671d634fa5860e8bdf176ffb2 / 0x0ecfa40bed38d323 = 0x0000000000000008d80913755d8ad21c:0x00000000000000000a9e9182da2f31de 0xf9292affd1c91713d8a1142692458287 / 0x584ab435ff4987df = 0x0000000000000002d26f9202488d82e9:0x000000000000000055d41be953869a90 

if use x86 assembly, simpler:

#include <stdio.h>  unsigned mulmod(unsigned a, unsigned b, unsigned m) {   unsigned result = 0;    __asm   {     mov  eax,     mov  ebx, b     mul  ebx // edx:eax = 64-bit product of a*b     push eax // store away low 32 bits of dividend      mov  ecx, m     mov  eax, edx     xor  edx, edx     div  ecx // high 32 bits of quotient     xchg eax, [esp] // store them on stack, low 32 bits of dividend     div  ecx // low 32 bits of quotient , remainder     mov  result, edx   }    return result; }  int main(void) {   unsigned = 4294967231, b = 4294967279, m = 4294967291;   printf("assembly:\n(%u * %u) mod %u = %u\n", a, b, m, mulmod(a, b, m));   printf("validation:\n(%u * %u) mod %u = %u\n", a, b, m, (unsigned)((unsigned long long)a * b % m));   return 0; } 

output (compiled open watcom c/c++ 1.9):

assembly: (4294967231 * 4294967279) mod 4294967291 = 720 validation: (4294967231 * 4294967279) mod 4294967291 = 720