Previous Up Next

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 :

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 X2 = Y2 (mod n )) avant que d'avoir terminé le crible. Le format de ce fichier « produit du crible » est le suivant :
Previous Up Next