/*
  Author:  Pate Williams (c) 1997

  Exercise III.1.10
  "You intercept the ciphertext message
  "PWULPZTQAWHF", which you know was encrypted
  using an affine transformation in the
  26-letter alphabet, where, as in the text,
  a digraph whose two letters have numerical
  equivalentsx and y correspond to the integer
  26x + y. An extensive statistical analysis
  of earlier ciphertexts which had been coded
  by the same enciphering map shows that the
  most frequently occurring digraphs in all
  the ciphertext are "IX" and "TQ", in that
  order. It is known that the most common
  digraphs in the English language are "TH"
  and "HE", in that order."
  (a) Find the deciphering key, and read the
  message.
  (b) You decide to have the intended recipient
  of the message incapacitated, but you don't
  want the sender to know anything is amiss.
  So you want to impersonate the sender's
  accomplice and reply "GOODWORK". Find the
  enciphering key, and determine the appropriate
  ciphertext." -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 63.
*/

#include <stdio.h>
#include <string.h>

long Extended_Euclidean(long b, long n)
{
  long b0 = b, n0 = n, t = 1, t0 = 0, temp, q, r;

  q = n0 / b0;
  r = n0 - q * b0;
  while (r > 0) {
    temp = t0 - q * t;
    if (temp >= 0) temp = temp % n;
    else temp = n - (- temp % n);
    t0 = t;
    t = temp;
    n0 = b0;
    b0 = r;
    q = n0 / b0;
    r = n0 - q * b0;
  }
  if (b0 != 1) return 0;
  else return t % n;
}

int main(void)
{
  char ciphertext[16] = "PWULPZTQAWHF", plaintext[16];
  char plaintext1[16] = "GOODWORK", ciphertext1[16];
  long a, ap, b, bp, c, d, i, p, n = 26, N = n * n;
  long A[2][2], B[2], C[2][2];

  A[0][0] = ('T' - 'A') * n + ('H' - 'A');
  A[0][1] = 1;
  A[1][0] = ('H' - 'A') * n + ('E' - 'A');
  A[1][1] = 1;
  B[0] = ('I' - 'A') * n + 'X' - 'A';
  B[1] = ('T' - 'A') * n + 'Q' - 'A';
  d = (A[0][0] * A[1][1] - A[0][1] * A[1][0]) % N;
  if (d < 0) d += N;
  d = Extended_Euclidean(d, N);
  if (d == 0)
    printf("determinant is zero, solution does not exist\n");
  else {
    C[0][0] = (d * A[1][1]) % N;
    C[1][1] = (d * A[0][0]) % N;
    C[0][1] = - (d * A[0][1]) % N;
    C[1][0] = - (d * A[1][0]) % N;
    a = (C[0][0] * B[0] + C[0][1] * B[1]) % N;
    b = (C[1][0] * B[0] + C[1][1] * B[1]) % N;
    if (a < 0) a += N;
    if (b < 0) b += N;
    ap = Extended_Euclidean(a, N);
    bp = (- ap * b) % N;
    if (bp < 0) bp += N;
    printf("a  = %ld\n", a);
    printf("b  = %ld\n", b);
    printf("a' = %ld\n", ap);
    printf("b' = %ld\n", bp);
    for (i = 0; i < strlen(ciphertext); i += 2) {
      c = (ciphertext[i] - 'A') * n + ciphertext[i + 1] - 'A';
      p = (ap * c + bp) % N;
      if (p < 0) p += N;
      plaintext[i] = (char) (p / n + 'A');
      plaintext[i + 1] = (char) (p % n + 'A');
    }
    plaintext[strlen(ciphertext)] = '\0';
    printf("%s\n", ciphertext);
    printf("%s\n", plaintext);
    for (i = 0; i < strlen(plaintext1); i += 2) {
      p = (plaintext1[i] - 'A') * n + plaintext1[i + 1] - 'A';
      c = (a * p + b) % N;
      if (c < 0) c += N;
      ciphertext1[i] = (char) (c / n + 'A');
      ciphertext1[i + 1] = (char) (c % n + 'A');
    }
  }
  printf("%s\n", plaintext1);
  printf("%s\n", ciphertext1);
  return 0;
}