Commits

Gabriel Pichot  committed d0c4f66

Ajout de plusieurs essais automatiques, plus suppression log

  • Participants
  • Parent commits bf71366

Comments (0)

Files changed (4)

File arithmetik.ml

   log "\n---- Recherche de l'ordre de %i dans %i ----\n" p n; 
   let l = getQ n in
   let q = pow 2 l in
-  log "On trouve q = %i = 2 ^ %i.\n" q l;
+(*  log "On trouve q = %i = 2 ^ %i.\n" q l; *)
   let reg1 = new register l
   and reg2 = new register (nb_bits n) in
-  log "Création de deux registres de tailles respectives %i et %i.\n" 
-    (reg1#size()) (reg2#size());
+(*  log "Création de deux registres de tailles respectives %i et %i.\n" 
+    (reg1#size()) (reg2#size());*)
   (* On met le premier registre dans un état de superposition uniforme *)
   reg1#setUniformSuperposition q;
   (* On calcule x ^ a mod n pour tous les a, on doit cependant
   (* Et on oublie pas de normaliser *)
   reg1#normalize ();
   (* Maintenant on applique la transformée de Fourier *)
-  log "Transformée de Fourier.\n";
+(*  log "Transformée de Fourier.\n"; *)
   reg1#fft (); (* ou reg1#dft q() mais moins performant :) *)
-  log "Fin de la transformée de Fourier.\n";
+(*  log "Fin de la transformée de Fourier.\n";*)
   reg1#normalize ();
   (* Si on doit afficher le résultat de la transformée de Fourier *)
   if print then showProb (reg1#state ());
   if texPrint then printAsTex (reg1#state ()) p n;
   (* On mesure c sur le premier registre *)
   let c = reg1#measureState () in
-  log "On trouve pour c : %i.\n" c;
+ (* log "On trouve pour c : %i.\n" c;*)
   (* On approche le réel grâce aux fractions continues *)
   let s =  (float_of_int c) /. (float_of_int q) in
   let (d,r) = approx s (float_of_int q) in
-  log "---- Un ordre possible est donc %i. ----\n" r;
+(*  log "---- Un ordre possible est donc %i. ----\n" r;*)
   r
   
 
 let n = 
   if nb_args >= 2 then int_of_string argv.(1)
   else begin
-    print "Veuillez entrer un nombre à factoriser : ";
+    log "Veuillez entrer un nombre à factoriser : ";
     read_int ();
   end
 in
-printf "Le nombre à factoriser est %i.\n" n;
+log "Le nombre à factoriser est %i.\n" n;
 (* Un nombre qui ne divise pas n *)
 let p = 
   if nb_args >= 3 then int_of_string argv.(2)
   else begin
-    print "Veuillez entrer un nombre ne divisant pas n : "; 
+    log "Veuillez entrer un nombre ne divisant pas n : "; 
     read_int ();
   end
 in
-printf "Le nombre qui va nous servir (et qui ne divise pas n) est : %i.\n" p;
+log "Le nombre qui va nous servir (et qui ne divise pas n) est : %i.\n" p;
 (* On peut aussi afficher les graphes d'après de transformée de Fourier avec
  * l'option --print mise en dernière *)
 let printState = nb_args >= 4 && argv.(3) = "--print" in
 (* Vérifications {{{1 *) 
 (* 1) N n'est pas pair *)
 if n mod 2 = 0 then begin
-  print "Erreur : Le nombre à factoriser doit être impair !\n";
+  log "Erreur : Le nombre à factoriser doit être impair !\n";
   exit 0
 end;
 (* 2) Si le nombre est premier *)
 if primeTest n then begin
-  print "Erreur : Le nombre ne doit pas être premier !\n";
+  log "Erreur : Le nombre ne doit pas être premier !\n";
   exit 0
 end;
 (* @TODO
  * 3) Teste si le nombre est la puissance d'un nombre premier (ne fait rien 
  * pour le moment en vérité) *)
 if primePowTest n then begin
-  print "Erreur : le nombre ne doit être la puisance d'un nombre premier !\n";
+  log "Erreur : le nombre ne doit être la puisance d'un nombre premier !\n";
   exit 0
 end;
 (* Teste si 1 <= p <= n - 1 *)
 if 1 > p || p >= n then begin
-  printf "Erreur : l'entier p doit être compris entre 1 et le nombre à factoriser strictement.\n";
+  log "Erreur : l'entier p doit être compris entre 1 et le nombre à factoriser strictement.\n";
   exit 0
 end;
 (* Teste si n et p sont bien premiers entre eux *)
 if pgcd n p <> 1 then begin
-  printf "Pseudo-Succès :  %i | %i (sans passer l'algorithme de Shor).\n" (pgcd p n) n;
+  log "Pseudo-Succès :  %i | %i (sans passer l'algorithme de Shor).\n" (pgcd p n) n;
   exit 0
 end;
 (* }}} *)
 
+(* Tests sur l'ordre {{{1 *)
+let orderFail r p = 
+  (* Si r est impair *)
+  if r mod 2 = 1 then begin
+    log "Erreur : l'ordre est impair (%i), réessayez avec un autre nombre !\n" r;
+    true
+  end
+  (* Si r est congru a -1 modulo n *)
+  else if expModulaire p (r / 2) n = n - 1 then begin
+    log "Erreur : x^(r/2) est congru à -1 modulo n !, un autre entier ?\n";
+    true
+  end else false
+and findFactor r p =
+  let ppow = (expModulaire p (r/2) n) in (*pow p (r / 2) in *)
+  let r1 = pgcd (ppow - 1) n
+  and r2 = pgcd (ppow + 1) n in
+  if isANonTrivialDivisor r1 n then r1
+  else if isANonTrivialDivisor r2 n then r2
+  else 0
+in
+(* }}} *)
+
 (* Ce qui suit peut paraître dérisoire mais c'est pourtant le coeur de notre
  * algorithme et tout notre sujet :) *)
-let r     = order ~print:printState ~texPrint p n in
-let ppow  = pow p (r / 2) in
-
-  (* Tests sur l'ordre {{{1 *)
-(* Si r est impair *)
-if r mod 2 = 1 then begin
-  printf "Erreur : l'ordre est impair (%i), réessayez avec un autre nombre !\n" r;
-  exit 0
-end;
-(* Si r est congru a -1 modulo n *)
-if ppow mod n = n - 1 then begin
-  print "Erreur : x^(r/2) est congru à -1 modulo n !, un autre entier ?\n";
-  exit 0
-end;
-(* }}} *)
 
