load "collision.m"; function Extfld1(m1,p,n,r,t,rnd,step0,g,h); t2:=Cputime(); for ii in [1..1] do number:=3; rnd1:=Random(m1); F:=GF(p,n); FF:=GF(p);SET:={0,1}; Graph:={,}; f:=mapSET|Graph>; V,phi:=VectorSpace(F,GF(p)); G0:=Eltseq(g^rnd1); Z:=IntegerRing(); L:=Transpose(Matrix(Z,1,t,[2^(a-1): a in [1..t]])); s0:=0; for a in [1..t] do s0:=s0 + f(G0[n-t+a])*L[a,1]; end for; s0:=Modexp(s0,1,r) + 1; D1:=[0,0];D2:=[0,0];D3:=[F!(0),F!(0)]; F1:=FiniteField(m1); M1:=Matrix(F1,1,r,[]); M2:=Matrix(F1,1,r,[]); M3:=Matrix(F,1,r,[]); for i in [1..r] do ex11:=Random(m1-1)+1; ex12:=Random(m1-1)+1; M1[1,i]:=ex11; M2[1,i]:=ex12; M3[1,i]:=(g^ex11)*(h^ex12); end for; alpha:=F1!(rnd1); beta:=F1!(0); t1:=0;z3:=0;fail:=1;s00:=0;e1:=0;e2:=0;e3:=0;e4:=0; g0:=g^rnd1; for j in [1..10*Floor(10^6)] do g0:=g0*M3[1,s0]; G0:=phi(g0); s0:=0; for a in [1..t] do s0:=s0 + f(G0[n-t+a])*L[a,1]; end for; s0:=Modexp(s0,1,r) + 1; alpha:=alpha + M1[1,s0]; beta:=beta + M2[1,s0]; if (s0 eq 3) then s00:=s00+1; else s00:=0; end if; if (s00 eq 5) then s00:=0; ans,g0,alpha,beta,t1,z3,D1,D2,D3:=collision(m1,z3,p,n,g,h,rnd,g0,step0,alpha,beta,D1,D2,D3); end if; if (t1 eq 1) then number:=j/Sqrt(m1); fail:=0; break; end if; end for; t2:=Cputime(); print "time:=",t2,"L:=",number; end for; return fail,t2; end function;