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 <stdio.h>

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 <stdio.h>
#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