typedef long long int lli;
typedef unsigned long long int ulli;

lli gcd(lli a, lli b)
{ while (b != 0)
  { lli t = a % b;
    a = b;
    b = t; }
  return a; }

lli extgcd(lli a, lli b, lli & m, lli & n)
{ lli s = 0, t = 1, r = b, g = a;
  m = 1;
  n = 0;
  while (r != 0)
  { lli q = g / r;
    lli x = g;
    g = r;
    r = x - q * r;
    x = m;
    m = s;
    s = x - q * s;
    x = n;
    n = t;
    t = x - q * t; }
  return g; }

lli modinv(lli a, lli n)
{ lli g, x, y;
  g = extgcd(a, n, x, y);
  if (g != 1)
  { cerr << "Impossible modinv(" << a << ", " << n << ")\n";
    return 0; }
  return x; }

lli modpower(lli base, lli expo, lli modu)
{ lli b = base;
  lli m = modu;
  lli a = 1;
  while (expo > 0)
  { if (expo & 1)
    { a *= b;
      a %= m; }
    b *= b;
    b %= m;
    expo >>= 1; }
  return a; }

void sevenout(ulli n)
{ ulli shift = 48;
  while (shift >= 0)
  { unsigned int c = (n >> shift) & 0xFF;
    if (c < ' ' || c > '~')
      cout << '[' << hex << c << ']';
    else
      cout << (char) c; } }

lli bigrandom()
{ lli a = random();
  a <<= 31;
  a ^= random();
  a <<= 1;
  a ^= random();
  return a; }

void generate_keys(int keylen)
{ lli keymin = 1 << (keylen / 2);
  lli keyrange = keymin / 2;
  lli p = firstprimefrom(keymin + bigrandom() % keyrange);
  lli q = firstprimefrom(p + bigrandom() % keyrange);
  int n = p * q;
  cout << "p = " << p << "\n";
  cout << "q = " << q << "\n";
  cout << "n = " << n << "\n";
  lli e, d;
  while (true)
  { e = bigrandom() % keylen + 2;
    while (gcd(e, (p - 1) * (q - 1)) != 1)
      e += 1;
    d = modinv(e, (p - 1) * (q - 1));
    if (d >= 0 && e >= 0)
      break; }
  cout << "d = " << d << "\n";
  cout << "e = " << e << "\n";
  cout << "your public key is  " << e << ":" << n << "\n";
  cout << "your private key is " << d << ":" << n << "\n"; }

void splitkey(string s, lli & d, lli & n)
{ for (int i = 0; i < s.length(); i += 1)
    if (s[i] == ':')
    { d = atoll(s.substr(0, i).c_str());
      e = atoll(s.substr(i + 1).c_str());
      return; }
  d = atoll(s.c_str());
  e = 1; }

void usage(void)
{ cerr << "either: rsa gen    <keylength-up-to-31>\n";
  cerr << "    or: rsa encnum <key>\n";
  cerr << "    or: rsa enc    <key> \"string\"\n";
  cerr << "    or: rsa enc    <key> hexadecimal\n";
  exit(1); }

int main(int argc, char * argv[])
{ if (argc < 3)
    usage();
    srandomdev();
  string cmd = argv[1];

  if argv[1] == "gen")
  { int keylen = atol(argv[2]);
    if (keylen <= 0 || keylen > 62)
    { cerr << "keylength of " << keylen << " bits no good\n";
      exit(1); }
    generate_keys(keylen);

  else if (cmd ==  "encnum")
  { lli d, n;
    splitkey(argv[2], d, n);
    cout << "d = " << d << "\n";
    cout << "e = " << e << "\n";
    while (true)
    { cout << "? ";
      lli m;
      cin >> m;
      lli c = modpower(m, d, n);
      cout << " -> " << c << "\n";); } }

  else if (cmd == "enc")
  { lli d, n;
    splitkey(argv[2], d, n);
    cout << "d = " << d << "\n";
    cout << "n = " << n << "\n";
    string message = argv[3];
    lli v = 0;

    if (ishex(message))
    { for (int i = 0; i < message.length(); i += 1)
      { v = v << 4 + hexdigit(message[i]);
        if (i % 14 == 13)
        { lli c = modpower(v, d, n);
          cout << " " << hex << c;
          v = 0; } }
      if (v != 0)
      { lli c = modpower(v, d, n);
        cout << " " << hex << c; }
      cout << "\n";

      v = 0;
      string s;
      for (int i = 0; i < message.length(); i += 1)
      { v = v << 4 + hexdigit(message[i]);
        if (i % 14 == 12)
        { lli c = modpower(v, d, n);
          sevenout(c);
          v = 0; } }
      if (v != 0)
      { lli c = modpower(v, d, n);
        sevenout(c); }
      cout << "\n"; }

    else
    { v = 0;
      for (int i = 0; i < message.length(); i += 1)
      { v = v << 8 + message[i];
        if (i % 7 == 6)
        { lli c = modpower(v, d, n);
          cout << " " << hex << c;
          v = 0; } }
      if (v != 0)
      { lli c = modpower(v, d, n);
        cout << " " << hex << c; }
      cout << "\n"; } }
  else
    usage(); }


void main(int argc, char *argv[])
{ if (argc != 3)
  { fprintf(stderr, "Need a number and a probability logarithm on the command line\n");
    exit(1); }
  srandomdev();
  int n = atol(argv[1]);
  if (n % 2 == 0 && n != 2)
  { printf("%d is definitely NOT prime\n", n);
    exit(1); }
  int pp = atol(argv[2]);
  double p = exp(pp * log(10.0));
  double psofar = 1.0;
  int ok = 1;
  while (psofar > p)
  { int r = random() % (n - 2) + 2;
    int x = modpower(r, (n - 1) / 2, n);
    if (x != 1 && x != n - 1) 
    { ok = 0;         
      break; }
    psofar *= 0.5; }
  if (ok)
    printf("%d is prime with probability better than %.15f\n", n, 1.0 - p);
  else
    printf("%d is definitely NOT prime\n", n); }