#
# 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 I<MAX; Z<-Z,_CR, Q<-M SM_PLUS Q, " ", DP; I++; WEND
Z<-#sstomat Z

Z<-SM_FACTOR STR;B;B2;DQ;DTAB;K;LST;M;MAX;P;PB;Q;R;QV;V
|Factorize by chasing circle orbits (mod M)
B<-1000 & QV<-0 & B2<-10000
M<-"-b B<-#fi SHIFT|-v QV<-1" GETOPTS STR
IF "z"=1tZ<-P<-SM_POINT M; ->0
K<-0; LST<-Y_PNPP B
WHILE K<rLST; Q<-zLST[K++]
IF QV; V<-Q," ",P & 72tV
P<-M SM_MULT Q," ",P
IF ~"1" #equiv Z<-M EA Y_PRODUCT P; ->0
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 K<rDQ; Q<-DQ[K++]; P<-M SM_PLUS P," ", #deb DTAB[Q%2]; R<-R+Q
IF QV; V<-(zR)," ",P & 72tV
BREAKIF ~"1" #equiv Z<-M EA Y_PRODUCT P
WEND

Z<-SM_TEST STR;B;F;G;H;I;N;LST;SRC;QV;V
|Test circle group factoring on a file
|The file is normally output of a previous factoring run.
|the format is number->factor 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<N; LST<-LST,_CR,(#deb Z[I]) YDX _1; I++; WEND
Z<-3 #sed":d"; N<-1tr:LST<-#sstomat LST; I<-0
WHILE I<N; H<-#deb LST[I++ :]
REPEATIF "1" #equiv "3" FTEST H
"H= ",H
G<-SM_FACTOR (QV/"-v "),"-b ",B ," ",H
3 #print V<-H,"->", G & 72tV
WEND