📄 schoof2.cpp
字号:
XX=X;
YP=MFX;
XP2=1;
// Find X^P and Y^P together wrt new small modulus
cout << "Y^P" << flush;
for (jj=0;jj<M-1;jj++)
{
XP2*=XX;
XP2*=XP2;
YP*=YP;
YP+=(XP2*MFX);
}
YPy=XP2*XX;
XP=YPy*XX;
cout << "\b\b\b";
cout << "NP mod " << lp << " = " << flush;
SX=inverse(XX);
for (jj=0;jj<5;jj++)
{
Pf[jj]=(Poly2Mod)P[jj];
P2f[jj]=(Poly2Mod)P2[jj];
P3f[jj]=(Poly2Mod)P3[jj];
}
// if (lp%2==0) cout << "\n GCD(XX,Fl)= " << gcd(XX) << endl;
low=5;
for (lambda=1;lambda<=lp/2;lambda++)
{ // eigenvalue search
Poly2Mod Tx,Hx,Ax,Bx,Pf3,Pft;
tau=(lambda+invers(lambda,lp)*p)%lp;
cout << setw(4) << (p+1-tau)%lp << flush;
for (jj=low;jj<=lambda+2;jj++)
{
if (jj%2==1)
{
n=(jj-1)/2;
Pf[jj]=Pf[n+2]*P3f[n]+P3f[n+1]*Pf[n-1];
}
else
{
n=jj/2;
Pf[jj]=SX*Pf[n]*(Pf[n+2]*P2f[n-1]+Pf[n-2]*P2f[n+1]);
}
P2f[jj]=Pf[jj]*Pf[jj];
P3f[jj]=P2f[jj]*Pf[jj];
}
if (lambda+3>low) low=lambda+3;
Pft=Pf[lambda-1]*Pf[lambda+1];
Tx=(XP+XX)*P2f[lambda]+Pft;
if (degree(gcd(Tx))!=0)
{ // Got it! Now check Y-coord for correct sign
if (lambda==1)
{
Ax=YP;
Bx=YPy+one;
}
else
{
Pf3=P3f[lambda];
Pft*=Pf[lambda];
Ax=XX*Pf3*(YP+XX)+Pf[lambda-2]*P2f[lambda+1]+(XX*XX+XX)*Pft;
Bx=XX*Pf3*(YPy+one)+Pft;
}
Hx=Ax*Ax+XX*Ax*Bx+MFX*(Bx*Bx); // substitue y into curve
if (degree(gcd(Hx))==0)
{ // its the other one
tau=(lp-tau)%lp;
cout << "\b\b\b\b";
cout << setw(4) << (p+1-tau)%lp << flush;
}
t[i]=tau;
if ((p+1-tau)%lp==0)
{
cout << " ***" << endl;
if (search) escape=TRUE;
}
else cout << endl;
break;
}
cout << "\b\b\b\b";
}
for (jj=0;jj<low;jj++)
{
Pf[jj].clear();
P2f[jj].clear();
P2f[jj].clear();
}
if (escape) break;
continue;
}
// no eigenvalue found, but some tau values can be eliminated...
if (prime((Big)lp))
{
if (degree(Fl)==0)
{
for (tau=0;tau<=lp/2;tau++)
{
jj=(lp+tau*tau-(4*p)%lp)%lp;
if (jac(jj,lp)!=(-1)) permisso[tau]=FALSE;
}
}
else
{ // Fl==P[lp] so tau=+/- sqrt(p) mod lp
jj=(2*sqrmp(p%lp,lp))%lp;
for (tau=0;tau<=lp/2;tau++) permisso[tau]=FALSE;
if (jj<=lp/2) permisso[jj]=TRUE;
else permisso[lp-jj]=TRUE;
}
}
else
{ // prime power
for (jj=0;jj<start_prime;jj++)
if (lp%l[jj]==0)
{
for (tau=0;tau<=lp/2;tau++)
{
permisso[tau]=FALSE;
if (tau%l[jj]==t[jj]) permisso[tau]=TRUE;
if ((lp-tau)%l[jj]==t[jj]) permisso[tau]=TRUE;
}
break;
}
}
// These next are time-consuming calculations of Y^P, X^PP and Y^PP
cout << "Y^P " << flush;
YP=MFX;
for (jj=0;jj<M-1;jj++)
{
XP2=XK[jj]; // use values stored during generation of X^P
XK[jj].clear();
YP*=YP;
YP+=(XP2*MFX);
}
YPy=XP2*XX;
cout << "\b\b\b\bX^PP" << flush;
// Composition is faster for smaller lp
if (lp<40)
{
TT=compose(YPy,XP);
XPP=XP*TT;
cout << "\b\b\b\bY^PP" << flush;
YPP=compose(YP,XP)+YP*TT;
YPPy=TT*YPy;
}
else
{ // XPP and YPP are calculated together
YPP=YP;
for (jj=0;jj<M;jj++)
{
XP2*=XX;
XP2*=XP2;
YPP*=YPP;
YPP+=(XP2*MFX);
if (jj==M/2) cout << "\b\b\b\bY^PP" << flush;
}
YPPy=XP2*XX;
XPP=YPPy*XX;
}
cout << "\b\b\b\b";
Poly2Mod Pk,P2k,P3k,PkP1,PkM1,PkP2,Pt;
Pk=P[k]; PkP1=P[k+1]; PkM1=P[k-1]; PkP2=P[k+2];
//
// This is Schoof's algorithm
//
// Now looking for the value of tau which satisfies
// (X^PP,Y^PP) + k.(X,Y) = tau.(X^P,Y^P)
//
// Note that (X,Y) are rational polynomial expressions for points on
// an elliptic curve, so "+" means elliptic curve point addition
//
// Note also that Y is of the form A(x)+B(x).y. After the addition
// the X coordinate of the sum will also be of this form.
//
// k.(X,Y) can be found directly from Divisor polynomials
// Schoof Prop (2.2)
//
// Points are converted to projective (X,Y,Z) form
// Observe that (X/Z^2,Y/Z^3,1) is the same
// point in projective co-ordinates as (X,Y,Z)
//
if (k==1)
{ // easy case
XT=XX;
YT=0;
YTy=one;
ZT=one;
}
else
{
P2k=Pk*Pk;
P3k=P2k*Pk;
Pt=PkP1*PkM1;
X2=XX*XX;
XT=X2*(XX*P2k+Pt);
Pt*=Pk;
YT=X2*(X2*P3k+P[k-2]*PkP1*PkP1+(X2+XX)*Pt);
YTy=X2*(XX*P3k+Pt);
ZT=XX*Pk;
}
elliptic_add(XT,XTy,YT,YTy,ZT,XPP,YPP,YPPy);
//
// Test for Schoof's case 1 - LHS (XT,YT,ZT) is point at infinity
//
cout << "NP mod " << lp << " = " << flush;
if (iszero(ZT))
{ // Is it zero point? (XPP,YPP) = - K(X,Y)
t[i]=0;
cout << setw(4) << (p+1)%lp;
if ((p+1)%lp==0)
{
cout << " ***" << endl;
if (search) {escape=TRUE; break;}
}
else cout << endl;
continue;
}
Poly2Mod XP3,XP4,XP6;
Poly2Mod ZT2,ZT3,ZT2XP;
ZT2=ZT*ZT;
ZT3=ZT2*ZT;
ZT2XP=XP*ZT2;
XP2=XP*XP;
XP3=XP*XP2;
XP4=XP2*XP2;
XP6=XP3*XP3;
SX=inverse(XP); // we need 1/XP mod Fl
Pf[0]=0; Pf[1]=1; Pf[2]=XP;
P2f[1]=1; P3f[1]=1;
P2f[2]=Pf[2]*Pf[2];
P3f[2]=P2f[2]*Pf[2];
Pf[3]=XP4+XP3+B;
P2f[3]=Pf[3]*Pf[3];
P3f[3]=P2f[3]*Pf[3];
Pf[4]=XP6+B*XP2;
P2f[4]=Pf[4]*Pf[4];
P3f[4]=P2f[4]*Pf[4];
low=5;
for (tau=1;tau<=lp/2;tau++)
{
int res=0;
Poly2Mod Hx,Ax,Bx,Rx,Tx,Ry,Ty,Pt;
if (!permisso[tau]) continue;
cout << setw(4) << (p+1-tau)%lp << flush;
for (jj=low;jj<=tau+2;jj++)
{ // different for odd and even
if (jj%2==1)
{ // 2 mod-muls/
n=(jj-1)/2;
Pf[jj]=Pf[n+2]*P3f[n]+P3f[n+1]*Pf[n-1];
}
else
{ // 4 mod-muls
n=jj/2;
Pf[jj]=SX*Pf[n]*(Pf[n+2]*P2f[n-1]+Pf[n-2]*P2f[n+1]);
}
P2f[jj]=Pf[jj]*Pf[jj]; // square
if (jj<=1+(1+(lp/2))/2) P3f[jj]=P2f[jj]*Pf[jj]; // cube
}
if (tau+3>low) low=tau+3;
if (tau==1)
{ // easy case
Ax=ZT2XP+XT;
Bx=XTy;
}
else
{
Pt=Pf[tau-1]*Pf[tau+1];
Ax=ZT2*(XP*P2f[tau]+Pt)+P2f[tau]*XT;
Bx=P2f[tau]*XTy;
}
Hx=Ax*Ax+XX*Ax*Bx+MFX*(Bx*Bx);
if (iszero(Hx)) // NOTE: GCD not needed
{ // found it. Now compare Y coordinates to determine sign
if (tau==1)
{
Ax=YT+ZT3*YP;
Bx=YTy+ZT3*YPy;
}
else
{
Tx=XP*P2f[tau]*Pf[tau];
Pt*=Pf[tau];
Ax=YT*Tx+ZT3*(Tx*(XP+YP)+(XP2+XP+YP)*Pt+Pf[tau-2]*P2f[tau+1]);
Bx=YTy*Tx+ZT3*YPy*(Tx+Pt);
}
Hx=Ax*Ax+XX*Ax*Bx+MFX*(Bx*Bx); // substitute into curve
if (!iszero(Hx))
{ // its the other one
tau=(lp-tau)%lp;
cout << "\b\b\b\b";
cout << setw(4) << (p+1-tau)%lp << flush;
}
t[i]=tau;
if ((p+1-tau)%lp==0)
{
cout << " ***" << endl;
if (search) escape=TRUE;
}
else cout << endl;
break;
}
cout << "\b\b\b\b";
}
for (jj=0;jj<low;jj++)
{
Pf[jj].clear();
P2f[jj].clear();
P3f[jj].clear();
}
if (escape) break;
}
Modulus.clear();
for (i=0;i<=L+1;i++)
{
P[i].clear(); // reclaim space
P2[i].clear();
P3[i].clear();
}
if (escape) {bb+=1; continue;}
Big order,ordermod;
ordermod=1; for (i=0;i<nl-start_prime;i++) ordermod*=l[start_prime+i];
order=(p+1-CRT.eval(&t[start_prime]))%ordermod; // get order mod product of primes
nrp=kangaroo(p,order,ordermod,TR,found);
if (!found && search) {bb+=1; continue; }
else break;
}
if (fout)
{
cf=1; // set co-factor=1
if (found)
{ // An "ideal" curve was found
if (TR==1)
{
nrp/=2;
cf=2;
}
else
{
nrp/=4;
cf=4;
}
}
// generate a random point on the curve
// point will be of prime order for "ideal" curve, otherwise any point
forever
{
EC2 P;
do {
x=rand(p);
} while (!GG.set(x,x));
if (!found) break;
P=GG;
P*=(Big)cf;
if (P.iszero()) continue;
P=GG;
P*=nrp;
if (!P.iszero()) continue;
break;
}
GG.get(x,y);
ofile << M << endl;
mip->IOBASE=16;
ofile << aa << endl;
ofile << bb << endl;
ofile << nrp << endl;
ofile << x << endl;
ofile << y << endl;
mip->IOBASE=10;
ofile << a << endl;
ofile << b << endl;
ofile << c << endl;
}
if (p==nrp)
{
cout << "WARNING: Curve is anomalous" << endl;
return 0;
}
// check MOV condition for curves of Cryptographic interest
// if (M<128) return 0;
nrp/=2;
if (nrp%2==0) nrp/=2;
d=1;
for (i=0;i<50;i++)
{
d=modmult(d,p,nrp);
if (d==1)
{
if (i==1 || prime(nrp)) cout << "WARNING: Curve fails MOV condition, k= " << i << endl;
else cout << "WARNING: Curve fails MOV condition, k<= " << i << endl;
return 0;
}
}
return 0;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -