?? cm.cpp
字號:
case TIMES:
n*=oldn;
break;
case '/':
n=oldn/n;
break;
case '%':
n=oldn%n;
}
}
void eval_sum (Big& oldn,Big& n,char op)
{
switch (op)
{
case '+':
n+=oldn;
break;
case '-':
n=oldn-n;
}
}
void eval (Big& t)
{
Big oldn[3];
Big n;
int i;
char oldop[3];
char op;
char minus;
for (i=0;i<3;i++)
{
oldop[i]=0;
}
LOOP:
while (*s==' ')
s++;
if (*s=='-') /* Unary minus */
{
s++;
minus=1;
}
else
minus=0;
while (*s==' ')
s++;
if (*s=='(' || *s=='[' || *s=='{') /* Number is subexpression */
{
s++;
eval(t);
n=t;
}
else /* Number is decimal value */
{
for (i=0;s[i]>='0' && s[i]<='9';i++)
;
if (!i) /* No digits found */
{
cout << "Error - invalid number" << endl;
exit (20);
}
op=s[i];
s[i]=0;
n=atoi(s);
s+=i;
*s=op;
}
if (minus) n=-n;
do
op=*s++;
while (op==' ');
if (op==0 || op==')' || op==']' || op=='}')
{
eval_power (oldn[2],n,oldop[2]);
eval_product (oldn[1],n,oldop[1]);
eval_sum (oldn[0],n,oldop[0]);
t=n;
return;
}
else
{
if (op==RAISE)
{
eval_power (oldn[2],n,oldop[2]);
oldn[2]=n;
oldop[2]=RAISE;
}
else
{
if (op==TIMES || op=='/' || op=='%')
{
eval_power (oldn[2],n,oldop[2]);
oldop[2]=0;
eval_product (oldn[1],n,oldop[1]);
oldn[1]=n;
oldop[1]=op;
}
else
{
if (op=='+' || op=='-')
{
eval_power (oldn[2],n,oldop[2]);
oldop[2]=0;
eval_product (oldn[1],n,oldop[1]);
oldop[1]=0;
eval_sum (oldn[0],n,oldop[0]);
oldn[0]=n;
oldop[0]=op;
}
else /* Error - invalid operator */
{
cout << "Error - invalid operator" << endl;
exit (20);
}
}
}
}
goto LOOP;
}
int main(int argc,char **argv)
{
BOOL good,dir,always;
int i,ip,m,precision;
unsigned long SD,D;
ofstream ofile;
mip=mirsys(128,0);
Big p,k,t;
argv++; argc--;
irand(0L);
if (argc<1)
{
cout << "Incorrect Usage" << endl;
cout << "Program tries to find Elliptic Curve mod a prime P and point of prime order" << endl;
cout << "that is a point (X,Y) on the curve y^2=x^3+Ax+B of order R" << endl;
cout << "where R is large and prime > |P/K|. (K defaults to 256)" << endl;
cout << "cm <prime number P>" << endl;
cout << "OR" << endl;
cout << "cm -f <formula for P>" << endl;
#if defined(unix)
cout << "e.g. cm -f 2^192-2^64-1" << endl;
#else
cout << "e.g. cm -f 2#192-2#64-1" << endl;
#endif
cout << "To suppress commentary, use flag -s. To insist on A= -3, use flag -t" << endl;
cout << "(the commentary will make some sense to readers of IEEE 1363 Annex)" << endl;
cout << "To search downwards for a prime, use flag -d" << endl;
cout << "To output to a file, use flag -o <filename>" << endl;
cout << "To set maximum co-factor size K, use e.g. flag -K8" << endl;
cout << "To set infinite co-factor size K, use flag -K0" << endl;
cout << "(In this case the reported R is the number of points on the curve)" << endl;
cout << "To start searching from a particular D value, use e.g. flag -D10000" << endl;
cout << "To set MIRACL precision to 2^n words, use e.g. flag -Pn (default -P5)" << endl;
cout << "If program fails, try again with n=n+1" << endl;
cout << "To insist on IEEE-1363 invariants, use flag -IEEE" << endl;
#if defined(unix)
cout << "e.g. cm -f 2^224-2^96+1 -K12 -D4000000 -P9 -o common.ecs" << endl;
#else
cout << "e.g. cm -f 2#224-2#96+1 -K12 -D4000000 -P9 -o common.ecs" << endl;
#endif
cout << "Freeware from Shamus Software, Dublin, Ireland" << endl;
cout << "Full C++ source code and MIRACL multiprecision library available" << endl;
cout << "Email to mscott@indigo.ie for details" << endl;
return 0;
}
gprime(1000);
m=5;
ip=0;
k=256;
SD=1;
suppress=FALSE;
fout=FALSE;
dir=FALSE;
three=FALSE;
always=FALSE;
p=0;
while (ip<argc)
{
if (strcmp(argv[ip],"-f")==0)
{
if (p==0)
{
ip++;
s=argv[ip++];
t=0;
eval(t);
p=t;
continue;
}
else
{
cout << "Error in command line" << endl;
return 0;
}
}
if (strcmp(argv[ip],"-s")==0)
{
ip++;
suppress=TRUE;
continue;
}
if (strcmp(argv[ip],"-t")==0)
{
ip++;
three=TRUE;
continue;
}
if (strcmp(argv[ip],"-d")==0)
{
ip++;
dir=TRUE;
continue;
}
if (strncmp(argv[ip],"-K",2)==0)
{
k=argv[ip]+2;
ip++;
continue;
}
if (strncmp(argv[ip],"-D",2)==0)
{
SD=atol(argv[ip]+2);
ip++;
continue;
}
if (strncmp(argv[ip],"-P",2)==0)
{
m=atoi(argv[ip]+2);
ip++;
continue;
}
if (strncmp(argv[ip],"-IEEE",5)==0)
{
always=TRUE;
ip++;
continue;
}
if (strcmp(argv[ip],"-o")==0)
{
ip++;
fout=TRUE;
ofile.open(argv[ip++]);
continue;
}
if (p==0) p=argv[ip++];
else
{
cout << "Error in command line" << endl;
return 0;
}
}
if (!prime(p))
{
int incr=0;
cout << "That number is not prime!" << endl;
if (dir)
{
cout << "Looking for next lower prime" << endl;
p-=1; incr++;
while (!prime(p)) { p-=1; incr++; }
cout << "Prime P = P-" << incr << endl;
}
else
{
cout << "Looking for next higher prime" << endl;
p+=1; incr++;
while (!prime(p)) { p+=1; incr++; }
cout << "Prime P = P+" << incr << endl;
}
cout << "Prime P = " << p << endl;
}
if (p<100)
{
cout << "Prime is too small - use another method!" << endl;
return 0;
}
if (bits(p)>2048)
{
cout << "Prime is too big - sorry" << endl;
return 0;
}
Big W,V,K,r1,r2,ord,rmin;
if (k==0) rmin=1;
else rmin=(p-2*sqrt(p))/k;
if (rmin==0)
{
cout << "Bad k co-factor value" << endl;
return 0;
}
W=sqrt(p)+1;
K=(W*W)/rmin;
if (!suppress) cout << "P mod 8 = " << p%8 << endl;
if (!suppress) cout << "P is " << bits(p) << " bits long" << endl;
if (!suppress) cout << "precomputations..." << endl;
mirexit();
if (m<4) m=4;
precision=(1<<m);
mip=mirsys(precision+2,0); // restart with new precision
setprecision(m);
if (!suppress) cout << "precision in bits = " << precision*MIRACL << endl;
gprime(65536);
mip->RPOINT=ON;
Complex lam;
Float Fi2[7];
Float pi24;
pi24=fpi()/24;
lam=exp(Complex((Float)0,pi24));
Fi2[0]=1;
Fi2[2]=reciprocal(nroot((Float)2,3)); // pow((Float)2,Float(-1,3));
Fi2[3]=reciprocal(sqrt((Float)2)); // pow((Float)2,Float(-1,2));
Fi2[6]=(Float)1/2;
if (!suppress) cout << "finding a curve..." << endl;
for (D=SD;;D++)
{
if (three && D==3) continue;
if (!isaD(D,p%8,K)) continue;
if (jacobi(p-(Big)D,p)==-1) continue;
good=TRUE;
// A.14.2.3
for (i=1;;i++)
{
unsigned long sp=mip->PRIMES[i];
if (D==sp || sp*sp>D) break;
if (D%sp==0 && jacobi(p,(Big)sp)==-1)
{
good=FALSE;
break;
}
}
if (!good) continue;
if (!isacm(p,D,W,V)) continue;
r1=p+1+W;
r2=p+1-W;
if (k==0) ord=r1;
else
{
ord=trial_divide(r1);
if (!prime(ord) && r1%k==0) ord=r1/k;
}
if (ord==1) ord=r1;
if (ord>=rmin && (k==0 || prime(ord)))
get_curve(lam,Fi2,ofile,r1,r2,ord,D,p,W,m,always);
if (k==0) ord=r2;
else
{
ord=trial_divide(r2);
if (!prime(ord) && r2%k==0) ord=r2/k;
}
if (ord==1) ord=r2;
if (ord>=rmin && (k==0 || prime(ord)))
get_curve(lam,Fi2,ofile,r2,r1,ord,D,p,W,m,always);
if (D==1)
{
r1=p+1+V;
r2=p+1-V;
if (k==0) ord=r1;
else
{
ord=trial_divide(r1);
if (!prime(ord) && r1%k==0) ord=r1/k;
}
if (ord==1) ord=r1;
if (ord>=rmin && (k==0 || prime(ord)))
get_curve(lam,Fi2,ofile,r1,r2,ord,D,p,W,m,always);
if (k==0) ord=r2;
else
{
ord=trial_divide(r2);
if (!prime(ord) && r2%k==0) ord=r2/k;
}
if (ord==1) ord=r2;
if (ord>=rmin && (k==0 || prime(ord)))
get_curve(lam,Fi2,ofile,r2,r1,ord,D,p,W,m,always);
}
if (D==3)
{
r1=p+1+(W+3*V)/2;
r2=p+1-(W+3*V)/2;
if (k==0) ord=r1;
else
{
ord=trial_divide(r1);
if (!prime(ord) && r1%k==0) ord=r1/k;
}
if (ord==1) ord=r1;
if (ord>=rmin && (k==0 || prime(ord)))
get_curve(lam,Fi2,ofile,r1,r2,ord,D,p,W,m,always);
if (k==0) ord=r2;
else
{
ord=trial_divide(r2);
if (!prime(ord) && r2%k==0) ord=r2/k;
}
if (ord==1) ord=r2;
if (ord>=rmin && (k==0 || prime(ord)))
get_curve(lam,Fi2,ofile,r2,r1,ord,D,p,W,m,always);
r1=p+1+(W-3*V)/2;
r2=p+1-(W-3*V)/2;
if (k==0) ord=r1;
else
{
ord=trial_divide(r1);
if (!prime(ord) && r1%k==0) ord=r1/k;
}
if (ord==1) ord=r1;
if (ord>=rmin && (k==0 || prime(ord)))
get_curve(lam,Fi2,ofile,r1,r2,ord,D,p,W,m,always);
if (k==0) ord=r2;
else
{
ord=trial_divide(r2);
if (!prime(ord) && r2%k==0) ord=r2/k;
}
if (ord==1) ord=r2;
if (ord>=rmin && (k==0 || prime(ord)))
get_curve(lam,Fi2,ofile,r2,r1,ord,D,p,W,m,always);
}
}
cout << "No satisfactory curve found" << endl;
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -