Gabriel Pichot avatar Gabriel Pichot committed 1e7a881

primePowerTest ajouté et quelques modifications peu importantes

Comments (0)

Files changed (6)

   done;
   not !isNotPrime
 (* }}} *)
-(* primePowTest {{{1 @TODO
- * Teste si l'entier n passé en argument n'est pas la puissance d'un nombre
- * premier *)
-let primePowTest n = false
+(* primePowerTest {{{1 
+ * Teste si l'entier n passé en argument n'est pas la puissance d'un nombre *)
+let primePowerTest n = 
+  let nb = [|3;5;7;11;13;17;19;23;29;31|] in
+  let isPrimePower = ref false in
+  let i = ref 0 in
+  while not !isPrimePower && !i < Array.length nb - 1 do
+    let m = ref nb.(!i) in
+    while not !isPrimePower && !m <= n do
+      if !m = n then isPrimePower := true;
+      m := !m * nb.(!i)
+    done;
+    incr i;
+  done;
+  !isPrimePower
 (* }}} *)
 (* Pgcd {{{1 *)
 let rec pgcd a b = match b with 
   | n -> 1 + (nb_bits (n lsr 1))
 
 let order ~texPrint p n = 
-  log "\n---- Recherche de l'ordre de %i dans %i ----\n" p n; 
+  debug "\n---- Recherche de l'ordre de %i dans %i ----\n" p n; 
   let l = getQ n in
   let q = pow 2 l in
   debug "On trouve q = %i = 2 ^ %i.\n" q l;
     (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
+  (* On calcule p ^ a mod n pour tous les a, on doit cependant
    * penser à les conserver (ce que ne peut pas faire un calculateur 
    * quantique) pour les "superposer" avec le premier registre ensuite. *)
   let expModTemp = Array.make n Complex.zero in
   let value = reg2#measureState () in
   (* On doit répercuter cette mesure sur le premier registre *)
   for a = 0 to q - 1 do
-    reg1#setStateProbability a (if sauvExpMod.(a) = value then Complex.one else Complex.zero)
+    let new_val = (if sauvExpMod.(a) = value then Complex.one else Complex.zero) in
+    reg1#setStateProbability a new_val
   done;
   (* Et on oublie pas de normaliser *)
   reg1#normalize ();
   (* Maintenant on applique la transformée de Fourier *)
   debug "Transformée de Fourier.\n"; 
-  reg1#fft (); (* ou reg1#dft q() mais moins performant :) *)
+  reg1#fft (); 
   debug "Fin de la transformée de Fourier.\n";
   reg1#normalize ();
   (* Si on doit afficher le résultat de la transformée de Fourier *)
   let (d,r) = approx s (float_of_int q) in
   debug "---- Un ordre possible est donc %i. ----\n" r;
   r
-  
+
 
 (* }}} *)
 \usepackage[utf8x]{inputenc}
 \usepackage[T1]{fontenc}
 \usepackage[french]{babel}
-\usepackage{braket}
+
 \usepackage{fancybox}
-\usepackage{xstring}
 \usepackage{amsmath}
 \usepackage{amssymb}
 \usepackage{amsfonts}
   \end{center}
 }
 
+
+{
+  \theoremstyle{plain}
+  \theoremseparator{.}
+  \theoremprework{\medskip\hrule\medskip}
+  \theorempostwork{\hrule\bigskip}
+  \theorembodyfont{\sffamily}
+  \newtheorem*{definition}{Définition}
+  \theoremprework{\medskip\hrule\medskip}
+  \theorempostwork{\hrule\bigskip}
+  \newtheorem*{propriete}{Propriété}
+}
+{
+  \theorembodyfont{\normalfont}
+  \theoremsymbol{\ensuremath{\diamondsuit}}
+  \newtheorem*{demonstration}{Démonstration}
+}
+
 \newcommand\@ptsize{}
 \newif\if@restonecol
 \newif\if@titlepage

latex/tipe_dossier_ens.tex

 
 
 \usepackage{lgrind}
+
+\usepackage{tikz}
 \usepackage{pgfplots}
+\usetikzlibrary{calc}
 \usetikzlibrary{external}
 \tikzexternalize[prefix=tikz/]
-\usepackage{tikz}
-\usetikzlibrary{calc}
+
 
 \usepackage[top=2.5cm,bottom=2.5cm,left=2.5cm,right=2.5cm]{geometry}
 \usepackage{stmaryrd}
 \usepackage{mathabx}
-\def\@biblabel#1{}
-\noexpandarg
+\usepackage{xspace}
+\input{common_def.tex}
+
 
-\exploregroups
 %opening
 \title{L'algorithme de \textsc{Shor}}
 \subtitle{À la recherche de l'ordre}
 \scolaryear{2011-2012}
 \author{Gabriel Pichot}
 
-\DeclareMathOperator{\pgcd}{pgcd}
-\newcommand{\abs}[1]{\left| #1 \right|}
-\newcommand{\C}{\ensuremath{\mathbb{C}}}
-\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
-\newcommand{\intEntier}[1]{\ensuremath{\llbracket #1 \rrbracket}}
-\renewcommand{\O}{\ensuremath{\mathcal{O}}}
-\newcommand{\code}[1]{#1}
-\newcommand{\ZnZ}[1]{\ensuremath{\Z\slash #1\Z}}
-{
-  \theoremstyle{plain}
-  \theoremseparator{.}
-  \theoremprework{\medskip\hrule\medskip}
-  \theorempostwork{\hrule\bigskip}
-  \theorembodyfont{\sffamily}
-  \newtheorem*{definition}{Définition}
-  \theoremprework{\medskip\hrule\medskip}
-  \theorempostwork{\hrule\bigskip}
-  \newtheorem*{propriete}{Propriété}
-}
-{
-  \theorembodyfont{\normalfont}
-  \theoremsymbol{\ensuremath{\diamondsuit}}
-  \newtheorem*{demonstration}{Démonstration}
-}
-
-\newcommand\contFrac[1]{\ensuremath{ \StrSubstitute{#1}{//}{+\cfrac{1}}}}
+
 
 %\lstnewenvironment{ocaml}{\lstset{language=(Objective)Caml}}{}
 
 superposition de ces deux composantes. On peut donc représenter un qubit
 $\ket \varphi$ par un vecteur de $\C^2$ :
 \[ \ket \varphi = a \cdot \ket 0 + b \cdot \ket 1 \text{ avec } a,b\in\C \text{
-et } \abs a
-^2 + \abs b ^2 = 1 \]
+et } \abs a ^2 + \abs b ^2 = 1 \]
 où, en utilisant la notation de Paul \textsc{Dirac} : le \emph{ket}, $\ket 0$ et
 $\ket 1$ forment une base de $\C^2$, et correspondent aux deux états possibles. 
 
 %\input{../output/shor_8_15.tex}\\
 %\input{../output/shor_7_99.tex} (143,7)
 \begin{figure}
+  \input{../output/shor_7_15.tex}
 %  \input{../output/shor_13_289.tex}
-  \caption{État du registre après une transformée de Fourier pour $n = 289$ et
-$p = 13$}
+  \caption{État du registre après une transformée de \textsc{Fourier} pour $n =
+289$ et $p = 13$}
 \end{figure}
+\begin{figure}
+% \input{../output/shor_67_1001.tex}
+ \caption{État du registre après une transformée de \textsc{Fourier} pour le
+couple $(67,1001)$}
+\end{figure}
+
 %\input{../output/shor_17_1001.tex}
 
 \appendix
 (*
  * Ce fichier contient le squelette de l'application, vérifications etc.
  * @TODO :
- *  - faire la fonction primePowTest
  *  -? ne pas obliger l'utilisateur à rentrer l'entier p. 
  *)
 open Log;;        (* Log, debug *)
 (* Vérifications {{{1 *) 
 (* 1) N n'est pas pair *)
 if n mod 2 = 0 then begin
-  log "Erreur : Le nombre à factoriser doit être impair !\n";
+  log "Échec : Le nombre à factoriser doit être impair !\n";
   exit 0
 end;
 (* 2) Si le nombre est premier *)
 if primeTest n then begin
-  log "Erreur : Le nombre ne doit pas être premier !\n";
+  log "Échec : 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 
+(* 3) Teste si le nombre est la puissance d'un nombre (ne fait rien 
  * pour le moment en vérité) *)
-if primePowTest n then begin
-  log "Erreur : le nombre ne doit être la puisance d'un nombre premier !\n";
+if primePowerTest n then begin
+  log "Échec : 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
-  log "Erreur : l'entier p doit être compris entre 1 et le nombre à factoriser strictement.\n";
+  log "Échec : 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 *)
 let success = ref false 
 and attempts = ref 5 in
 while not !success && !attempts > 0 do
-  let r = order ~texPrint p n in
+  let r = order ~texPrint:(texPrint && !attempts = 5) p n in
   log "Ordre possible trouvé : %i.\n" r; 
   if not (orderFail r p) then begin
     let factor = findFactor r p in
   done;
   out := !out ^ "  \\foreach \\x in {0,2,...,16} \\draw (\\x,0) -- (\\x,0.2);
     \\draw[very thick] plot[ycomb] coordinates {\n";
-  output_string file (!out ^ s ^ "};\n\\end{tikzpicture}")
+  output_string file (!out ^ s ^ "};\n\\end{tikzpicture}");
+  close_out file
 ;;
    
 
         self#rowset (i + 1) s.(i)
       done;
     end
-  method setStateProbability s v = self#rowset (s+1) v
-  method getStateProbability s = 
-    if s > self#nbStates then raise (Quant_Bad_Access "getStateProbability")
-    else self#row (s+1)
+  method setStateProbability s v = self#rowset (s + 1) v
   method dump () =
     printf "Le registre est dans l'état (norme %f):\n" (self#norm () );
     for i = 1 to self#rows do
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.