# # circle group mod M # Zm = integers mod M # use the multiplicative group of the ring Zm[X]/(1+X^2) # This is a non trivial group for all M. # Z<-SM_POINT M;T |Random point x,y with x^2+y^2 mod M WHILE M #equiv Z<-"1"+T*T<-YRAND M; WEND IF "z" = 1tZ<-Z YMOD_INV M; ->0 Z<-(("2"*Z*T) YMOD M)," ",(Z*(T*T)-"1") YMOD M Z<-M SM_PLUS STR;A;B;C;D |Add two points in circle group mod M |Each point is an x,y pair A<-SHIFT;B<-SHIFT;C<-SHIFT;D<-SHIFT Z<-((A*C)-B*D) YMOD M Z<-Z," ",((A*D)+B*C) YMOD M Z<-M SM_DOUBLE STR;P;Q |Point doubling routine on circle mod M P<-SHIFT;Q<-SHIFT Z<-((P*P)-Q*Q) YMOD M Z<-Z," ",("2"*P*Q) YMOD M Z<-M SM_MULT STR;K;P |compute [K] P for circle mod M K<-SHIFT; P<-STR; Z<-"1 0" WHILE ~K #equiv "0" IF ODD K; Z<-M SM_PLUS Z," ",P K<-K%"2"; P<-M SM_DOUBLE P WEND Z<-M SM_TABLE STR;MAX;P;Q;DP |Return a table of points [2i]P for i=1 to N as a (N,W) matrix MAX<-#fi SHIFT;P<-STR I<-1; Z<-_CR,"1 0",_CR, Q<-DP<-M SM_DOUBLE P WHILE I0 K<-0; LST<-Y_PNPP B WHILE K0 WEND | stage two PB<-P; MAX<-c/LST; B2<-10*B; LST<-(LST>MAX)/LST<-SIEVE 400000 f (B2+1)%2 R<-Q<-1tLST; DQ<-(1dLST)-_1dLST DTAB<-M SM_TABLE (zc/DQ)," ",PB | Build table IF QV; V<-(zR)," ",P & 72tV P<-M SM_MULT (zQ)," ",PB BREAKIF ~"1" #equiv Z<-M EA Y_PRODUCT P K<-0 WHILE Kfactor list B<-"1000"; QV<-0 SRC<-"-b B<-SHIFT|-v QV<-1" GETOPTS STR<-"" #ifndef "STR" IF 0=rSRC; SRC<-"tmp.num" IF 0= #fstat SRC; Z<-1; ->0 |Get last componenent of hard to factor set LST<-"";I<-0; N<-1tr:Z<- #sed"X:r",SRC,";v/p/;s/.*->//*;:cm" WHILE I", G & 72tV WEND