using System;
using System.Threading.Tasks;
namespace ConsoleApp22
{
class Program
{
/*static int ModInverse(int a, int m)
{
for (int x = 1; x < m; x++)
if (((a % m) * (x % m)) % m == 1)
return x;
return 0;
}
public static double gcdex(double a, double b, out double x, out double y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
double x1, y1;
double d1 = gcdex(b, a % b, out x1, out y1);
x = y1;
y = x1 - (a / b) * y1;
return d1;
}
public static int ReverseElement(double a, double N, out double result)
{
double x , y , d;
d = gcdex(a, N,out x,out y);
if (d != 1)
{
result = 1;
return 1;
}
else
{
result = x;
return 0;
}
}
private static double BinModPow(double a, double b, double n)
{
decimal x = (decimal)b;
int i = 0;
do
{
if (x % 2 == 1) x--;
x = x / 2;
i++;
}
while (x > 0);
x = (decimal)b;
decimal[] ar = new decimal[i];
for (i = 0; i < ar.Length; i++)
{
ar[i] = x % 2;
if (x % 2 == 1) x--;
x = x / 2;
}
x = (decimal)a;
for (i = ar.Length - 2; i >= 0; i--)
{
x = (x * x) % (decimal)n;
x = (x * (decimal)Math.Pow(a, (double)ar[i])) % (decimal)n;
}
return (double)x;
}
*/
public static bool num(long n)
{
if (n < 2)
return false;
if (n == 2)
return true;
for (long i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}
static double gcdExtended(double a, double b, out double x, out double y)
{
if (a == 0)
{
x = 0; y = 1;
return b;
}
double x1, y1;
double gcd = gcdExtended(b % a, a, out x1, out y1);
x = y1 - (b / a) * x1;
y = x1;
return gcd;
}
static double modInverse(int a, int m)
{
double x, y;
double g = gcdExtended(a, m, out x, out y);
if (g != 1)
{
Console.WriteLine("No inverse");
return 0;
}
else
{
double res = (x % m + m) % m;
return res;
}
}
static int ModInverse(int a, int m)
{
a = a % m;
for (int x = 1; x < m; x++)
if ((a * x) % m == 1)
return x;
return 1;
}
static void Main(string[] args)
{
double x, g, y, u1, u2, r = 0, s = 0;
int p, q;
string ss = Console.ReadLine();
p = Convert.ToInt32(Console.ReadLine());
q = Convert.ToInt32(Console.ReadLine());
if (num(p) && num(q))
{
Random
rand = new Random
(); g = Math.Pow(2.0, ((p - 1.0) / q)) % p;
y = Math.Pow(g, x) % p;
r = 0;
s = 0;
while ((r == 0) && (s == 0))
{
double k
= rand.
Next(1, q
); r = (Math.Pow(g, k) % p) % q;
s = (Math.Pow(k, -1) * (ss.GetHashCode() + x * r)) % q;
}
Console.WriteLine(ss.GetHashCode());
double w = ModInverse(ss.GetHashCode(), q );
//ReverseElement(, out w);
//w = Math.Pow(ss.GetHashCode(), q - 2) % q;
//w = BinModPow(ss.GetHashCode(), ss.GetHashCode(),q);
u1 =( s * w) %q;
//Console.WriteLine(w);
//u1 = (s * Math.Pow(ss.GetHashCode(), -1))%q;
Console.WriteLine("Hash: " + ss.GetHashCode());
u2 = ((-1*r) * w) ;
//u2 = ((-1 * r) * Math.Pow(ss.GetHashCode(), -1)) % q;
var v = ((Math.Pow(g, u1) * Math.Pow(y, u2)) % p) % q;
Console.WriteLine(v.ToString() + "\n" + r.ToString());
if (Math.Abs(v - r) < 1e-6)
Console.WriteLine("Подпись подлинная");
else
Console.WriteLine("Подпись не подлинная");
}
else
{
Console.WriteLine("p или q - не простые числа!");
}
}
}
}
CnVzaW5nIFN5c3RlbTsKdXNpbmcgU3lzdGVtLlRocmVhZGluZy5UYXNrczsKCm5hbWVzcGFjZSBDb25zb2xlQXBwMjIKewogICAgY2xhc3MgUHJvZ3JhbQogICAgewoKICAgICAgICAvKnN0YXRpYyBpbnQgTW9kSW52ZXJzZShpbnQgYSwgaW50IG0pCiAgICAgICAgewogICAgICAgICAgICBmb3IgKGludCB4ID0gMTsgeCA8IG07IHgrKykKICAgICAgICAgICAgICAgIGlmICgoKGEgJSBtKSAqICh4ICUgbSkpICUgbSA9PSAxKQogICAgICAgICAgICAgICAgICAgIHJldHVybiB4OwogICAgICAgICAgICByZXR1cm4gMDsKICAgICAgICB9CiAgICAgICAgcHVibGljIHN0YXRpYyBkb3VibGUgZ2NkZXgoZG91YmxlIGEsIGRvdWJsZSBiLCBvdXQgZG91YmxlIHgsIG91dCBkb3VibGUgeSkKICAgICAgICB7CiAgICAgICAgICAgIGlmIChiID09IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHggPSAxOwogICAgICAgICAgICAgICAgeSA9IDA7CiAgICAgICAgICAgICAgICByZXR1cm4gYTsKICAgICAgICAgICAgfQogICAgICAgICAgICBkb3VibGUgeDEsIHkxOwogICAgICAgICAgICBkb3VibGUgZDEgPSBnY2RleChiLCBhICUgYiwgb3V0IHgxLCBvdXQgeTEpOwogICAgICAgICAgICB4ID0geTE7CiAgICAgICAgICAgIHkgPSB4MSAtIChhIC8gYikgKiB5MTsKICAgICAgICAgICAgcmV0dXJuIGQxOwogICAgICAgIH0KCiAgICAgICAgcHVibGljIHN0YXRpYyBpbnQgUmV2ZXJzZUVsZW1lbnQoZG91YmxlIGEsIGRvdWJsZSBOLCBvdXQgZG91YmxlIHJlc3VsdCkKICAgICAgICB7CiAgICAgICAgICAgIGRvdWJsZSB4ICwgeSAsIGQ7CiAgICAgICAgICAgIGQgPSBnY2RleChhLCBOLG91dCAgeCxvdXQgeSk7CiAgICAgICAgICAgIGlmIChkICE9IDEpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJlc3VsdCA9IDE7CiAgICAgICAgICAgICAgICByZXR1cm4gMTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICByZXN1bHQgPSB4OwogICAgICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIGRvdWJsZSBCaW5Nb2RQb3coZG91YmxlIGEsIGRvdWJsZSBiLCBkb3VibGUgbikKICAgICAgICB7CiAgICAgICAgICAgIGRlY2ltYWwgeCA9IChkZWNpbWFsKWI7CiAgICAgICAgICAgIGludCBpID0gMDsKICAgICAgICAgICAgZG8KICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKHggJSAyID09IDEpIHgtLTsKICAgICAgICAgICAgICAgIHggPSB4IC8gMjsKICAgICAgICAgICAgICAgIGkrKzsKICAgICAgICAgICAgfQogICAgICAgICAgICB3aGlsZSAoeCA+IDApOwogICAgICAgICAgICB4ID0gKGRlY2ltYWwpYjsKICAgICAgICAgICAgZGVjaW1hbFtdIGFyID0gbmV3IGRlY2ltYWxbaV07CiAgICAgICAgICAgIGZvciAoaSA9IDA7IGkgPCBhci5MZW5ndGg7IGkrKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgYXJbaV0gPSB4ICUgMjsKICAgICAgICAgICAgICAgIGlmICh4ICUgMiA9PSAxKSB4LS07CiAgICAgICAgICAgICAgICB4ID0geCAvIDI7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgeCA9IChkZWNpbWFsKWE7CiAgICAgICAgICAgIGZvciAoaSA9IGFyLkxlbmd0aCAtIDI7IGkgPj0gMDsgaS0tKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB4ID0gKHggKiB4KSAlIChkZWNpbWFsKW47CiAgICAgICAgICAgICAgICB4ID0gKHggKiAoZGVjaW1hbClNYXRoLlBvdyhhLCAoZG91YmxlKWFyW2ldKSkgJSAoZGVjaW1hbCluOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHJldHVybiAoZG91YmxlKXg7CiAgICAgICAgfQoKICAgICAgIAogICAgICAgICovCiAgICAgICAgcHVibGljIHN0YXRpYyBib29sIG51bShsb25nIG4pCiAgICAgICAgewogICAgICAgICAgICBpZiAobiA8IDIpCiAgICAgICAgICAgICAgICByZXR1cm4gZmFsc2U7CgogICAgICAgICAgICBpZiAobiA9PSAyKQogICAgICAgICAgICAgICAgcmV0dXJuIHRydWU7CgogICAgICAgICAgICBmb3IgKGxvbmcgaSA9IDI7IGkgPCBuOyBpKyspCiAgICAgICAgICAgICAgICBpZiAobiAlIGkgPT0gMCkKICAgICAgICAgICAgICAgICAgICByZXR1cm4gZmFsc2U7CgogICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICB9CiAgICAgICAgc3RhdGljIGRvdWJsZSBnY2RFeHRlbmRlZChkb3VibGUgYSwgZG91YmxlIGIsIG91dCBkb3VibGUgeCwgb3V0IGRvdWJsZSB5KQogICAgICAgIHsKCiAgICAgICAgICAgIGlmIChhID09IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHggPSAwOyB5ID0gMTsKICAgICAgICAgICAgICAgIHJldHVybiBiOwogICAgICAgICAgICB9CgogICAgICAgICAgICBkb3VibGUgeDEsIHkxOwogICAgICAgICAgICBkb3VibGUgZ2NkID0gZ2NkRXh0ZW5kZWQoYiAlIGEsIGEsIG91dCB4MSwgb3V0IHkxKTsKICAgICAgICAgICAgeCA9IHkxIC0gKGIgLyBhKSAqIHgxOwogICAgICAgICAgICB5ID0geDE7CgogICAgICAgICAgICByZXR1cm4gZ2NkOwogICAgICAgIH0KICAgICAgICBzdGF0aWMgZG91YmxlIG1vZEludmVyc2UoaW50IGEsIGludCBtKQogICAgICAgIHsKICAgICAgICAgICAgZG91YmxlIHgsIHk7CiAgICAgICAgICAgIGRvdWJsZSBnID0gZ2NkRXh0ZW5kZWQoYSwgbSwgb3V0IHgsIG91dCB5KTsKICAgICAgICAgICAgaWYgKGcgIT0gMSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgQ29uc29sZS5Xcml0ZUxpbmUoIk5vIGludmVyc2UiKTsKICAgICAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZG91YmxlIHJlcyA9ICh4ICUgbSArIG0pICUgbTsKICAgICAgICAgICAgICAgIHJldHVybiByZXM7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgc3RhdGljIGludCBNb2RJbnZlcnNlKGludCBhLCBpbnQgbSkKICAgICAgICB7CiAgICAgICAgICAgIGEgPSBhICUgbTsKICAgICAgICAgICAgZm9yIChpbnQgeCA9IDE7IHggPCBtOyB4KyspCiAgICAgICAgICAgICAgICBpZiAoKGEgKiB4KSAlIG0gPT0gMSkKICAgICAgICAgICAgICAgICAgICByZXR1cm4geDsKICAgICAgICAgICAgcmV0dXJuIDE7CiAgICAgICAgfQogICAgICAgIHN0YXRpYyB2b2lkIE1haW4oc3RyaW5nW10gYXJncykKICAgICAgICB7CgogICAgICAgICAgICBkb3VibGUgeCwgZywgeSwgdTEsIHUyLCByID0gMCwgcyA9IDA7CiAgICAgICAgICAgIGludCBwLCBxOwogICAgICAgICAgICBzdHJpbmcgc3MgPSBDb25zb2xlLlJlYWRMaW5lKCk7CiAgICAgICAgICAgIHAgPSBDb252ZXJ0LlRvSW50MzIoQ29uc29sZS5SZWFkTGluZSgpKTsKICAgICAgICAgICAgcSA9IENvbnZlcnQuVG9JbnQzMihDb25zb2xlLlJlYWRMaW5lKCkpOwoKICAgICAgICAgICAgaWYgKG51bShwKSAmJiBudW0ocSkpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIFJhbmRvbSByYW5kID0gbmV3IFJhbmRvbSgpOwogICAgICAgICAgICAgICAgeCA9IHJhbmQuTmV4dCgwLCAxMjgpOwogICAgICAgICAgICAgICAgZyA9IE1hdGguUG93KDIuMCwgKChwIC0gMS4wKSAvIHEpKSAlIHA7CiAgICAgICAgICAgICAgICB5ID0gTWF0aC5Qb3coZywgeCkgJSBwOwogICAgICAgICAgICAgICAgciA9IDA7CiAgICAgICAgICAgICAgICBzID0gMDsKICAgICAgICAgICAgICAgIHdoaWxlICgociA9PSAwKSAmJiAocyA9PSAwKSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBkb3VibGUgayA9IHJhbmQuTmV4dCgxLCBxKTsKICAgICAgICAgICAgICAgICAgICByID0gKE1hdGguUG93KGcsIGspICUgcCkgJSBxOwogICAgICAgICAgICAgICAgICAgIHMgPSAoTWF0aC5Qb3coaywgLTEpICogKHNzLkdldEhhc2hDb2RlKCkgKyB4ICogcikpICUgcTsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZShzcy5HZXRIYXNoQ29kZSgpKTsKCiAgICAgICAgICAgICAgICBkb3VibGUgdyA9IE1vZEludmVyc2Uoc3MuR2V0SGFzaENvZGUoKSwgcSAgKTsKICAgICAgICAgICAgICAgIC8vUmV2ZXJzZUVsZW1lbnQoLCBvdXQgdyk7CiAgICAgICAgICAgICAgICAvL3cgPSBNYXRoLlBvdyhzcy5HZXRIYXNoQ29kZSgpLCBxIC0gMikgJSBxOwogICAgICAgICAgICAgICAgLy93ID0gQmluTW9kUG93KHNzLkdldEhhc2hDb2RlKCksIHNzLkdldEhhc2hDb2RlKCkscSk7CiAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgdTEgPSggcyAqIHcpICVxOwogICAgICAgICAgICAgICAgLy9Db25zb2xlLldyaXRlTGluZSh3KTsKICAgICAgICAgICAgICAgIC8vdTEgPSAocyAqIE1hdGguUG93KHNzLkdldEhhc2hDb2RlKCksIC0xKSklcTsKICAgICAgICAgICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKCJIYXNoOiAiICsgc3MuR2V0SGFzaENvZGUoKSk7CiAgICAgICAgICAgICAgICB1MiA9ICgoLTEqcikgKiB3KSA7CiAgICAgICAgICAgICAgICAvL3UyID0gICgoLTEgKiByKSAqIE1hdGguUG93KHNzLkdldEhhc2hDb2RlKCksIC0xKSkgJSBxOwogICAgICAgICAgICAgICAgdmFyIHYgPSAoKE1hdGguUG93KGcsIHUxKSAqIE1hdGguUG93KHksIHUyKSkgJSBwKSAlIHE7CgogICAgICAgICAgICAgICAgQ29uc29sZS5Xcml0ZUxpbmUodi5Ub1N0cmluZygpICsgIlxuIiArIHIuVG9TdHJpbmcoKSk7CgogICAgICAgICAgICAgICAgaWYgKE1hdGguQWJzKHYgLSByKSA8IDFlLTYpCiAgICAgICAgICAgICAgICAgICAgQ29uc29sZS5Xcml0ZUxpbmUoItCf0L7QtNC/0LjRgdGMINC/0L7QtNC70LjQvdC90LDRjyIpOwogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKCLQn9C+0LTQv9C40YHRjCDQvdC1INC/0L7QtNC70LjQvdC90LDRjyIpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgQ29uc29sZS5Xcml0ZUxpbmUoInAg0LjQu9C4IHEgLSDQvdC1INC/0YDQvtGB0YLRi9C1INGH0LjRgdC70LAhIik7CgogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9CgoKCgo=