#include #include "Zm.h" int gcd(int m, int n) { int a = m; int b = n; // (a, b) -> (b, r), where r is a reminder of dividing a by b // Invariant: gcd(a, b) = gcd(b, r) // a = q*b + r, |r| < |b| => // sets of common divizors for pairs (a, b) and (b, r) are equal while (b != 0) { int r = a%b; a = b; b = r; } assert(b == 0); // gcd(a, 0) = a return a; } // Extended Euclid's Algorithm // Input: integer numbers m, n, one of them must be nonzero. // Output: d = gcd(m, n) and integers u, v such that // d = u*m + v*n void extEucl( int m, int n, int& d, int& u, int& v ) { // Invariant: // gcd(a, b) = gcd(m, n), // a = u1*m + v1*n, // b = u2*m + v2*n int a = m, b = n; int u1 = 1, v1 = 0; int u2 = 0, v2 = 1; // assert(gcd(a, b) = gcd(m, n)); assert(a == u1*m + v1*n && b == u2*m + v2*n); while (b != 0) { assert(a == u1*m + v1*n && b == u2*m + v2*n); int q = a/b; int r = a%b; assert(a == q*b + r); a = b; b = r; // (a, b) <-- (b, r) // u1' = u2; v1' = v2 // r = a - q*b = (u1*m + v1*n) - q*(u2*m + v2*n) = // = (u1 - q*u2)*m + (v1 - q*v2)*n // u2' = u1 - q*u2; v2' = v1 - q*v2; int tmp = u1; u1 = u2; u2 = tmp - q*u2; tmp = v1; v1 = v2; v2 = tmp - q*v2; } assert(b == 0); assert(a == u1*m + v1*n && b == u2*m + v2*n); if (a >= 0) { d = a; u = u1; v = v1; } else { d = (-a); u = (-u1); v = (-v1); } } int powermod(int a, int n, int m) { assert(n >= 0 && m != 0); // b^k * p == a^n (mod m) // End of loop condition: k == 0 int b = a; int k = n; int p = 1; while (k > 0) { if (k%2 == 0) { k /= 2; b = (b*b)%m; } else { k -= 1; p = (p*b)%m; } } return p; } // Using exceptions for error processing // throw MyException("Reason of error"); // // try { // // Dangerous code // . . . // } catch (MyException& e) { // // Processing exception // cerr << "Exception: " << e.what() << endl; // } catch (SomeOtherException& e) { // // Processing another exception // . . . // } int Zm::m = 7; // Definition of static variable of class Zm