-(* It's done !! {{{1 *)
-let r1 = pgcd (ppow - 1) n
-and r2 = pgcd (ppow + 1) n in
-if isANonTrivialDivisor r1 n then
-  printf "\nSuccès : %i = %i x %i.\n" n r1 (n / r1)
-else if isANonTrivialDivisor r2 n then
-  printf "\nSuccès : %i = %i x %i.\n" n r2 (n / r2)
-else
-  printf "Impossible de factoriser ce nombre, désolé (r = %i).\n" r;
+(* Et ... {{{1 *)
+let success = ref false 
+and attempts = ref 5 in
+while not !success && !attempts > 0 do
+  let r = order ~print:printState ~texPrint p n in
+  log "Ordre possible trouvé : %i.\n" r; 
+  if not (orderFail r p) then begin
+    let factor = findFactor r p in
+    if factor <> 0 then begin
+      log "\n ---- Succès : %i = %i x %i. ----\n" n factor (n / factor);
+      success := true
+    end
+  end;
+  decr attempts
+done;
+if not !success then
+  log "\nToutes les tentatives ont échouées à factoriser ce nombre.\n";
 (* }}} *)
 
 
 
 let showProb u = 
   let n = u#rows () in
-  let base = 800 / n in
+  let base = if 800 / n = 0 then 1 else 800 / n in
   let swidth = base * n
   and sheight = 300 in
   open_graph (Printf.sprintf " %ix%i" swidth sheight);
   let rec obtainList = function
     | 0 -> []
     | k -> let y = Complex.norm2 (u#row k) in
-      if y > 0.0001 then (k,y) :: (obtainList (k - 1))
+      if y > 0.00001 then (k,y) :: (obtainList (k - 1))
       else obtainList (k - 1)
   and max = List.fold_left (fun a b -> if snd a > snd b then a else b) (0,0.) in
   let data = obtainList (u#rows ()) in
     end
   (* Transformation de Fourier discrète sur les q premiers états {{{2 *)
   method dft q = 
-    let d       = complex_of_float(float_of_int q ** (-0.5)) in
     let dftvals = Array.make q Complex.zero in 
     for a = 0 to q - 1 do
       for c = 0 to q - 1 do
         dftvals.(c) <- dftvals.(c) +! (
           Complex.exp (
             (complex_of_float(2. *. pi /. (float_of_int q) *. float_of_int(a * c)  ) ) *! Complex.i
-          ) *! d *! (state#row (a + 1))
+          ) *! (state#row (a + 1))
         )
       done
     done;