Environnement de programmation, exemples

Bibliothèques et code fourni

Comme déjà dit dans le sujet vous emploierez les classes BigInteger (grands nombres) et BitSet (champs de bits). En outre voici une classe Arith qui donne quelques méthodes bien utiles. Les méthodes qui vous intéressent sont les suivantes :

• Racine carré entière, ⁠static BigInteger sqrt⁠(⁠BigInteger n⁠).
• Test de l’existence de deux solutions à l’équation x² = n (mod p ), ⁠static boolean isResidue⁠(⁠BigInteger n⁠, int p⁠).
• Trouver une solution de l’équation x² = n (mod p ), ⁠static int sqrtMod⁠(⁠BigInteger n⁠, int p⁠). Le fonctionnement n’est garanti que si la méthode précédente renvoie ⁠true.

De l’importance de tester son programme (et de respecter l’interface demandée)

Votre programme sera testé par une procédure automatique. Mon travail sera donc grandement facilité si vous respectez l’interface définie dans l’énoncé, qui est particulièrement simple. Votre programme prend en argument un nombre n adapté et produit une factorisation de n, sous la forme de deux nombres séparés par «  *  ». Par exemple :

# java Qs 350243405507562291174415825999
75576435361433 * 4634293795844903

Par ailleurs, le test en cours de développement est une démarche incontournable de la programmation. Il permet d’une part de contrôler la correction du programme (dans une certaine mesure), mais aussi, si les tests sont appliqués systématiquement après chaque modification majeure, de contrôler que d’éventuelles améliorations sont bien des optimisations.

Exemples

Voici donc des exemples de factorisation dont vous pourrez vous servir :

Les temps sont des ordres de grandeur (sur une machine 1Ghz). On peut accepter de faire moins bien, on peut aussi faire mieux !

Vous noterez que pour chaque exemple, outre la factorisation, est fourni un fichier produit du crible. Ce fichier permet de commencer le développement de la dernière étape de la factorisation (algèbre linéraire + fabrication et exploitation des congruences X² = Y² (mod n )) avant que d’avoir terminé le crible. Le format de ce fichier « produit du crible » est le suivant :

• La première ligne rappelle les nombres n et B.
• Ensuite viennent les congruences x_i² ≡ p₀^{α_{0, i}} p₁^{α_{1, i}} ⋯ p_b^{α_{b, i}} (mod n ), à raison d’une par ligne et sous la forme :

  xi: décomposition en petits facteurs premiers de yi
  

  La décomposition est donnée par la liste de ses facteurs (il peut donc y avoir des répétitions).