Script started on Mon Apr 14 22:06:27 2003 [root@Fizzgig /root]# cd C [root@Fizzgig C]# cat makefile modq: modq.o main.o g++ -g modq.o main.o -o modq modq.o: modq.cpp modq.hpp g++ -c modq.cpp main.o: main.cpp modq.hpp g++ -c main.cpp [root@Fizzgig C]# cat modq.hpp #include class modq { private: unsigned int value; //value of the modq object public: modq(unsigned int n = 0); int operator==(modq a) {return value==a.value;}; modq operator+=(modq a); modq operator-=(modq a); modq operator*=(modq a); modq operator/=(modq a); void print(); }; /* constants initialzed in modq.hpp */ extern const unsigned int P; //prime number used by mod extern const modq NAN; //Not A Number object modq sqrt(modq a); modq operator^(modq a, int n); modq inverse(modq a); modq operator+(modq a, modq b); modq operator-(modq a, modq b); modq operator*(modq a, modq b); modq operator/(modq a, modq b); [root@Fizzgig C]# cat modq.cpp /* modq.cpp */ /* Implementation of the class modq and associated functions. */ /* To be used for modular arithmatic: x mod P. P is constant. */ /* Author: Zach Tomaszewski */ /* Date: 14 Apr 2003 */ #include "modq.hpp" const unsigned int P = 65479; const modq NAN = modq(0xffffff); /*Constructor */ modq::modq(unsigned int n = 0){ if (n < 0 || n >= P) { value = 0xffffff; }else { value = n; } } //Operator methods /* Adds a to the value of (*this) (which is the lvalue of the operator) and mod P's the result. Returns (*this). (Note: this is the typical behavior for each of the "op=" methods.) */ modq modq::operator+=(modq a){ if (*this == NAN || a == NAN) { *this = NAN; }else { value = (value + a.value) % P; } return *this; } /* Subtraction. (See += docs for more.) */ modq modq::operator-=(modq a){ if (*this == NAN || a == NAN) { *this = NAN; }else { if (a.value > value) { //avoids negative results value = (value + P) - a.value; }else{ value = (value - a.value); } } return *this; } /* Multiplication. (See += docs for more.) */ modq modq::operator*=(modq a){ if (*this == NAN || a == NAN) { *this = NAN; }else { value = (value * a.value) % P; } return *this; } /* Division. (See += docs for more.) */ modq modq::operator/=(modq a){ if (*this == NAN || a == NAN) { *this = NAN; }else { value = (value * inverse(a).value) % P; } return *this; } /* Prints the value of the object to the screen. Output is formated to 6 spaces wide, including an initial padding space */ void modq::print() { if (*this == NAN){ printf(" *NAN*"); }else { printf(" %5d", value); } } //Operator functions /* Returns a new modq with the value of a + b. */ modq operator+(modq a, modq b){ if (a == NAN || b == NAN) { return NAN; }else { return a += b; //safe to work on a since function is pass by value } } /* Returns a new modq with the value of a - b. */ modq operator-(modq a, modq b){ if (a == NAN || b == NAN) { return NAN; }else { return a -= b; } } /* Returns a new modq with the value of a * b. */ modq operator*(modq a, modq b){ if (a == NAN || b == NAN) { return NAN; }else { return a *= b; } } /* Returns a new modq with the value of a / b. */ modq operator/(modq a, modq b){ if (a == NAN || b == NAN) { return NAN; }else { return a /= b; } } /* Returns the modq square root of a, or else NAN if a has no square root. */ modq sqrt(modq a){ if (a == NAN) { return NAN; }else{ modq t = a^((P+1)/4); return (t * t == a) ? t : NAN; } } /* Returns the value of a raised to the power of n. If n is negative, as in a^-n, returns the inverse of (a^n). */ modq operator^(modq a, int n){ if (a == NAN) { return NAN; }else if (n == 0){ return modq(1); //a^0 is 1 }else if (n==1) { //a^1 is a return a; }else if (n > 1){ modq tempA = a; for (int i=2; i <= n; i++){ a *= tempA; } return a; }else { //n < 0 return inverse(a ^ -n); } } /* Returns the inverse mod P value of the given object. */ modq inverse(modq a){ if (a == NAN) { return NAN; }else { return a^(P-2); //rule to derive inverse } } [root@Fizzgig C]# make g++ -c modq.cpp g++ -c main.cpp g++ -g modq.o main.o -o modq [root@Fizzgig C]# modq 0 5 2000 20000 A 50000 0 0 B a!=b a==a 52000 4521 1995 63484 C 10000 4712 15625 1 D 52000 4521 1995 63484 E 10000 4712 62704 1 F 400 26192 400 26192 G 1 *NAN* 44022 54892 H *NAN* *NAN* *NAN* *NAN* I *NAN* *NAN* *NAN* *NAN* J 0 1 K 1 [root@Fizzgig C]# cat modqmath.cpp /* modqmath.cpp */ /* A couple functions to be used with modular arithmetic. */ /* Author: Zach Tomaszewski */ /* Date: 14 Apr 2003 */ #include #include "modq.hpp" int quadratic(modq a, modq b, modq c, modq* x1, modq* x2); modq solveBinomial(modq a, modq b, modq c, modq x); modq* solveLinear(modq a, modq b, modq c); int main(){ //quadratic test modq* x1; modq* x2; modq a(1); modq b(33); modq c(5003); printf("\nQuadratic test: x^2 + 33x + 5003 = 0\n"); printf("Solutions: %d\n", quadratic(a, b, c, x1, x2)); printf("x1: "); (*x1).print(); printf("\nx2: "); (*x2).print(); printf("\n"); printf("Check solutions by inserting into original equation:\n"); printf("(x1)^2 + 33(x1) + 5003 =? "); solveBinomial(a, b, c, *x1).print(); printf("\n(x2)^2 + 33(x2) + 5003 =? "); solveBinomial(a, b, c, *x2).print(); printf("\n"); //linear test 1 a = modq(17) ; b = modq(500); c = modq(1200); modq *x, *y; printf("\nLinear test: 17x + 500y = 1200\n"); printf("X and Y intercept solutions: "); modq* sol = solveLinear(a, b, c); printf("("); sol[0].print(); printf(","); sol[1].print(); printf("); ("); sol[2].print(); printf(","); sol[3].print(); printf(").\n"); printf("Check: 17("); sol[0].print(); printf(") + 500(0) ="); (a * sol[0]).print(); printf("\nCheck2: 17(0) + 500("); sol[3].print(); printf(") ="); (b * sol[3]).print(); printf("\n"); //linear test 1 a = modq(300) ; b = modq(1); c = modq(700); printf("\nLinear test: 300x + y = 700\n"); printf("X and Y intercept solutions: "); sol = solveLinear(a, b, c); printf("("); sol[0].print(); printf(","); sol[1].print(); printf("); ("); sol[2].print(); printf(","); sol[3].print(); printf(").\n"); printf("Check: 300("); sol[0].print(); printf(") + (0) ="); (a * sol[0]).print(); printf("\nCheck2: 300(0) + ("); sol[3].print(); printf(") ="); (b * sol[3]).print(); printf("\n\n"); return 0; } /* Given an equation in the form: ax^2 + bx + c, returns the two solutions for x given by: x = (-b + sqrt(b^2 - 4ac))/2a and: x = (-b - sqrt(b^2 - 4ac))/2a Places the solutions in x1 and x2; otherwise, sets them to NAN. Uses modular arithmetic. Returns the number of unique, rational solutions found: 0, 1, or 2. */ int quadratic(modq a, modq b, modq c, modq* x1, modq* x2){ *x1 = *x2 = NAN; modq root = (b^2) - (4*a*c); root = sqrt(root); if (root == NAN) { //solutions will be imaginary, not rational return 0; } *x1 = ((0 - b) + root)/(2*a); *x2 = ((0 - b) - root)/(2*a); return (*x1 == *x2) ? 1 : 2; } /* Given an equation in the form: ax^2 + bx + c, Returns the value of the expression. */ modq solveBinomial(modq a, modq b, modq c, modq x){ modq sol; sol = a * (x^2); sol += b * x; sol += c; return sol; } /* Given an equation in the form: ax + by = c Solves for x and y intercepts. Returns the solutions in array sol as: [x1, y1, x2, y2]. */ modq* solveLinear(modq a, modq b, modq c){ modq* sol = new modq[4]; //x = (c - by)/a modq x = (c/a); //if y is 0, x is c/a; sol[0] = x; sol[1] = modq(0); modq y = (c/b); //if x is 0, y is c/b sol[2] = modq(0); sol[3] = y; return sol; } [root@Fizzgig C]# g++ modq.cpp modqmath.cpp -o modqmath [root@Fizzgig C]# modqmath Quadratic test: x^2 + 33x + 5003 = 0 Solutions: 2 x1: 18072 x2: 47374 Check solutions by inserting into original equation: (x1)^2 + 33(x1) + 5003 =? 0 (x2)^2 + 33(x2) + 5003 =? 0 Linear test: 17x + 500y = 1200 X and Y intercept solutions: ( 7774, 0); ( 0, 26194). Check: 17( 7774) + 500(0) = 1200 Check2: 17(0) + 500( 26194) = 1200 Linear test: 300x + y = 700 X and Y intercept solutions: ( 43655, 0); ( 0, 700). Check: 300( 43655) + (0) = 700 Check2: 300(0) + ( 700) = 700 [root@Fizzgig C]# exit Script done on Mon Apr 14 22:08:48 2003