C: Convert big number from string to int modulo n

Question

I'm trying to convert realy big numbers (>100 digits) from string to integer in Z_n additive group (modulo n). n is guaranteed to be in standard C int range (say n=12345).

Neither the simple approach of atoi then "%", nor BigIntiger works here.

Any ideas how to implement that?

Answer 1

I'm going to assume you meant C++ in your question (there is no such thing as C/C++). atoi converts a string into a number that can fit into a standard integer (32-bits), so that's not what you want. You'll have to write your own conversion function.

To keep the maths simple, let's assume that your number is positive. First note that addition and multiplication under modulus is equivalent to that without the modulus. So we only need to retain the result of those two operations, modulus n. Then note that we can construct the big number digit by digit:

unsigned int convert(const char* s, int n) {
    long long x = 0;
    for (char *p = s; *p; p++) {
        x *= 10;
        x += (int)(*p - '0');
        x %= n;
    }
    return x;
}

I left out any error checking for clarity. As an exercise, write some additional code to ensure that s is a valid null-terminated string representing a big integer without any whitespace/additional formatting.