Calculer a*a mod n sans débordement

Question

J'ai besoin de calculer a*a mod n mais a est assez grand, ce qui provoque un dépassement lorsqu'on le met au carré. Faire ((a % n)*(a % n)) % n ne fonctionne pas car (n-1)2 peut provoquer un dépassement. C'est en C++ et j'utilise int64_t

Éditer:

Valeur de l'exemple : a = 821037907258 et n = 800000000000, ce qui provoque un dépassement si on le met au carré.

J'utilise DevCPP et j'ai déjà essayé de faire fonctionner des bibliothèques de grands entiers sans succès.

Éditer 2:

Non, il n'y a pas de motif à ces nombres.

Answer 1

Si vous ne pouvez pas utiliser une bibliothèque d'entiers longs, et que vous n'avez pas de type uint128_t natif (ou similaire), vous devrez le faire manuellement.

Une option consiste à exprimer a comme la somme de deux quantités de 32 bits, c'est-à-dire a = 232b + c, où b contient les 32 bits de poids fort, et c contient les 32 bits de poids faible. L'opération de carré consiste ensuite en quatre multiplications croisées; chaque résultat est garanti de rentrer dans un type de 64 bits. Vous effectuez ensuite l'opération de modulo en recombinant les termes individuels (en tenant compte avec soin des décalages nécessaires pour réaligner tout).

Answer 2

Je sais que vous n'avez plus besoin de cela et qu'il existe une solution alternative, mais je veux ajouter une méthode alternative pour le mettre en œuvre. Il fournit deux techniques différentes : l'algorithme du doublement et de l'addition, et la méthode pour gérer mod(a + b, n) avec la détection de dépassement.

L'algorithme du doublement et de l'addition est généralement utilisé dans des domaines où la multiplication n'est pas possible ou trop coûteuse à calculer directement (comme les courbes elliptiques), mais nous pourrions l'adopter pour le gérer dans notre situation afin de gérer les dépassements.

Le code suivant est probablement plus lent que la solution acceptée (même lorsque vous l'optimisez), mais si la vitesse n'est pas critique, vous pouvez le préférer pour sa clarté.

unsigned addmod(unsigned x, unsigned y, unsigned n)
{
    // Précondition : x>= 1) {
        if (b & 1) {
            sum = addmod(sum, a, n);
        }
        a = addmod(a, a, n);
    }
    return sum;
}

Answer 3

Voici une implémentation de multiplication double-and-add a * b % m, sans dépassements, quelle que soit la taille de a, b et m.

(Notez que les lignes res -= m et temp_b -= m reposent sur le dépassement d'entiers non signés de 64 bits afin de donner les résultats attendus. Cela devrait fonctionner car le dépassement d'entiers non signés est bien défini en C et C++. Pour cette raison, il est important d'utiliser des types entiers non signés.)

uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m) {
    uint64_t res = 0;
    uint64_t temp_b;

    /* Nécessaire uniquement si b peut être >= m */
    if (b >= m) {
        if (m > UINT64_MAX / 2u)
            b -= m;
        else
            b %= m;
    }

    while (a != 0) {
        if (a & 1) {
            /* Ajouter b à res, modulo m, sans dépassement */
            if (b >= m - res) /* Équivaut à if (res + b >= m), sans dépassement */
                res -= m;
            res += b;
        }
        a >>= 1;

        /* Doubler b, modulo m */
        temp_b = b;
        if (b >= m - b)       /* Équivaut à if (2 * b >= m), sans dépassement */
            temp_b -= m;
        b += temp_b;
    }
    return res;
}

Ceci est ma modification d' une autre réponse à une question similaire.

Answer 4

Vous pouvez implémenter la multiplication vous-même, en ajoutant n à chaque exécution, et en faisant immédiatement le modulo du résultat.

Answer 5

Je pense vraiment que ((a % n)*(a % n)) % n devrait fonctionner pour les entiers positifs. Pourquoi pensez-vous que cela ne fonctionne pas? Avez-vous un contre-exemple? Si n pouvait être négatif, alors l'opérateur % est indéfini.