restart;maple_mode(0);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); //radians,pas de cmplx, pas de Sqrt // fltk N4xcas23Comment_Multiline_InputE 20 599 916 42 12 bete comme le crible d'eratostene sont en O(p), et bete n'use pas de memoire.£ donc asymptotiquement, le crible n'est pas avantageux. // fltk 7Fl_Tile 27 324 909 174 12 [ // fltk N4xcas7EditeurE 27 324 909 173 12 239 , bete(n):={ j:=3; a:=0; SQ:=evalf(sqrt(n)); //pour ne le faire qu'une fois. ne pas le mettre dans le while! while (j0 then j:=j+2; else a:=j;j:=n; fi ; }; if a<>0 then a; else n fi; }; j:=4;N:=nextprime(10^j+5432)*nextprime(2*10^j+1234); bete(N); j:=5;N:=nextprime(10^j+5432)*nextprime(2*10^j+1234); //j=6 passe encore mais... bete(N); // fltk N4xcas23Comment_Multiline_InputE 20 599 916 42 12 Attention, pour que la suite r\'ecurrente soit bien programmee, il ne faut pas£ recalculer tous les termes jusque u_i ni u_2i a chaque etape! // fltk 7Fl_Tile 27 324 909 159 12 [ // fltk N4xcas7EditeurE 27 324 909 158 12 186 , pollard(n) :={ local x,y ; x:=1; y:=x^2+1; while (member ( igcd(y-x,n) , set[1,n] )) { x:=irem((x^2+1), n) ; y:=irem((y^2+1)^2+1, n) ; }; igcd(y-x,n); }; N:=nextprime(10^6)*nextprime(2*10^6):; pollard(N); N:=nextprime(10^8+5*rand(1000))*nextprime(2*10^8+11*rand(1000)):; pollard(N); // fltk N4xcas23Comment_Multiline_InputE 20 599 916 28 12 pollard est en O(sqrt(p)) ssi la fonction suivante est bornee. // fltk 7Fl_Tile 27 324 909 174 12 [ // fltk N4xcas7EditeurE 27 324 909 173 12 209 , comptep(n):={ local x,y,j ; x:=1; y:=x^2+1 ;j:=0; while (member ( igcd(y-x,n) , %{1,n%} )) { x:=irem(x^2+1,n) ; y:=irem((y^2+1)^2+1, n) ; j:=j+1; } evalf(j/sqrt(igcd(y-x,n))); }; // fltk N4xcas23Comment_Multiline_InputE 20 599 916 71 12 On cr\'ee une liste de valeurs. Il ne faut pas des nombres trop petits pour que£pollard ait de bonne chance d'aboutir. On fait imprimer a chaque etape pour£voir s'il blocque a une etape.£On met des floor pour les grands rand car il bascule en flottant a partir de 2^31 // fltk N4xcas19Multiline_Input_tabE 20 415 916 231 12 l:=[]; £ for(j:=7;j<31;j++){£ N:=nextprime(floor(rand(3^(j))))*nextprime(floor(rand(2^(j+1))));£ t:=comptep(N);£ print(j,t);£ l:=append(l,t);£ N:=nextprime(floor(rand(3^(j))))*nextprime(floor(rand(2^(j+1))));£ t:=comptep(N);£ print(j,t);£ l:=append(l,t);£ N:=nextprime(floor(rand(3^(j))))*nextprime(floor(rand(2^(j+1))));£ t:=comptep(N);£ print(j,t);£ l:=append(l,t);£ }; plotlist(l); //ca a bien l'air borne P:=i0->product(1-j/p,j=1..i0-1); i0:=2;limit(log(P(i0))/(i0*(i0-1)/2/p),p,+infinity); // fltk N4xcas23Comment_Multiline_InputE 20 599 916 28 12 On devine que P(i0) equivaut a: -i0*(i0-1)/(2p), on l'illustre ainsi: l:=limit(log(P(2))/(i0*(i0-1)/2/p),p,+infinity); for i0 from 3 to 50 do l:=l,limit(log(P(i0))/(i0*(i0-1)/2/p),p,+infinity) od; // fltk N4xcas23Comment_Multiline_InputE 20 599 916 42 12 Puisque ln est croissante, on se demande quand ln(P(i0))>ln(0.5). On compare£ donc -ln(0.5) avec i0^2/2p sqrt(-2*ln(0.5)); //ca fait a peu pres le 1.18 de l'enonce // fltk N4xcas23Comment_Multiline_InputE 20 599 916 71 12 u_2i=u_i est mauvais pour cette suite recurent, c'est en O(p) comme la methode bete.£ En effet u_2i=a^i u_i +c(a^i-1)/(a-1) [p], donc u_2i=u_i ssi£ (a^i-1)(-ui+c/(a-1))=0[p]. Mais a^i=1[p] par ex si a generateur,£ alors i>=p-1 // fltk N4xcas23Comment_Multiline_InputE 20 599 916 28 12 illustration: on fait afficher le rapport entre le nombre de tours et sqrt(p). a:=54321123;c:=nextprime(10^4); // fltk 7Fl_Tile 27 324 909 174 12 [ // fltk N4xcas7EditeurE 27 324 909 173 12 229 , comptelin(n,a,c):={ local x,y ; x:=1; y:=irem(a*x+c, n) ;j:=0; while (member ( igcd(y-x,n) , %{1,n%} )) { x:=irem(a*x+c, n) ; y:=irem((a*(a*y+c)+c) , n) ; j:=j+1; }; evalf(j/sqrt(igcd(y-x,n))); }; l:=[];rand(3^4); // fltk N4xcas19Multiline_Input_tabE 20 415 916 100 12 for(i0:=4;i0<20;i0++){ £ N:=nextprime(rand(3^i0))*nextprime(rand(2^(i0+1)));£ t:=comptelin(N,a,c);£print(i0,t);£l:=append(l,t);£}; plotlist(l); // ca n'a plus l'air borne l:=[seq(rand(2),j=1..100)]:; histogram(classes(l,0,1)); //On commence a 0, largeur constante 1. l:=[seq(rand(2),j=1..1000)]:; histogram(classes(l,0,1)); N:=nextprime(10^6)*nextprime(2*10^6); u:=n->if n=0 then 2 else irem(((u(n-1))^2+1) ,N) fi; u(10); // u(10000);Error, (in u) too many levels of recursion // fltk N4xcas19Multiline_Input_tabE 20 415 916 144 12 etudesuite(n,M):={ £ local x,l; £ x:=12345;l:=[];£ for(i0:=1;i0<=M;i0++){£ x:=irem((x^2+1), n) ; £ l:=[op(l),x];£ }; £ l; £ }; donnees:=(etudesuite(N,2000)); cldonnees:=classes(donnees,0,N/40); //40 classes diagramme_batons(cldonnees); //on peut cacher les noms dans le menu Cfg // fltk N4xcas19Multiline_Input_tabE 20 415 916 158 12 etudesuite2(n,M):={ £ local x,y,l; £ x:=12345;l:=[];£ for(i0:=1;i0<=M;i0++){£ x:=irem((x^2+1), n) ;£ y:=irem((y^2+1)^2+1, n);£ l:=[op(l),[x,y]];£ }; £ l; £ }; couples:=(etudesuite2(N,200)); scatterplot(couples); // fltk N4xcas23Comment_Multiline_InputE 20 599 916 28 12 l'hypothese d'independance semble raisonable. // fltk N4xcas23Comment_Multiline_InputE 20 599 916 57 12 -----------------Test d'une variante de pollard------------------------------------------£ cette variante de pollard pour minimiser le nombre de igcd n'apporte pas d'amalioration£ sous xcas, elle me semble meme un peu plus longue!!!!!!! // fltk 7Fl_Tile 27 324 909 304 12 [ // fltk N4xcas7EditeurE 27 324 909 303 12 439 , pollard2(n) :={ local x,y,c,yy,xx,pp ; xx:=1; yy:=xx^2+1 ;pp:=1; while ((igcd(pp,n)==1)) { x:=xx;y:=yy; for c from 1 to 20 do xx:=irem((xx^2+1) , n) ; yy:=irem((yy^2+1)^2+1, n) ; pp:=irem(pp*(xx-yy) , n); od ; } while ( igcd(y-x,n)==1 ) { x:=irem(x^2+1 , n) ; y:=irem((y^2+1)^2+1 , n) ; } pp:=igcd(y-x,n); if (pp<>n) then pp else print("pas trouve") fi; }:; N:=nextprime(10^6)*nextprime(2*10^6):; pollard2(N); N:=nextprime(10^8+5*rand(1000))*nextprime(2*10^8+11*rand(1000)):; pollard2(N); pollard(N);