fork download
copy 
  1.  
  2. using System;
  3. using System.Threading.Tasks;
  4.  
  5. namespace ConsoleApp22
  6. {
  7.     class Program
  8.     {
  9.  
  10.         /*static int ModInverse(int a, int m)
  11.         {
  12.             for (int x = 1; x < m; x++)
  13.                 if (((a % m) * (x % m)) % m == 1)
  14.                     return x;
  15.             return 0;
  16.         }
  17.         public static double gcdex(double a, double b, out double x, out double y)
  18.         {
  19.             if (b == 0)
  20.             {
  21.                 x = 1;
  22.                 y = 0;
  23.                 return a;
  24.             }
  25.             double x1, y1;
  26.             double d1 = gcdex(b, a % b, out x1, out y1);
  27.             x = y1;
  28.             y = x1 - (a / b) * y1;
  29.             return d1;
  30.         }
  31.  
  32.         public static int ReverseElement(double a, double N, out double result)
  33.         {
  34.             double x , y , d;
  35.             d = gcdex(a, N,out  x,out y);
  36.             if (d != 1)
  37.             {
  38.                 result = 1;
  39.                 return 1;
  40.             }
  41.             else
  42.              {
  43.                 result = x;
  44.                 return 0;
  45.             }
  46.         }
  47.  
  48.         private static double BinModPow(double a, double b, double n)
  49.         {
  50.             decimal x = (decimal)b;
  51.             int i = 0;
  52.             do
  53.             {
  54.                 if (x % 2 == 1) x--;
  55.                 x = x / 2;
  56.                 i++;
  57.             }
  58.             while (x > 0);
  59.             x = (decimal)b;
  60.             decimal[] ar = new decimal[i];
  61.             for (i = 0; i < ar.Length; i++)
  62.             {
  63.                 ar[i] = x % 2;
  64.                 if (x % 2 == 1) x--;
  65.                 x = x / 2;
  66.             }
  67.             x = (decimal)a;
  68.             for (i = ar.Length - 2; i >= 0; i--)
  69.             {
  70.                 x = (x * x) % (decimal)n;
  71.                 x = (x * (decimal)Math.Pow(a, (double)ar[i])) % (decimal)n;
  72.             }
  73.             return (double)x;
  74.         }
  75.  
  76.        
  77.         */
  78.         public static bool num(long n)
  79.         {
  80.             if (n < 2)
  81.                 return false;
  82.  
  83.             if (n == 2)
  84.                 return true;
  85.  
  86.             for (long i = 2; i < n; i++)
  87.                 if (n % i == 0)
  88.                     return false;
  89.  
  90.             return true;
  91.         }
  92.         static double gcdExtended(double a, double b, out double x, out double y)
  93.         {
  94.  
  95.             if (a == 0)
  96.             {
  97.                 x = 0; y = 1;
  98.                 return b;
  99.             }
  100.  
  101.             double x1, y1;
  102.             double gcd = gcdExtended(b % a, a, out x1, out y1);
  103.             x = y1 - (b / a) * x1;
  104.             y = x1;
  105.  
  106.             return gcd;
  107.         }
  108.         static double modInverse(int a, int m)
  109.         {
  110.             double x, y;
  111.             double g = gcdExtended(a, m, out x, out y);
  112.             if (g != 1)
  113.             {
  114.                 Console.WriteLine("No inverse");
  115.                 return 0;
  116.             }
  117.             else
  118.             {
  119.                 double res = (x % m + m) % m;
  120.                 return res;
  121.             }
  122.         }
  123.         static int ModInverse(int a, int m)
  124.         {
  125.             a = a % m;
  126.             for (int x = 1; x < m; x++)
  127.                 if ((a * x) % m == 1)
  128.                     return x;
  129.             return 1;
  130.         }
  131.         static void Main(string[] args)
  132.         {
  133.  
  134.             double x, g, y, u1, u2, r = 0, s = 0;
  135.             int p, q;
  136.             string ss = Console.ReadLine();
  137.             p = Convert.ToInt32(Console.ReadLine());
  138.             q = Convert.ToInt32(Console.ReadLine());
  139.  
  140.             if (num(p) && num(q))
  141.             {
  142.                 Random rand = new Random();
  143.                 x = rand.Next(0, 128);
  144.                 g = Math.Pow(2.0, ((p - 1.0) / q)) % p;
  145.                 y = Math.Pow(g, x) % p;
  146.                 r = 0;
  147.                 s = 0;
  148.                 while ((r == 0) && (s == 0))
  149.                 {
  150.                     double k = rand.Next(1, q);
  151.                     r = (Math.Pow(g, k) % p) % q;
  152.                     s = (Math.Pow(k, -1) * (ss.GetHashCode() + x * r)) % q;
  153.                 }
  154.  
  155.                 Console.WriteLine(ss.GetHashCode());
  156.  
  157.                 double w = ModInverse(ss.GetHashCode(), q  );
  158.                 //ReverseElement(, out w);
  159.                 //w = Math.Pow(ss.GetHashCode(), q - 2) % q;
  160.                 //w = BinModPow(ss.GetHashCode(), ss.GetHashCode(),q);
  161.  
  162.                 u1 =( s * w) %q;
  163.                 //Console.WriteLine(w);
  164.                 //u1 = (s * Math.Pow(ss.GetHashCode(), -1))%q;
  165.                 Console.WriteLine("Hash: " + ss.GetHashCode());
  166.                 u2 = ((-1*r) * w) ;
  167.                 //u2 =  ((-1 * r) * Math.Pow(ss.GetHashCode(), -1)) % q;
  168.                 var v = ((Math.Pow(g, u1) * Math.Pow(y, u2)) % p) % q;
  169.  
  170.                 Console.WriteLine(v.ToString() + "\n" + r.ToString());
  171.  
  172.                 if (Math.Abs(v - r) < 1e-6)
  173.                     Console.WriteLine("Подпись подлинная");
  174.                 else
  175.                     Console.WriteLine("Подпись не подлинная");
  176.             }
  177.             else
  178.             {
  179.                 Console.WriteLine("p или q - не простые числа!");
  180.  
  181.             }
  182.         }
  183.     }
  184. }
  185.  
  186.  
  187.  
  188.  
  189.  
Success #stdin #stdout 0.03s 22776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
p или q - не простые числа!
https://ideone.com/i8Q2CB
language:
C# (gmcs 5.20.1)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!