Quelques exercices supplémentaires pour la séance du 23 octobre#

Méthode de Pollard#

  • À l’aide de sage, définir une fonction \(f\) de paramètres \(a\) et \(x\) et renvoyant \(x^2+a\).

  • À l’aide de sage

    • définir l’anneau \(A=\mathbb Z/42\mathbb Z\) (en utilisant IntegerModRing)

    • tirer un élément \(a\) de \(A\) au hasard (en utilisant random_element)

    • déterminer le parent de \(a\) (à l’aide de parent)

    • définir b=a.lift(), que vaut \(b\) et quel est son parent ?

    • mêmes questions avec c=ZZ(a)

  • À l’aide de sage, calculer le pgcd de \(2024\) et \(5635\) puis factoriser ces deux entiers.

  • On rappelle le principe général de la méthode Pollard pour chercher un diviseur non trivial d’un entier composé \(n\) : on travaille dans \(\mathbb Z/n\mathbb Z\), on définit la suite \((x_k)\) par \(x_{k+1}=x_k^2+a\) (où \(a\) et la conditions iniale \(x_0\) sont tirés au hasard). On calcule alors la suite \(\mathrm{pgcd}(x_{2k}-x_k,n)\) jusqu’à obtenir un résultat différent de \(1\). Concevoir puis implémenter cette méthode avec les caractéristiques suivantes :

    • les paramètres sont \(n\) et \(N\);

    • on teste pour \(k\leq N\), si on dépasse le nombre maximal de tests, la procédure revoie une erreur;

    • si \(\mathrm{pgcd}(x_{2k}-x_k,n)=n\), la procédure s’arrête et renvoie une erreur;

    • si \(d = \mathrm{pgcd}(x_{2k}-x_k,n)\neq 1,n\), la procédure s’arrête et renvoie \(d\).

  • Expérimenter.

Matrices involutives dans \(\mathbb F_2\)#

  • À l’aide de sage (et en utilisant au maximum des méthodes adaptées, voir par exemple Calcul mathématique avec Sage, chapitre 8)

    • définir l’anneau \(A\) des matrices des matrices \(M_{10}(\mathbb F_2)\);

    • définir l’identité de \(A\);

    • tirer un élément \(m\) au hasard;

    • tester si \(m\) est inversible;

    • tester si \(m\) est une involution (on rappelle que \(m\) est dite involutive si \(m\) est inversible et \(m^{-1}=m\)).

  • À l’aide de sage calculer le nombre de matrices involutives de \(M_{4}(\mathbb F_2)\). Comparer au nombre de matrices de \(M_{4}(\mathbb F_2)\).

  • Écrire une fonction avec les caractéristiques suivantes

    • les paramètres sont \(n\) et \(N\);

    • on effectue au plus \(N\) tests, si on dépasse le nombre maximal de tests, la prodédure renvoie une erreur;

    • à chaque étape, on tire une matrice \(m\) au hasard dans \(M_{n}(\mathbb F_2)\), si \(m\) est une involution, la procédure s’arrête et renvoie \(m\) et le nombre de tests effectués.

  • Pour \(n=4\), représenter graphiquement (par exemple à l’aide de bar_chart) le nombre de tests effectués pour la fonction précédente (en faisant par exemple \(20\) puis \(100\) appels à la fonction).

  • Faire la moyenne du nombre de tests effectués dans le point précédent. Commenter.

Un peu de résultant#

Les questions préliminaires de la feuille de TP sur le résultant sont à traiter avant de s’attaquer à cet exercice.

  • À l’aide de sage, définir \(P= X^2Y^2+X+3Y+1\) et \(Q = XY+1\) dans \(\mathbb Q[X,Y]\).

  • Calculer leur résultant en \(Y\).

  • En déduire les points d’interstions des zéros de \(P\) et \(Q\) (dans \(\mathbb C^2\)).

  • Faire un dessin.

  • Mêmes questions avec \(P= X^2Y^2+X-Y+1\) et \(Q = XY+1\) dans \(\mathbb Q[X,Y]\).

  • Commenter.