Lab 2 Spring 2015

1. Implement modexp algorithm in C++. Do exercise 1.25
2. Compute 2 ^{2 2015} (modd 3)
3. (optional) Do exercise 1.26
4. Using pencil and paper find x,y and d such that 17*x+11*y=1 using Extended Euclidean Algorithm (Here a is 17 and b is 11 ) use 1 = 1-0
5. Implement primality (random) testing algorithm in C++. Generate all prime numbers between 3 and 10000.
6. (Please do not believe all the code you found in the Web) Please see a C langauge implementation of Karp-Rabin String matching here. This code has many problems. In particular do you see a problem with this code segment.

    /* Main comparison loop */
       for (i = 0; i < num_iterations; i) {
           if (pattern_hash == text_hash && 
               !strncmp(pattern, &(text[i]), pattern_len)) return i;
   }
   

   Your instructor created working version of this C code here. Your job is to get a C++ version running. Test with three text strings and three pattern strings.