Learn French 100% free Get 1 free lesson per week // Add a new lesson
Log in!

> Log in <
New account
Millions of accounts created on our sites.
JOIN our free club and learn French now!




Get a free French lesson every week!

  • Home
  • Contact
  • Print
  • Guestbook
  • Report a bug


  •  



    Calcul inv et modulo (1)

    << Forum maths || En bas

    POSTER UNE NOUVELLE REPONSE


    Calcul inv et modulo
    Message de antoine posté le 12-04-2009 à 12:56:40 (S | E | F)

    Bonjour,
    J'ai un petit soucis pour appliquer l'algorithme d'Euclide étendu (inv et modulo).
    Je ne trouve jamais le même résultat que sur le site Lien Internet


    par exemple :
    je cherche inv (13) mod 27

    27 = 2 x 13 + 1
    13 = 13 x 1 + 0

    ensuite on fait

    1 = 1 x 27 - 2 x 13
    le site me donne 25 et je ne vois pas d'ou cela vient (27 - 2 ?)

    Enfin je dois mal m'y prendre à un moment...

    un autre exemple :
    inv 5 mod 17
    17 = 3 x 15 + 2
    5 = 2 x 2 + 1
    2 = 2 x 1 + 0

    1 = 1 x 5 - 2 x 2
    1 = -2 x 17 + 7 x 5

    Le site me donne 7 en résultat.

    Pouvez vous m'aider, cela serait cool, car j'ai cherché sur différents
    sites sans réponse, je dois mal m'y prendre.



    Réponse: Calcul inv et modulo de antoine, postée le 15-04-2009 à 23:00:24 (S | E)
    personne ne sait ?


    Réponse: Calcul inv et modulo de iza51, postée le 16-04-2009 à 06:54:32 (S | E)
    Bonjour,
    l'algorithme donné donne bien 25 comme résultat à inv(13) [mod 27]quand on fait les calculs demandés "à la main"

    Pour espérer trouver la même réponse, il faut suivre les étapes de l'algorithme
    b=13 et n=27
    n0=n=27
    b0=b=13
    t0=0
    t=1
    q=E(n0/b0)=E(27/13)=2
    r=n0-qb0=27-2*13=1
    début boucle: r>0 donc temp=t0-qt=-2
    temp <0
    donc nouveau temp= n-((-ancien (temp) mod 27)=27-(2 mod 27)=27-2=25

    t0=t=1
    t=25
    n0=13
    b0=1
    q=E(n0/b0)=E(13/1)=13
    r= 13 -13*1 = 0
    fin de la boucle
    inv(b) mod n est égal à t
    ici inv(13 )mod 27 est égal à 25



    Réponse: Calcul inv et modulo de ajl, postée le 16-04-2009 à 10:56:12 (S | E)
    Bonjour,

    Une tentative de réponse :
    soit a l'inverse de 13 modulo 27. Il faut donc que le reste de la division de 13a par 27 donne 1. Ou encore que 13a - 1 soit un multiple de 27.

    Or si on prend a=-2 on trouve 13(-2)-1=-27. Or "a" doit être un nombre entier compris entre 0 et 26. Il faut donc "convertir" -2 en un nombre compris entre 0 et 26 d'où -2= 25 - 27.

    On vérifie que 13(-2)=-27 peut s'écrire 13(25)=27(26) puisque -1 = 26 -27

    De la même façon :
    Soit b l'inverse de 5 modulo 17. Il faut que 5b-1 soit un multiple de 17.

    Or 5(7)-1=34 donc b=7.



    Réponse: Calcul inv et modulo de antoine, postée le 18-04-2009 à 14:02:25 (S | E)
    d'accord merci beaucoup pour vos différentes réponses, j'ai enfin compris



    POSTER UNE NOUVELLE REPONSE