/*
  Author:  Pate Williams (c) 1997

  Exercise III.1.4
  "In a long string of ciphertext which was encrypted
  by means of an affine map on single-letter message
  units in the 26-letter alphabet, you observe that
  the most frequently occurring letters are "Y" amd
  "V", in that order. Assuming that those ciphertext
  message units are the encryption of "E" and "T",
  respectively, read the message "QAOOYQQEVHEQV"."
  -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 62.
*/

#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] = "QAOOYQQEVHEQV", plaintext[16];
  long A[2][2], B[2], C[2][2], a, b, d, i, p;

  A[0][0] = 'E' - 'A', A[0][1] = 1;
  A[1][0] = 'T' - 'A', A[1][1] = 1;
  B[0] = 'Y' - 'A', B[1] = 'V' - 'A';
  d = (A[0][0] * A[1][1] - A[0][1] * A[1][0]) % 26;
  if (d < 0) d += 26;
  d = Extended_Euclidean(d, 26);
  if (d == 0)
    printf("determinant is zero, solution does not exist\n");
  else {
    C[0][0] = (d * A[1][1]) % 26;
    C[1][1] = (d * A[0][0]) % 26;
    C[0][1] = - (d * A[0][1]) % 26;
    C[1][0] = - (d * A[1][0]) % 26;
    a = (C[0][0] * B[0] + C[0][1] * B[1]) % 26;
    b = (C[1][0] * B[0] + C[1][1] * B[1]) % 26;
    if (a < 0) a += 26;
    if (b < 0) b += 26;
    printf("a = %ld\n", a);
    printf("b = %ld\n", b);
    a = Extended_Euclidean(a, 26);
    for (i = 0; i < strlen(ciphertext); i++) {
      p = (a * (ciphertext[i] - 'A' - b)) % 26;
      if (p < 0) p += 26;
      plaintext[i] = (char) (p + 'A');
    }
    plaintext[strlen(ciphertext)] = '\0';
    printf("%s\n", ciphertext);
    printf("%s\n", plaintext);
  }
  return 0;
}