Répondre à la discussion
Affichage des résultats 1 à 9 sur 9

Calculer modulo grand nombre



  1. #1
    aoc

    Calculer modulo grand nombre


    ------

    Salut, j'aimerais savoir comment faire pour faire le modulo de grand nombre.
    Je sais qu'on peu décomposer les exposant, avec des multiplications et des additions . (exemple : 10 ^100 = 10^10 * 10*90) .
    Je recherche un exemple très simple pour expliquer les modulo de grand nombre , l'exemple peu être avec des nombres assez petit , je l'adapterai .
    Merci

    -----

  2. Publicité
  3. #2
    MiMoiMolette

    Re : Calculer modulo grand nombre

    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  4. #3
    aoc

    Re : Calculer modulo grand nombre

    Merci , j'ai déjà lu ce topic mais j'ai du mal à comprendre, se serait possible d'avoir un exemple très simple (surtout que je devrai expliqué à des gens ).
    Merci

  5. #4
    Maquessime

    Re : Calculer modulo grand nombre

    On a que si p est un premier et a est un entier positif tel que p ne divise pas a, alors (mod p)
    Par exemple, si a=2 et p=7
    (mod 7)

  6. #5
    aoc

    Re : Calculer modulo grand nombre

    Merci de ton exemple, mais en fait l'exemple que je devrais expliquer serais plutôt : 2^15 mod 22 , simplifier cela pour trouver facilement la réponse .

  7. A voir en vidéo sur Futura
  8. #6
    Flanders

    Re : Calculer modulo grand nombre

    Citation Envoyé par aoc Voir le message
    Merci de ton exemple, mais en fait l'exemple que je devrais expliquer serais plutôt : 2^15 mod 22 , simplifier cela pour trouver facilement la réponse .
    Tu peux utiliser la méthode qu'on appelle exponentiation rapide (dite 'square and multiply' en anglais), elle permet de calculer rapidement les résidus de puissances modulo un certain nombre rapidement. Pour cela, on écrit le diviseur en binaire, dans ton exemple 15=1+2+4+8.
    On a
    • 2^1=2 (mod 22)
    • 2^2=4 (mod 22)
    • 2^4=16 (mod 22)
    • 2^8=14 (mod 22)
    Pour finir tu as juste à multiplier ces résultats et établir un nouveau reste, celà donne 215=2*4*16*14=1792=10 (mod 22)

    En fait ton exemple se prête assez mal à cette méthode, d'autant plus que tout le monde sait que 2^15 vaut 32768 dont le reste par 22 vaut 10.

    Un exemple plus probant serait de calculer le reste modulo 31 de 3257. Là ton ordinateur n'aura pas assez de chiffres significatifs pour effectuer le calcul directement. On a 257=1+256.
    • 3^1=3 (mod 31)
    • 3^2=9 (mod 31)
    • 3^4=20 (mod 31)
    • 3^8 = 28 (mod 31)
    • 3^16=9 (mod 31)
    • 3^32=20 (mod 31)
    • 3^64=28 (mod 31)
    • 3^128=9 (mod 31)
    • 3^256=20 (mod 31)

    Et finalement 3257=31*3256=3*20=29 (mod 31)

  9. Publicité
  10. #7
    MiMoiMolette

    Re : Calculer modulo grand nombre

    C'est trop compliqué ~

    Surtout ça :

    d'autant plus que tout le monde sait que 2^15 vaut 32768 dont le reste par 22 vaut 10.


    Soit x la congruence de 2^15 modulo 22
    2^15 = x + 22k
    Hop ! On est dans un cas particulier puisque 2 divise 22 (autrement, on cherche l'inverse)

    2^14 = x/2 + 11k

    Now on cherche la congruence de 2^14 modulo 11
    : fonction indicatrice d'Euler.
    Le théorème d'Euler dit en fait que si a et b sont premiers entre eux,

    Formule générale :




    Donc on sait que



    Donc x = 10.

    C'est peut-être plus long en taille mais c'est beaucoup moins fastidieux que de faire des calculs.
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  11. #8
    MiMoiMolette

    Re : Calculer modulo grand nombre

    Citation Envoyé par Flanders Voir le message
    Un exemple plus probant serait de calculer le reste modulo 31 de 3257. Là ton ordinateur n'aura pas assez de chiffres significatifs pour effectuer le calcul directement. On a 257=1+256.
    • 3^1=3 (mod 31)
    • 3^2=9 (mod 31)
    • 3^4=20 (mod 31)
    • 3^8 = 28 (mod 31)
    • 3^16=9 (mod 31)
    • 3^32=20 (mod 31)
    • 3^64=28 (mod 31)
    • 3^128=9 (mod 31)
    • 3^256=20 (mod 31)

    Et finalement 3257=31*3256=3*20=29 (mod 31)
    Trop compliqué aussi !
    On regarde
    Donc

    Division euclidienne de 257 par 30 : reste 17



    Et après on fait ta méthode pour 3^17.
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  12. #9
    Nablamax

    Re : Calculer modulo grand nombre

    Bonjour, 81 mod 31=19 et pas 20....c'est pourquoi le calcul de 3^257 mod 31 était faux...
    Amicalement,

Discussions similaires

  1. emailing en grand nombre
    Par jefdevannes dans le forum Internet - Réseau - Sécurité générale
    Réponses: 3
    Dernier message: 14/02/2013, 00h00
  2. Comment calculer un nombre d'electron de valence
    Par fan_de_stargate dans le forum Chimie
    Réponses: 14
    Dernier message: 20/01/2009, 15h14
  3. Argument d'un nombre complexe modulo 2 pi ?
    Par vjonas dans le forum Mathématiques du collège et du lycée
    Réponses: 6
    Dernier message: 11/10/2008, 19h18
  4. Le plus grand nombre premier.
    Par criticus dans le forum Mathématiques du supérieur
    Réponses: 15
    Dernier message: 12/05/2005, 17h12
  5. Calculer le nombre de photon.
    Par Floris dans le forum Physique
    Réponses: 9
    Dernier message: 19/11/2004, 12h03