Environnement de programmation, exemples

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 :

n Résultat Temps Produit du crible

T20 650556341 * 28540307599 2s T20.txt

T30 4634293795844903 * 75576435361433 4s T30.txt

T40 72694838627523822433 * 78492223909528900351 25s T40.txt

F7 5704689200685129054721 * 59649589127497217 30s F7.txt

T45 15877128246765026029153 * 46116492876183969306047 2min T45.txt

T60 2188226993578711982382919035585611 * 309059470384525060888946669 4h30 T60.txt

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 :
```
x_i: décomposition en petits facteurs premiers de y_i
```
La décomposition est donnée par la liste de ses facteurs (il peut donc y avoir des répétitions).