# # Dixon's random squares factoring # Important in theory. # find values x, y with x^2=y^2 #mod N # The real problem is finding so called smooth quadratic # residues (mod N). Continued fraction and variants of the # quadratic sieve are common. # Matrix algebra is a bottleneck in large problems because of # the vast amount of memory required. # Z<-RANDOM_SQUARES STR;B;E;FB;FW;I;J;M;NR;NC;QV;SZ;X;Y;XI;XSQ |Random squares method B<-100; QV<-0; SZ<-#screen FW<- -1+rM<-"-b B<-#fi SHIFT|-v QV<-1" GETOPTS STR Z<-0 r 5 #sed":d"; I<-J<-0; MA<-i0; XLIST<-"" #print "M= ",M #print "digits= ### digit sum= ####" z (rM), +/(#av M)-#av "0" NR<-16+NC<-rFB<-2, SIEVE (B+1)%2 #print "b= ###### [####] " z B, rFB #print "ufb=", z FB #print "#","matrix #### ####" z NR, NC WHILE J0 NR<-#fi (\$T[Z]) YDX 1 XS<-(NR,FW) t TAB<-\$T[Z+1+iNR]; MA<-(NR,-NC) t TAB E<-~f/MA="."; NC<-rFB<-E/FB;MA<-E/MA | Crunch blank columns IF 00 I<-I/irI X<-M C_PRODUCT XS[DM+I] Y<-PRODUCT ((+/MA[DM+I])%2)/FB Y<-Y #mod M #print V<-"(x,y) ",X," ",Y; IF QV;V I<-M EA X+Y |Here we have X^2=Y^2 #mod M BREAKIF ~ (I #equiv "1") c I #equiv M #print V<-"trivial factor"; IF QV;V DM++; WEND #print Z<-I," ",M%I; IF QV; Z # # Relations amongst rows # Find a set of rows which sum to zero (mod 2) # Z<-QS Z2_SCAN_ROWS X;C;DX;DZ;I;J;K;NR;NC;R |Brute force attempt to return a set of rows which sum to zero |It is slow for large sets QS<-0 #ifndef "QS" | Slider Z<-(iNR<-1tr:X) #outer = iNC<-1dr:X; I<-0 WHILE I0)/iNC; Z<-Z[I]; ->0 | A row sum is zero C<-,X[:J<-1tJ]; K<-(C[K] * I #ne K)/K<-iNR; DX<-(rK)/:R; DZ<-(rK)/:Z[I] X[K]<-X[K] #ne DX; Z[K]<-Z[K] #ne DZ I++ WEND Z<-V_SLIDER CX |Progress bar. position, fraction<1 Z<-"X."[((50*CX[2])%CX[3])<=i50] Z<-0 r Z #wput CX[0 1],1, rZ Z<-M C_PRODUCT TAB;I;NR |Product of long table mod M Z<-"1"; I<-0; NR<-1tr:TAB WHILE I0 Z<-0 r 5 #sed":d"; I<-J<-0; MA<-i0; XLIST<-"" NR<-16+NC<-rFB<-2, SIEVE (B+1)%2 #print "M= ",M #print "digits= ### digit sum= ####" z (rM), +/(#av M)-#av "0" #print "b= ###### [####] " z B, NC #print "ufb=", zFB #print "#","matrix #### ####" z NR, NC P<-"0" & Q<-"1" & I<-0 & AC<-"0 1" WHILE I0 #print V<-(FWtX),(FWtXSQ)," ", ".o"[XI]; I++ (SZ[1]-8) t ("####/#### "z I,NR ), V WEND #print "#end" IF QV; #sed":u cfrac.log" "Matrix phase" Z<-RSQ_MATRIX_PHASE"-w 5 -v" IF QV; #sed":u cfrac.log" Z<-QUAD_ZERO STR;A;E;FB;FW;I;J;M;NR;NC;QV;SQRTM;SZ;T;V;X;XI;XSQ |Use values X*X-M. Try to factorize at once, without sieve B<-100; QV<-0; SZ<-#screen FW<- -1+rM<-"-b B<-#fi SHIFT|-v QV<-1" GETOPTS STR Z<-0 r 5 #sed":d"; I<-J<-0; MA<-i0; XLIST<-"" SQRTM<-Y_SQRT M #print "M= ",M #print "digits= ### digit sum= ####" z (rM), +/(#av M)-#av "0" NR<-16+NC<-rFB<-2, SIEVE (B+1)%2 #print "b= ###### [####] " z B, rFB #print "ufb=", z FB #print "#","matrix #### ####" z NR, NC I<-J<-0 WHILE I