TS Cryptographie : méthode des empilements

[Sirdec]

Bonjour tout le monde !

Voila mon exercice (qui porte sur la cryptographie : la méthode des empilements dite du "sac à dos"):

--------------------------------------------------------------------------
Page 1
Page 2
--------------------------------------------------------------------------

J'ai répondu aux questions du A/ sauf la 4) qui consistait à décrire l'algorithme (je comprend pas trés bien).

Ensuite au B/ sa donne :
1) Lettre choisie : K => K=11=1011 en binaire ==> m(0,1,0,1,1)
2) Ensuite je calcule M= 4 438 (c'est 945 + 1 095 + 2 398)

Puis viens le grand C/ (c'est là que je suis bloqué) :

1) sa c'est ok (ils sont bien premiers)
2)a) pu+qv=1 ==> d'aprés le théorème de Bezout on trouve u=295 et v=-311

b) Mv = 4 438*(-311) = - 1 380 218
H (reste de la division euclidienne de Mv par p=1380) = 218

c) Et là j'y arrive pas .... la liste est (b1,b2,b3,b4,b5)=(13,45,183,315,802) et il faut trouver x=(x1,x2,x3,x4,x5) pour que H= x1b1 + x2b2 + x3b3 + x4b4 + x5b5 avec les valeurs que peuvent prendre les x soit 0 et 1 .....
J'ai cherché mais je ne trouve pas (b4=315 > 218=H donc b4 et b5 ne peuvent pas être pris ; il reste b1, b2 et b3 mais 183 + 45 (les 2 plus grands qu'il reste) = 228 et 183 + 13 = 196 ==> conclusion : je ne vois pas de solution).

Je l'ai refais trois fois et je n'ai trouvé aucune erreur (j'ai même essayé ensuite avec deux autres lettres mais je n'ai pas eu plus de résultat).
J'espere que vous pourrez m'aidé et me mettre sur la bonne voie

Merci d'avance à ceux qui essayeront !

[Sirdec]

Il y a aussi un autre exercice :

1)On considère x et y des entiers relatifs et l'équation (E) : 91x + 10y = 1
a) Determiner une solution particulière de l'équation (E) et en déduire une solution particulière de l'équation (E') : 91x + 10y = 412

==> Solution particulière de (E) : x = 1 et y = -9
Solution particulière de (E') : pour passer de (E) a (E') on multiplie par 412 les deux membres ( 91x*412 + 10y*412 = 1*412) les solutions sont donc x*412 = 412 et y*412 = 3708

b) Résoudre (E')

==> Ben là j'ai des problèmes ... malgrés le cours qu'on a fait en cours j'y arrive pas et donc si vous pouviez me mettre sur la bonne voie pour résoudre cette question ce serait sympas

[fahr451]

fais donc la soustraction membre à membre (pour éliminer les 412 du second membre) déduis en que 91 divise ...

[Sirdec]

fais donc la soustraction membre à membre (pour éliminer les 412 du second membre) déduis en que 91 divise ...

Merci ^^ (je venais justement pour dire que j'avais trouvé mais merci quand même :++: )

La suite :
2) Montrer que les nombres entiers An = 3(puissance 2n) -1, où n est un entier naturel non nul, sont divisibles par 8 (une des méthode possibles est un raisonnement par récurrence).

J'essaye le raisonnement par récurence mais a un moment je sais plus comment faire :

. Initialisation : A1 = 3(puissance 2*1) -1 = 8
8 est bien divisible par 8

. Hérédité : c'est la que je vois pas trés bien comment partir ....

[fahr451]

tu connais les congruences?

[Sirdec]

Oui je connais les congruences.

[fahr451]

alors pas de récurrence à faire

3^2 = 9 congru à 1 modulo 8 permet de conclure

[Sirdec]

Ah ouais c'est vrai ..... Merci !

(et la fin)
3) On considère l'équation (E'') : A3*x + A2*y = 3 296
a) Déterminer les couples d'entiers relatifs (x;y) solutions de l'équation (E'').
b) Montrer que (E'') admet pour solution un couple unique d'entiers naturels. Le determiner.

(evidemment avec mes misérables connaissances je n'y arrive pas ... va falloir à nouveau que je reprenne tout ça ==> révision en perspective ^^ mais bon pour l'instant j'ai encore besoin d'aide [juste une dernière fois pour sa])

[fahr451]

tu sais quoi ?

A3 = 8 *91 , A2= 8*10, 3296 = 8 *412
...

souvent les exos ont une logique et la question 3 vient après la question 1

[Sirdec]

Ok merci tu m'as vraiment bien aidé