Então, eu tenho trabalhado recentemente em uma implementação do teste de primalidade de Miller-Rabin. Estou limitando-o a um escopo de todos os números de 32 bits, porque este é um projeto divertido que estou fazendo para me familiarizar com c ++ e não quero ter que trabalhar com nada de 64 bits para Um tempo. Um bônus adicional é que o algoritmo é determinístico para todos os números de 32 bits, para que eu possa aumentar significativamente a eficiência porque sei exatamente para que testemunhas testar.

Portanto, para números baixos, o algoritmo funciona excepcionalmente bem. No entanto, parte do processo depende de exponenciação modular, ou seja (num ^ pow)% mod. então, por exemplo,

3 ^ 2 % 5 = 
9 % 5 = 
4

Aqui está o código que tenho usado para essa exponenciação modular:

unsigned mod_pow(unsigned num, unsigned pow, unsigned mod)
{
    unsigned test;
    for(test = 1; pow; pow >>= 1)
    {
        if (pow & 1)
            test = (test * num) % mod;
        num = (num * num) % mod;
    }

    return test;

}

Como você já deve ter adivinhado, surgem problemas quando os argumentos são todos números excepcionalmente grandes. Por exemplo, se eu quiser testar o número 673109 quanto à primalidade, em um momento preciso encontrar:

(2 ^ 168277)% 673109

agora 2 ^ 168277 é um número excepcionalmente grande e, em algum lugar do processo, excede o teste, o que resulta em uma avaliação incorreta.

no verso, argumentos como

Qual o valor do frete?

também avaliar incorretamente, pela mesma razão.

Alguém tem sugestões para exponenciação modular de forma a impedir esse estouro e / ou manipulá-lo para produzir o resultado correto? (a meu ver, o estouro é apenas outra forma de módulo, que é num% (UINT_MAX + 1))