Troisième semaine

Exercice 1	Travail sur la notion de bit et de clé en cryptographie	Bit Cle TestCle
Exercice 2	Monomes et polynomes	Monome Polynome TestPolynome

Exercice 1 :

On parle beaucoup ces temps-ci de cryptage et tout particulièrement de clés. La clé d'un algorythme de cryptage est en général un nombre binaire utilisé pour coder un message. On trouve des clés de 40, 56, 64, 128 bits ou plus ! On va
réaliser ici une classe permettant de manipuler de telles clés.

On a tout d'abord besoin d'une classe Bit pour manipuler les bits. un bit sera mémorisé sous la forme d'un booléen (car on n'a que deux états '0' ou '1'). Voici le squelette de cette classe :

class Bit { protected boolean bit; public Bit(boolean bit) { // ... } public Bit(char c) { // ... } public String toString() { // ... } public Bit not() public Bit xor(Bit b)

public Bit copie()

}

Les clés sont mémorisées sous la forme d'un vecteur de Bits; la taille du vecteur étant égale au nombre de bits de la clé.
Ecrire une classe Cle correspondant au squelette suivant :

class Cle { protected Bit[] cle; public Cle(String cle) // par exemple "0011010" { // ... } public Cle(int length) // Créé une clé de longueur 'length' initialisée à "0000...0000" { // ... } public String toString() public int length() // Retourne la longueur de la clé public Cle not() // Retourne le complément de la clé courante public Cle xor(Cle cle) // Calcul le "ou exclusif" de la clé courante avec la clé passé en paramètre public Cle copie() // Effectue une copie de la clé courante }

Enfin, ajouter une méthode dont la signature est la suivante

public Cle permutation(int[] indices)

Cette méthode prend en paramètre un tableau contenant les nouveaux indices :

0	1	2	3
3	2	1	0

Ainsi le tableau ci-dessus permet d'inverser une clé (l'indice 0 devient 3, le 1 devient 2, etc ...)

Voici le code de la classe TestCle, à vous de faire celui de la classe Cle :

class TestCle { public static void main(String[] args) { Cle cle1 = new Cle("10011"); Cle cle2 = new Cle("11111"); System.out.println("Cle1 = "+cle1+" et Cle2 = "+cle2); System.out.println("Complement de la Cle1 = "+cle1.not()); System.out.println("Complement du complement de la Cle1 = "+cle1.not().not()); System.out.println("Cle1 xor Cle2 = "+cle1.xor(cle2)); System.out.println("(Cle1 xor Cle2) xor Cle2 = "+cle1.xor(cle2).xor(cle2)); System.out.println("Permutation de Cle1 = "+cle1.permutation(new int[]{4,3,2,1,0}));
} }

Voici un exemple d'exécution de la classe TestCle :

C:\Java\Algo> java TestCle
Cle1 = 10011 et Cle2 = 11111
Complement de la Cle1 = 01100
Complement du complement de la Cle1 = 10011
Cle1 xor Cle2 = 01100
(Cle1 xor Cle2) xor Cle2 = 10011
Permutation de Cle1 = 11001
C:\Java\Algo>

La méthode cryptographique consistant à utiliser le XOR et une clé aussi longue que le message à coder est appelée one time pad. C'est une méthode infaillible qui a l'inconvénient de devoir gérer le transport des clés entre les interlocuteurs. Pour plus d'informations sur les systèmes de cryptographie, jetez un oeil ici .

Exercice 2 :
On désire créer une class Polynome pour manipuler des polynomes d'ordre quelconque. On se limitera ici aux polynomes à coefficients entiers. Un polynome est composé de monomes, par exemple le polynome ci dessous, d'ordre 3, comporte 4 monomes :

3x2-2x2+x+1

Partie A :

Pour commencer il faut fabriquer une classe Monome . Voici le squelette de cette classe :

class Monome { /** Le coefficient de ce monome */ protected int coef; /** L'exposant de ce monome */ protected int exp; public Monome(int coef, int exp) { // ... } public String toString() {    // ...
} public int getCoef() {    // ...
}

public int getExp()
{    // ...
}

}

Partie B:

Un polynome est un ensemble de monomes. Pour mémoriser un polynome il suffit de mémoriser ses monomes. Les monomes à coefficient nul sont mémorisés, si leur exposant est inférieur au degré du polynome.

Les monomes sont mémorisés dans un vecteur de Monomes de taille égale à l'ordre du polynome plus un. En fonction des manipulations effectuées sur les polynomesil est plus pratique de mémoriser les monomes à l'envers.

class Polynome { /** Un polynome est un ensemble de monomes */ protected Monome[] monomes; public Polynome() { // ... } public Polynome(int a) { // ... }

public Polynome(int a, int b) { // ... }

public Polynome(int a, int b, int c) { // ... }

public Polynome(int[] coeffs) { // ... }
public int coefAt(...) { // ... }

public String toString() { // Dans le cas ou le polynome ne contient que des monomes nuls afficher 0 (zéro) }

}

Partie C :

Ajouter une méthode calcul(..), à résultat entier, qui calcule la valeur d'un polynome pour l'entier x passé en paramètre.

Ajouter une méthode derivee(..), à résultat Polynome, qui dérive le polynome courant (le nouveau polynome, dérivé du polynome courant sera le résultat). Les coefficients de la dérivée sont :

d_i=(i+1).a_(i+1)

Note: Il est possible d'ajouter un constructeur had hoc pour faciliter cette question et les suivantes.

Ajouter une méthode sommme(..), à résultat Polynome, quifait la somme du polynome courant avec un autre polynome passé en paramètre (le nouveau polynome, somme des deux autres, sera le résultat). On additionne deux à deux les coefficients correspondants des deux polynomes :

s_i=a_i+b_i

Ajouter une méthode produit(..), à résultat Polynome , quifait le produit du polynome courant avec un autre polynome passé en paramètre (le nouveau polynome, produit des deux autres, sera le résultat). L'ordre du polynome résultat est égal à la somme de l'ordre des deux autres plus un. Les coefficients du produit sont :

p_i=Somme pour j=0 à i de (a_j.b_i-j)

Note: Il faut veiller à ce que les indices restent dans les valeurs permises .

C:\Java\Algo> java TestPolynome
P0 = X+1, soit P0(2) = 3 et sa derivee 1
P1 = 3X^2-X+1, soit P1(2) = 11 et sa derivee 6X-1
P2 = 5X^4+4X^3+3X^2+2X+1, soit P2(2) = 129 et sa derivee 20X^3+12X^2+6X+2
PN = -6X^5-5X^4-4X^3-3X^2-2X-1, soit PN(2) = -321 et sa derivee -30X^4-20X^3-12X^2-6X-2

Somme de P1 et PN = -6X^5-5X^4-4X^3-3X
Produit de P0 par lui meme = X^2+2X+1
C:\Java\Algo>

Voici le code de la classe TestPolynome, à vous de faire celui de la classe Monome et Polynome :

class TestPolynome { public static void main(String[] args) { Polynome p0 = new Polynome(1,1); // 1 + X Polynome p1 = new Polynome(1,-1,3); // 1 - X + 3X^2 Polynome p2 = new Polynome(1,2,3,4,5); // 1 + 2X + 3X^2 + 4X^3 + 5X^4 Polynome pn = new Polynome(new int[]{-1,-2,-3,-4,-5,-6}); System.out.println("P0 = "+p0+", soit P0(2) = "+p0.calcul(2)+" et sa derivee "+p0.derivee()); System.out.println("P1 = "+p1+", soit P1(2) = "+p1.calcul(2)+" et sa derivee "+p1.derivee()); System.out.println("P2 = "+p2+", soit P2(2) = "+p2.calcul(2)+" et sa derivee "+p2.derivee()); System.out.println("PN = "+pn+", soit PN(2) = "+pn.calcul(2)+" et sa derivee "+pn.derivee()); System.out.println(); System.out.println("Somme de P1 et PN = "+p1.somme(pn)); System.out.println("Produit de P0 par lui meme = "+ p0.produit(p0)); } }