// xcas version=0.7.3 fontsize=20 font=0 // fltk 7Fl_Tile 23 74 920 49 20 0 [ // fltk N4xcas23Comment_Multiline_InputE 23 74 920 49 20 0 Construction d'un entier produit de 2 premiers, et decomposition en utilisant£les fractions continues (cf. Cohen chapitre 10.1) , // fltk N4xcas10Log_OutputE 23 123 920 0 20 0 ] , // fltk 7Fl_Tile 23 125 920 54 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 125 920 30 20 0 nextprime(1000) , // fltk N4xcas10Log_OutputE 23 155 920 1 20 0 , // fltk N4xcas8EquationE 23 156 920 23 20 0 1009 ] , // fltk 7Fl_Tile 23 181 920 54 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 181 920 30 20 0 nextprime(2000) , // fltk N4xcas10Log_OutputE 23 211 920 1 20 0 , // fltk N4xcas8EquationE 23 212 920 23 20 0 2003 ] , // fltk 7Fl_Tile 23 237 920 54 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 237 920 30 20 0 N:=1009*2003 , // fltk N4xcas10Log_OutputE 23 267 920 1 20 0 , // fltk N4xcas8EquationE 23 268 920 23 20 0 2021027 ] , // fltk 7Fl_Tile 23 293 920 54 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 293 920 30 20 0 (3*N) %4 , // fltk N4xcas10Log_OutputE 23 323 920 1 20 0 , // fltk N4xcas8EquationE 23 324 920 23 20 0 1%4 ] , // fltk 7Fl_Tile 23 349 920 82 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 349 920 30 20 0 l1:=dfc(sqrt(3*N),8) , // fltk N4xcas10Log_OutputE 23 379 920 1 20 0 , // fltk N4xcas8EquationE 23 380 920 51 20 0 [2462,3,122,1,3,1,1,1,(sqrt(6063081)+971)/2320] ] , // fltk 7Fl_Tile 23 433 920 78 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 433 920 30 20 0 xf:=dfc2f(l1[0..(size(l1)-2)]) , // fltk N4xcas10Log_OutputE 23 463 920 1 20 0 , // fltk N4xcas8EquationE 23 464 920 47 20 0 12732721/5171 ] , // fltk 7Fl_Tile 23 513 920 54 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 513 920 30 20 0 x:=numer(xf) , // fltk N4xcas10Log_OutputE 23 543 920 1 20 0 , // fltk N4xcas8EquationE 23 544 920 23 20 0 12732721 ] , // fltk 7Fl_Tile 23 569 920 54 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 569 920 30 20 0 t:=x*x %N , // fltk N4xcas10Log_OutputE 23 599 920 1 20 0 , // fltk N4xcas8EquationE 23 600 920 23 20 0 2320%2021027 ] , // fltk 7Fl_Tile 23 625 920 64 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 625 920 30 20 0 ifactor(abs(t%0)) , // fltk N4xcas10Log_OutputE 23 655 920 1 20 0 , // fltk N4xcas8EquationE 23 656 920 33 20 0 2^4*5*29 ] , // fltk 7Fl_Tile 23 691 920 31 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 691 920 30 20 0 , // fltk N4xcas10Log_OutputE 23 721 920 1 20 0 ] , // fltk 7Fl_Tile 23 724 920 333 20 0 [ // fltk N4xcas7EditeurE 23 724 920 265 20 0 239 , ktox(k,N,taille):={ local l1,x,t; // if ((k*N)%4!=1%4) return undef; l1:=dfc(sqrt(k*N),taille); x:=numer(dfc2f(l1[0..(taille-1)])); x:=(x%N)%0; t:=((x*x)%N) % 0; if (t==x*x) return undef; return x,t,ifactor(abs(t)); }:;, // fltk N4xcas10Log_OutputE 23 989 920 45 20 0 // Parsing ktox£// Success compiling ktox£ , // fltk N4xcas8EquationE 23 1034 920 23 20 0 "Done" ] , // fltk 7Fl_Tile 23 1059 920 31 20 0 [ // fltk N4xcas23Comment_Multiline_InputE 23 1059 920 30 20 0 Essai avec une reduite de sqrt(2*N), on a de la chance tout de suite! , // fltk N4xcas10Log_OutputE 23 1089 920 1 20 0 ] , // fltk 7Fl_Tile 23 1092 920 63 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 1092 920 29 20 0 ktox(2,N,2) , // fltk N4xcas10Log_OutputE 23 1121 920 1 20 0 , // fltk N4xcas8EquationE 23 1122 920 33 20 0 4021,225,3^2*5^2 ] , // fltk 7Fl_Tile 23 1157 920 31 20 0 [ // fltk N4xcas23Comment_Multiline_InputE 23 1157 920 31 20 0 donc 4021^2=15^2 mod N, on peut factoriser , // fltk N4xcas10Log_OutputE 23 1188 920 0 20 0 ] , // fltk 7Fl_Tile 23 1190 920 53 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 1190 920 29 20 0 gcd(N,4021+15) , // fltk N4xcas10Log_OutputE 23 1219 920 1 20 0 , // fltk N4xcas8EquationE 23 1220 920 23 20 0 1009 ] , // fltk 7Fl_Tile 23 1245 920 31 20 0 [ // fltk N4xcas23Comment_Multiline_InputE 23 1245 920 30 20 0 Essai avec d'autres reduites on garde les petits des petits facteurs premiers (disons<=7) , // fltk N4xcas10Log_OutputE 23 1275 920 1 20 0 ] , // fltk 7Fl_Tile 23 1278 920 266 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 1278 920 30 20 0 for (j:=1;j<=10;j++) print("j:="+j,ktox(11,N,j)); , // fltk N4xcas10Log_OutputE 23 1308 920 213 20 0 "j:=1",4715,-72,2^3*3^2£"j:=2",612951,9101,19*479£"j:=3",617666,-261,3^2*29£"j:=4",undef£"j:=5",617414,-2263,31*73£"j:=6",448593,232,2^3*29£"j:=7",371891,-3783,3*13*97£"j:=8",-828652,3584,2^9*7£"j:=9",735614,-1227,3*409£"j:=10",278592,2583,3^2*7*41£ , // fltk N4xcas8EquationE 23 1521 920 23 20 0 1 ] , // fltk 7Fl_Tile 23 1546 920 69 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 1546 920 29 20 0 ktox(11,N,1) , // fltk N4xcas10Log_OutputE 23 1575 920 0 20 0 , // fltk N4xcas8EquationE 23 1575 920 40 20 0 4715,-72,2^3*3^2 ] , // fltk 7Fl_Tile 23 1617 920 64 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 1617 920 30 20 0 ktox(11,N,8) , // fltk N4xcas10Log_OutputE 23 1647 920 1 20 0 , // fltk N4xcas8EquationE 23 1648 920 33 20 0 -828652,3584,2^9*7 ] , // fltk 7Fl_Tile 23 1683 920 64 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 1683 920 30 20 0 ktox(3,N,2) , // fltk N4xcas10Log_OutputE 23 1713 920 1 20 0 , // fltk N4xcas8EquationE 23 1714 920 33 20 0 7387,40,2^3*5 ] , // fltk 7Fl_Tile 23 1749 920 64 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 1749 920 30 20 0 ktox(15,N,8) , // fltk N4xcas10Log_OutputE 23 1779 920 1 20 0 , // fltk N4xcas8EquationE 23 1780 920 33 20 0 957688,420,2^2*3*5*7 ] , // fltk 7Fl_Tile 23 1815 920 64 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 1815 920 30 20 0 ktox(23,N,3) , // fltk N4xcas10Log_OutputE 23 1845 920 1 20 0 , // fltk N4xcas8EquationE 23 1846 920 33 20 0 61361,-980,2^2*5*7^2 ] , // fltk 7Fl_Tile 23 1881 920 64 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 1881 920 30 20 0 ktox(43,N,12) , // fltk N4xcas10Log_OutputE 23 1911 920 1 20 0 , // fltk N4xcas8EquationE 23 1912 920 33 20 0 498122,40,2^3*5 ] , // fltk 7Fl_Tile 23 1947 920 31 20 0 [ // fltk N4xcas23Comment_Multiline_InputE 23 1947 920 30 20 0 donc 498122^2=7387^2 mod N -> on obtient un facteur , // fltk N4xcas10Log_OutputE 23 1977 920 1 20 0 ] , // fltk 7Fl_Tile 23 1980 920 54 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 1980 920 30 20 0 gcd(498122-7387,N) , // fltk N4xcas10Log_OutputE 23 2010 920 1 20 0 , // fltk N4xcas8EquationE 23 2011 920 23 20 0 2003 ] , // fltk 7Fl_Tile 23 2036 920 64 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 2036 920 30 20 0 ktox(35,N,4) , // fltk N4xcas10Log_OutputE 23 2066 920 1 20 0 , // fltk N4xcas8EquationE 23 2067 920 33 20 0 126157,1024,undef*2^10 ] , // fltk 7Fl_Tile 23 2102 920 31 20 0 [ // fltk N4xcas23Comment_Multiline_InputE 23 2102 920 30 20 0 on peut aussi conclure avec x=126157 car 2^10 est un carre , // fltk N4xcas10Log_OutputE 23 2132 920 1 20 0 ] , // fltk 7Fl_Tile 23 2135 920 54 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 2135 920 30 20 0 gcd(126157-2^5,N) , // fltk N4xcas10Log_OutputE 23 2165 920 1 20 0 , // fltk N4xcas8EquationE 23 2166 920 23 20 0 1009 ] , // fltk 7Fl_Tile 23 2191 920 64 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 2191 920 30 20 0 ktox(99,N,1) , // fltk N4xcas10Log_OutputE 23 2221 920 1 20 0 , // fltk N4xcas8EquationE 23 2222 920 33 20 0 14145,-648,2^3*3^4 ] , // fltk 7Fl_Tile 23 2257 920 64 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 2257 920 30 20 0 ktox(107,N,5); ktox(107,N,7) , // fltk N4xcas10Log_OutputE 23 2287 920 1 20 0 , // fltk N4xcas8EquationE 23 2288 920 33 20 0 724449,-840,2^3*3*5*7,-682349,-405,3^4*5 ] , // fltk 7Fl_Tile 23 2323 920 205 20 0 [ // fltk N4xcas23Comment_Multiline_InputE 23 2323 920 205 20 0 calcul de la matrice pour£498122,40,2^3*5£-828652,3584,2^9*7£957688,420,2^2*3*5*7£61361,-980,2^2*5*7^2£14145,-648,2^3*3^4£724449,-840,2^3*3*5*7£682349,-405,3^4*5£4715,-72,2^3*3^2£bases 2,3,5,7 , // fltk N4xcas10Log_OutputE 23 2528 920 0 20 0 ] , // fltk 7Fl_Tile 23 2530 920 334 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 2530 920 30 20 0 M:=[[0,3,0,1,0],[0,9,0,0,1],[0,2,1,1,1],[1,2,0,1,2],[1,3,4,0,0],[1,3,1,1,1],[1,0,4,1,0],[1,3,2,0,0]] , // fltk N4xcas10Log_OutputE 23 2560 920 1 20 0 , // fltk N4xcas8EquationE 23 2561 920 303 20 0 [[0,3,0,1,0],[0,9,0,0,1],[0,2,1,1,1],[1,2,0,1,2],[1,3,4,0,0],[1,3,1,1,1],[1,0,4,1,0],[1,3,2,0,0]] ] , // fltk 7Fl_Tile 23 2866 920 174 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 2866 920 30 20 0 ker(tran(M%2)) , // fltk N4xcas10Log_OutputE 23 2896 920 1 20 0 , // fltk N4xcas8EquationE 23 2897 920 143 20 0 [[1%2,0%2,0%2,1%2,1%2,0,0,0],[1%2,0%2,1%2,1%2,0,1%2,0,0],[0%2,0%2,0%2,1%2,0,0,1%2,0],[1%2,0%2,0%2,1%2,0,0,0,1%2]] ] , // fltk 7Fl_Tile 23 3042 920 31 20 0 [ // fltk N4xcas23Comment_Multiline_InputE 23 3042 920 31 20 0 Les 3 premiers elements du noyau ne donnent rien (pas de chance!), le 4eme , // fltk N4xcas10Log_OutputE 23 3073 920 0 20 0 ] , // fltk 7Fl_Tile 23 3075 920 54 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 3075 920 30 20 0 X:=498122*61361*4715 , // fltk N4xcas10Log_OutputE 23 3105 920 1 20 0 , // fltk N4xcas8EquationE 23 3106 920 23 20 0 144115219958030 ] , // fltk 7Fl_Tile 23 3131 920 54 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 3131 920 30 20 0 X*X%N , // fltk N4xcas10Log_OutputE 23 3161 920 1 20 0 , // fltk N4xcas8EquationE 23 3162 920 23 20 0 801373%2021027 ] , // fltk 7Fl_Tile 23 3187 920 51 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 3187 920 27 20 0 (M[0]+M[3]+M[7])/2; Y:=2^4*3*5*7; , // fltk N4xcas10Log_OutputE 23 3214 920 1 20 0 , // fltk N4xcas8EquationE 23 3215 920 23 20 0 [1,4,1,1,1],1680 ] , // fltk 7Fl_Tile 23 3240 920 53 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 3240 920 29 20 0 Y*Y%N , // fltk N4xcas10Log_OutputE 23 3269 920 1 20 0 , // fltk N4xcas8EquationE 23 3270 920 23 20 0 801373%2021027 ] , // fltk 7Fl_Tile 23 3295 920 51 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 3295 920 27 20 0 gcd(X+Y,N) , // fltk N4xcas10Log_OutputE 23 3322 920 1 20 0 , // fltk N4xcas8EquationE 23 3323 920 23 20 0 1009 ] , // fltk 7Fl_Tile 23 3348 920 28 20 0 [ // fltk N4xcas23Comment_Multiline_InputE 23 3348 920 28 20 0 On peut aussi exploiter des relations ou on a tout factorise sauf un meme grand premier , // fltk N4xcas10Log_OutputE 23 3376 920 0 20 0 ] , // fltk 7Fl_Tile 23 3378 920 53 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 3378 920 29 20 0 ktox(5,N,9) , // fltk N4xcas10Log_OutputE 23 3407 920 1 20 0 , // fltk N4xcas8EquationE 23 3408 920 23 20 0 546144,-1059,3*353 ] , // fltk 7Fl_Tile 23 3433 920 53 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 3433 920 29 20 0 ktox(5,N,10) , // fltk N4xcas10Log_OutputE 23 3462 920 1 20 0 , // fltk N4xcas8EquationE 23 3463 920 23 20 0 -947275,706,2*353 ] , // fltk 7Fl_Tile 23 3488 920 31 20 0 [ // fltk N4xcas19Multiline_Input_tabE 23 3488 920 30 20 0 , // fltk N4xcas10Log_OutputE 23 3518 920 1 20 0 ]