readme.c

calc大数库

		printf("using the LLL based method, followed by Gauss lattice reduction.\n");
		printf("The output is sent to a file improvep.out.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, mlll_str) == 0)
	{
		printf("          **************************\n");
		printf("mlll: usage: mlll()\n");
		printf("The MLLL algorithm of M. Pohst is applied to an integer matrix\n");
		printf("whose first row is non-zero.\n");
		printf("The reduced matrix is sent to mlllbas.out\n");
		printf("the transforming matrix is sent to mllltran.out.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, smith_str) == 0)
	{
		printf("          **************************\n");
		printf("smith: usage: smith()\n");
		printf("The Smith normal form SNF(A) of an integer matrix A is found\n");
		printf("using a pivoting strategy due to G. Havas.\n");
		printf("A cutoff value is requested. When coefficients grow\n");
		printf("above this value in size, the MLLL algorithm is used to\n");
		printf("reduce coefficient explosion. Unimodular matrices P and Q\n");
		printf("are found such that PAQ=SNF(A).\n");
		printf("The invariant factors d[1],...,d[r],\n");
		printf("together with P and Q, are sent to files\n");
		printf("smith.out, smithp.out, smithq.out, respectively, if desired.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, rsae_str) == 0)
	{
		printf("          **************************\n");
		printf("rsae: usage: e=rsae(p,q)\n");
		printf("Here p and q are distinct odd primes\n");
		printf("and e is the least integer such that\n");
		printf("gcd(e,(p-1)(q-1))=1 and 32^e>pq.\n");
		printf("e is for use as an RSA encryption modulus.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, encode_str) == 0)
	{
		printf("          **************************\n");
		printf("encode: usage: encode(e,n)\n");
		printf("n=p*q, a product of primes each greater than 355142.\n");
		printf("(p*q>126126126126.)\n");
		printf("e is the RSA encryption modulus, found using rsae() above.\n");
		printf("A string of non-control characters when entered from the keyboard\n");
		printf("or from a file consisting of lines each containing less than 500 characters.\n");
		printf("These characters have ascii values in the range 32-126.\n");
		printf("The message string is encoded using the RSA algorithm:\n");
		printf("every 4 characters are converted to ascii, joined as strings\n");
		printf("and the resulting large number m is encoded as n=m^e(mod p*q).\n");
		printf("The encoded numbers are sent to encoded.out, which is terminated by an entry -1.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, decode_str) == 0)
	{
		printf("          **************************\n");
		printf("decode: usage: decode(e,p,q)\n");
		printf("This calculates the decryption modulus d,\n");
		printf("then decodes each number n in encoded.out.\n");
		printf("m=n^d(mod pq). The ascii characters are split off\n");
		printf("and the original string of message characters is recreated.\n");
		printf("The decoded message is sent to decoded.out, as well as to the screen.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, addcubicr_str) == 0)
	{
		printf("          **************************\n");
		printf("addcubicr: usage: addcubicr()\n");
		printf("The sum of two points on the elliptic curve y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6 over Q\n");
		printf("is calculated. The discriminant is also calculated.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, powercubicr_str) == 0)
	{
		printf("          **************************\n");
		printf("powercubicr: usage: powercubicr()\n");
		printf("The point nP, where P is on the elliptic curve over Q:\n");
		printf("y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6, is calculated.\n");
		printf("The discriminant is also calculated.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, ordercubicr_str) == 0)
	{
		printf("          **************************\n");
		printf("ordercubicr: usage: ordercubicr()\n");
		printf("Finds the order of P on the elliptic curve over Q:\n");
		printf("y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6.\n");
		printf("The discriminant is also calculated.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, addcubicm_str) == 0)
	{
		printf("          **************************\n");
		printf("addcubicm: usage: addcubicm()\n");
		printf("The sum of two points on the elliptic curve\n");
		printf("y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6 over Z_p\n");
		printf("is calculated. The discriminant is also calculated.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, powercubicm_str) == 0)
	{
		printf("          **************************\n");
		printf("powercubicm: usage: powercubicm()\n");
		printf("The point nP, where P is on the elliptic curve over Z_p:\n");
		printf("y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6, is calculated.\n");
		printf("The discriminant is also calculated.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, ordercubicm_str) == 0)
	{
		printf("          **************************\n");
		printf("ordercubicm: usage: ordercubicm()\n");
		printf("Finds the order of P on the elliptic curve over Z_p:\n");
		printf("y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6.\n");
		printf("The discriminant is also calculated.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, convergents_str) == 0)
	{
		printf("          **************************\n");
		printf("convergents: usage: convergents(a[],&p[],&q[])\n");
		printf("The convergents p[0]/q[0],...,p[n]/q[n] of the continued fraction\n");
		printf("[a[0];a[1],...,a[n]] are returned as arrays p[] and q[]\n");
		printf("and are sent to a file convergents.out.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, lagrange_str) == 0)
	{
	  printf("          **************************\n");
	  printf("Usage: lagrange(\"poly\",&a[],m)\n");
	  printf("""poly"" is a polynomial\n");
	  printf("with integer coefficients, having no rational roots\n");
	  printf("and having exactly one real positive root x > 1.\n");
	  printf("The method of Lagrange (1797) is used to find the\n");
	  printf("the first m+1 partial quotients a[0],...,a[m] of x.\n");
	  printf("(See Knuth, Art of computer programming, volume2, problem 13, 4.5.3.\n");
	  printf("Also S. Lang and H. Trotter, 'Continued fractions for some algebraic numbers',\n");
	  printf("J. fur Math. 255 (1972) 112-134; Addendum 267 (1974) ibid. 219-220.\n");
	  printf("Also D.G. Cantor, P.H. Galyean, H.G. Zimmer,\n");
	  printf("'A continued fraction algorithm for real algebraic numbers',\n");
	  printf("Math. Comp. 26, July 1972, 785-791.\n");
	  printf("          **************************\n");
	  GetReturn();
	}
	else if (strcmp(name, perfectpower_str) == 0)
	{
		printf("          **************************\n");
		printf("perfectpower: usage: z=perfectpower(n)\n");
		printf("Here n > 1.  z = x if n = x^k, for some x, k > 1,\n");
		printf("NULL otherwise.\n");
		printf("See E. Bach and J. Sorenson,\n");
		printf("'Sieve algorithms for perfect power testing'\n");
		printf("Algorithmica 9 (1993) 313-328.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, leastqnr_str) == 0)
	{
		printf("          **************************\n");
		printf("leastqnr: usage: z=leastqnr(p):\n");
		printf("Returns n_p, the least quadratic non-residue (mod p),\n");
		printf("if n_p< 65536, otherwise returns 0.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, examples_str) == 0)
	{
		printf("          **************************\n");
		printf("SOME EXAMPLES\n");
		printf("To find z=gcd(4,6), type z=gcd(4,6)\n");
		printf("Then z is stored and its value is printed on typing z,\n");
		printf("as follows:\n");
		printf("z\n");
		printf("2\n");
		GetReturn();

		printf("To find z=gcd(4,6) together with integers u,v\n");
		printf("satisfying z=4u+6v, type z=gcdv(4,6,&u,&v)\n");
		printf("The values of u,v are stored and their values printed,\n");
		printf("by typing u,v, as in \n");
		printf("u\n");
		printf("-1\n");
		printf("v\n");
		printf("1\n");
		GetReturn();

		printf("To find z=gcd(4,6,9), type\n");
		printf("x[0]=4;x[1]=6;x[2]=9\n");
		printf("z=gcda(x[])\n");
		GetReturn();

		printf("To find z=gcd(4,6,9), together with integers\n");
		printf("b[0],b[1],b[2] satisfying z=4*b[0]+6*b[1]+9*b[2],\n");
		printf("type\n");
		printf("x[0]=4;x[1]=6;x[2]=9\n");
		printf("z=gcdav(x[],&b[])\n");
		printf("The values of b[0],b[1],b[2] are stored\n");
		printf("and their values printed by typing printa(b,2) \n");
		GetReturn();
		printf("\nCalc can also parse polynomials.\n");
		printf("Typing\n> (X+2)^2\ngives\nX^2 + 4X + 4\n");
		printf("If you assign the polynomial to a variable with\n");
		printf("> z=X^3+3X^2+2X+1\nyou can evaluate the polynomial\n");
		printf("at various integer points by typing (for example)\n");
		printf("> z(2)\nwhich gives\n25\n");
		printf("One can also enter arrays in the following manner\n");
		printf("> a[] = {1, 2, 3, 4, 5, 6}\n");
		printf("Note: Any previous definition of the array will be");
		printf("erased\n");
		printf("Or one can enter arrays like so:\n");
		printf("> a[1]=2\n> a[3]=2\n> a[7]=1000\n");
		printf("One can view the contents of the array by typing\n");
		printf("> a[]\nwhich gives\n[0]:0\n[1]:2\n[2]:0\n[3]:2\n");
		printf("[4]:0\n[5]:0\n[6]:0\n[7]:1000\n");
		printf("Note that the undefined subscripts have been\n");
		printf("initialised to zero.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, content_str) == 0) {
	  printf("\n***************************************\n");
	  printf("Usage: content(f(X))\n");
	  printf("Returns the content of a polynomial f(X).\n");
	  printf("eg. content(3X^2+6) returns 3\n");
	  printf("*****************************************\n");
	  GetReturn();
	}
	else if (strcmp(name, primitive_str) == 0) {
	  printf("\n***************************************\n");
	  printf("Usage: primitive(f(X))\n");
	  printf("Returns the primitive part of a polynomial f(X).\n");
	  printf("eg. primitive(3X^2+6) returns X^2+2\n");
	  printf("*****************************************\n");
	  GetReturn();
	}
	else if (strcmp(name, sturm_str) == 0) {
	  printf("\n***************************************\n");
	  printf("Usage: sturm(f(X))\n");
	  printf("Prints rational open intervals that are guaranteed to\n");
	  printf("contain only one real root of f(X).\n");
	  printf("It is not guaranteed to produce correct results if the\n");
	  printf("polynomial entered has rational roots.  The output is \n");
	  printf("sent to the file sturm.out and to the screen.\n");
	  printf("***************************************\n");
	  GetReturn();
	}
	else if(strcmp(name, rootexp_str) == 0) {
	  printf("\n***************************************\n");
	  printf("Usage: rootexp(f(X), m)\n");
	  printf("Finds m partial quotients of the continued fraction \n");
	  printf("expansion of all real roots of a squarefree polynomial f(X)\n");
	  printf("(having no rational roots)\n");
	  printf("using Lagrange's method and methods presented in a\n");
	  printf("paper by Cantor, Galyean and Zimmer called A Continued \n");
	  printf("Fraction Algorithm for Real Algebraic Numbers.  The \n");
	  printf("output is sent to a file rootexp.out and to the screen.\n");
	  printf("***************************************\n");
	  GetReturn();
	}
	else if(strcmp(name, log2_str) == 0) {
	  printf("\n***************************************\n");
	  printf("Usage: log2(a,b,d,r,s,e)\n");
	  printf("This is a discrete version of Shank's log_b(a) algorithm.\n");
	  printf("d > 1, 1< =r < s are integers. The larger is s-r, the more\n");
	  printf("accurate the output. eg s=2r, but this is slow when r=500.\n");
          printf("But s=r+10 should be adequate.\n");
	  printf("A certain number (usually at least r if d=10) of \n");
	  printf("number of partial quotients are printed.\n");
	  printf("The correctness is not 100 percent guaranteed.\n");
	  printf("e=0 prints only the partial quotients,\n");
	  printf("while e nonzero prints convergents and decimal expansion.\n");
	  printf("Output is sent to log2.out.\n");
	  printf("***************************************\n");
	  GetReturn();
	}
	else if(strcmp(name, log_str) == 0) {
	  printf("\n***************************************\n");
	  printf("Usage: log(a,b,d,r,&a[],&l)\n");
	  printf("This is a discrete version of Shank's log_b(a) algorithm.\n");
	  printf("a>b>1, d>1, r>0 are integers. \n");
	  printf("l  is the number of partial quotients a[s].\n");
	  printf("The correctness is not 100 percent guaranteed.\n");
	  printf("Output is sent to log.out.\n");
	  printf("See http://www.numbertheory.org/pdfs/log.pdf.\n");
	  printf("***************************************\n");
	  GetReturn();
	}
	else if(strcmp(name, testlog_str) == 0) {
	  printf("\n***************************************\n");
	  printf("Usage: testlog(a,b,d,m,n)\n");
	  printf("This runs the modified Shank's log_b(a) algorithm\n");
	  printf("for r=m,...,n. \n");
	  printf("Here a>b>1, d>1 are integers. \n");
	  printf("Output is sent to testlog.out.\n");
	  printf("With d=10 and m=n, we expect to get at least m partial quotients\n");
	  printf("The idea is to run it for a range (m-t,m+t) with d=10\n");
	  printf("to get a good idea of the correct partial quotients.\n");
	  printf("See http://www.numbertheory.org/pdfs/log.pdf.\n");
	  printf("***************************************\n");
	  GetReturn();
	}
	else if(strcmp(name, log1_str) == 0) {
	  printf("\n***************************************\n");
	  printf("Usage: log1(a,b,d,r,e), where d>=2, r>=1.\n");
	  printf("d=2 is fast, but d = say 10 gives more output.\n");
	  printf("This is Algorithm 1 of http://www.maths.uq.edu.au/~krm/log.pdf.\n");
	  printf("A certain number (approximately r) of \n");
	  printf("number of partial quotients are printed.\n");
	  printf("The correctness is not 100 percent guaranteed.\n");
	  printf("So far a counter-example has not emerged.\n");
	  printf("e=0 prints only the partial quotients,\n");
	  printf("while e nonzero prints convergents, the integers A[i] and  the decimal expansion of log_b(a).\n");
	  printf("Output is sent to log1.out.\n");