API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 14th, 2019
107
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 20.85 KB | None | 0 0
raw download clone embed print report
  1. using System;
  2. using System.Collections.Generic;
  3. using System.IO;
  4. using System.Linq;
  5. using System.Numerics;
  6. using System.Text;
  7. using System.Security.Cryptography;
  8.  
  9. namespace methods
  10. {
  11.     class Program
  12.     {
  13.         public static BigInteger p, A, NR;
  14.         public static int w = 0;
  15.         public static List<BigInteger> NR_;
  16.  
  17.         static BigInteger Pow(BigInteger a, BigInteger b)
  18.         {
  19.             BigInteger result = 1;
  20.             for (BigInteger i = 0; i < b; i++)
  21.                 result *= a;
  22.        
  23.             return result;
  24.         }
  25.         static bool IsPrime(BigInteger p)
  26.         {
  27.             BigInteger rounds = 30, t = p - 1;
  28.             if (p == 2 || p == 3)
  29.                 return true;
  30.  
  31.             if (p < 2 || p % 2 == 0)
  32.                 return false;
  33.  
  34.             int s = 0;
  35.             while (t % 2 == 0)
  36.             {
  37.                 t /= 2;
  38.                 s += 1;
  39.             }
  40.  
  41.             for (int i = 0; i < rounds; i++)
  42.             {
  43.                 RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
  44.                 byte[] _a = new byte[p.ToByteArray().LongLength];
  45.                 BigInteger a;
  46.                 do
  47.                 {
  48.                     rng.GetBytes(_a);
  49.                     a = new BigInteger(_a);
  50.                 }
  51.                 while (a < 2 || a >= p - 2);
  52.  
  53.                 BigInteger x = BigInteger.ModPow(a, t, p);
  54.                 if (x == 1 || x == p - 1)
  55.                     continue;
  56.  
  57.                 for (int r = 1; r < s; r++)
  58.                 {
  59.                     x = BigInteger.ModPow(x, 2, p);
  60.  
  61.                     if (x == 1)
  62.                         return false;
  63.  
  64.                     if (x == p - 1)
  65.                         break;
  66.                 }
  67.  
  68.                 if (x != p - 1)
  69.                     return false;
  70.             }
  71.             return true;
  72.         }
  73.  
  74.         static BigInteger GenerateNumberOfLength(int l)
  75.         {
  76.             RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
  77.             byte[] _result = new byte[BigInteger.Pow(2, l).ToByteArray().LongLength];
  78.             BigInteger result;
  79.             do
  80.             {
  81.                 rng.GetBytes(_result);
  82.                 result = new BigInteger(_result);
  83.             } while (result <= BigInteger.Pow(2, (l - 1)) || result >= BigInteger.Pow(2, l));
  84.            
  85.             return result;
  86.         }
  87.  
  88.         static BigInteger GenerateSimpleNumberOfLength(int l)
  89.         {  
  90.             BigInteger result;
  91.             result = GenerateNumberOfLength(l);
  92.             while (!IsPrime(result))
  93.             {  
  94.                 result = GenerateNumberOfLength(l);
  95.             }
  96.             return result;
  97.         }
  98.  
  99.         private static void FindPrimeNumberOfLength(int l)
  100.         {
  101.             do
  102.             {
  103.                 p = GenerateSimpleNumberOfLength(l);
  104.             } while ((p % 4) != 1);
  105.         }
  106.  
  107.         private static Boolean CheckSqrt(BigInteger n, BigInteger root)
  108.         {
  109.             BigInteger lowerBound = root * root, upperBound = (root + 1) * (root + 1);
  110.  
  111.             return (n >= lowerBound && n < upperBound);
  112.         }
  113.  
  114.         public static BigInteger Sqrt_N(BigInteger N)
  115.         {
  116.             if (N == 0)
  117.                 return 0;
  118.  
  119.             if (N > 0)
  120.             {
  121.                 int bitLength = Convert.ToInt32(Math.Ceiling(BigInteger.Log(N, 2)));
  122.                 BigInteger root = BigInteger.One << (bitLength / 2);
  123.  
  124.                 while (!CheckSqrt(N, root))
  125.                 {
  126.                     root += N / root;
  127.                     root /= 2;
  128.                 }
  129.                 return root;
  130.             }
  131.             throw new ArithmeticException("NaN");
  132.         }
  133.  
  134.         static BigInteger BinaryEuclide(BigInteger a, BigInteger b)
  135.         {
  136.             BigInteger g = 1;
  137.             while (a % 2 == 0 && b % 2 == 0)
  138.             {
  139.                 a = a / 2;
  140.                 b = b / 2;
  141.                 g = 2 * g;
  142.             }
  143.             BigInteger u = a, v = b;
  144.             while (u != 0)
  145.             {
  146.                 while (u % 2 == 0) u = u / 2;
  147.                 while (v % 2 == 0) v = v / 2;
  148.                 if (u >= v) u = u - v;
  149.                 else v = v - u;
  150.             }
  151.             return g * v;
  152.         }
  153.  
  154.         static Tuple<BigInteger,BigInteger> ExtendedEuclide(BigInteger a, BigInteger b)
  155.         {
  156.             BigInteger r0 = a, r1 = b, x0 = 1, x1 = 0, y0 = 0, y1 = 1, x, y, d;
  157.             while (true)
  158.             {
  159.                 BigInteger q = r0 / r1, r = r0 % r1;
  160.                 if (r == 0)
  161.                     break;
  162.                 else
  163.                 {
  164.                     r0 = r1;
  165.                     r1 = r;
  166.                     x = x0 - q * x1;
  167.                     x0 = x1;
  168.                     x1 = x;
  169.                     y = y0 - q * y1;
  170.                     y0 = y1;
  171.                     y1 = y;
  172.                 }
  173.             }
  174.             d = r1;
  175.             x = x1;
  176.             y = y1;
  177.             return new Tuple<BigInteger,BigInteger>(x, y);
  178.         }
  179.  
  180.         public static int Legendre(BigInteger a, BigInteger p)
  181.         {
  182.             if (p < 2)
  183.                 Console.WriteLine("P должно быть больше 2");
  184.             if (a == 0)
  185.                 return 0;
  186.            
  187.             if (a == 1)
  188.                 return 1;
  189.            
  190.             int result;
  191.             if (a < 0)
  192.             {
  193.                 result = Legendre(-a, p);
  194.                 BigInteger deg = (p - 1) / 2;
  195.                 if (deg % 2 != 0) result = -result;
  196.             }
  197.             else
  198.             {
  199.                 if (a % 2 == 0)
  200.                 {
  201.                     result = Legendre(a / 2, p);
  202.                     BigInteger deg = (p * p - 1) / 8;
  203.                     if (deg % 2 != 0) result = -result;
  204.                 }
  205.                 else
  206.                 {
  207.                     result = Legendre(p % a, a);
  208.                     BigInteger deg = (a - 1) * ((p - 1) / (4));
  209.                     if (deg % 2 != 0) result = -result;
  210.                 }
  211.             }
  212.             return result;
  213.         }
  214.  
  215.         static BigInteger Jacobi(BigInteger a, BigInteger n)
  216.         {
  217.             if (BinaryEuclide(a, n) != 1)
  218.                 return 0;
  219.            
  220.             BigInteger r = 1;
  221.             if (a < 0)
  222.             {
  223.                 a = -a;
  224.                 if (n % 4 == 3)
  225.                     r = -r;
  226.             }
  227.             while (a != 0)
  228.             {
  229.                 BigInteger k = 0;
  230.                 while (a % 2 == 0)
  231.                 {
  232.                     k++;
  233.                     a = a / 2;
  234.                 }
  235.                 if (k % 2 != 0)
  236.                 {
  237.                     if (n % 8 == 3 || n % 8 == 5)
  238.                         r = -r;
  239.                 }
  240.                 if (n % 4 == 3 && a % 4 == 3)
  241.                     r = -r;
  242.                
  243.                 BigInteger temp = a;
  244.                 a = n % a;
  245.                 n = temp;
  246.             }
  247.             return r;
  248.         }
  249.  
  250.         static List<BigInteger> ComparisonSolution(BigInteger a, BigInteger b, BigInteger m)
  251.         {
  252.             List<BigInteger> answer = new List<BigInteger>();
  253.             BigInteger d = BinaryEuclide(a, m);
  254.             if (b % d != 0)
  255.                 return answer;
  256.            
  257.             else
  258.             {
  259.                 BigInteger a1 = a / d, b1 = b / d, m1 = m / d;
  260.                 Tuple<BigInteger, BigInteger> xy = ExtendedEuclide(a1, m1);
  261.                 BigInteger x0 = (b1 * xy.Item1) % m1;
  262.                 while (x0 < 0)
  263.                     x0 = x0 + m1;
  264.                 answer.Add(x0 % m1);
  265.             }
  266.             return answer;
  267.         }
  268.  
  269.         static BigInteger ReverseElement(BigInteger a, BigInteger m)
  270.         {
  271.             BigInteger d = BinaryEuclide(a, m);
  272.             if (d != 1)
  273.                 return -1;
  274.            
  275.             else
  276.             {
  277.                 List<BigInteger> answer = ComparisonSolution(a, 1, m);
  278.                 return answer[0];
  279.             }
  280.         }
  281.  
  282.         static BigInteger SqrtMod(BigInteger a, BigInteger p)
  283.         {
  284.             a += p;
  285.             BigInteger jacobi = Jacobi(a, p);
  286.             if (jacobi == -1)
  287.                 return 0;
  288.            
  289.             int N = 0;
  290.             if (jacobi == 1)
  291.             {
  292.                 for (int i = 2; i < p; i++)
  293.                 {
  294.                     if (Jacobi(i, p) == -1)
  295.                     {
  296.                         N = i;
  297.                         break;
  298.                     }
  299.                 }
  300.             }
  301.             BigInteger h = p - 1;
  302.             int k = 0;
  303.             while (h % 2 == 0)
  304.             {
  305.                 k++;
  306.                 h = h / 2;
  307.             }
  308.             BigInteger a1 = (int)BigInteger.ModPow(a, (h + 1) / 2, p);
  309.             BigInteger a2 = ReverseElement(a, p);
  310.             BigInteger N1 = BigInteger.ModPow(N, h, p);
  311.             BigInteger N2 = 1;
  312.             BigInteger[] j = new BigInteger[k - 1];
  313.             for (int i = 0; i <= k - 2; i++)
  314.             {
  315.                 BigInteger b = (a1 * N2) % p;
  316.                 BigInteger c = (a2 * b * b) % p;
  317.                 BigInteger pow = Pow(2, k - 2 - i);
  318.                 BigInteger d = BigInteger.ModPow(c, pow, p);
  319.                 if (d == 1)
  320.                     j[i] = 0;
  321.                
  322.                 if (d == p - 1 || d - p == -1)
  323.                     j[i] = 1;
  324.                
  325.                 N2 = (N2 * (BigInteger.ModPow(N1, BigInteger.Pow(2, i) * j[i], p))) % p;
  326.             }
  327.             BigInteger answer = (a1 * N2) % p;
  328.             BigInteger answer1 = (-answer + p) % p;
  329.             return answer;
  330.         }
  331.  
  332.         public static List<BigInteger> Decomposition_P(BigInteger D, BigInteger p)
  333.         {
  334.             if (Legendre(-D, p) == -1)
  335.                 return new List<BigInteger>();
  336.             BigInteger R = SqrtMod(-D, p);
  337.             int i = 0;
  338.             List<BigInteger> U = new List<BigInteger>();
  339.             List<BigInteger> M = new List<BigInteger>();
  340.             U.Add(R);
  341.             M.Add(p);
  342.             do
  343.             {
  344.                 M.Add((U[i] * U[i] + D) / M[i]);
  345.                 U.Add(BigInteger.Min(U[i] % M[i + 1], M[i + 1] - U[i] % M[i + 1]));
  346.                 i++;
  347.             } while (M[i] != 1);
  348.             i--;
  349.             List<BigInteger> a = new List<BigInteger>();
  350.             List<BigInteger> b = new List<BigInteger>();
  351.             for (int j = 0; j <= i; j++)
  352.             {
  353.                 a.Add(0);
  354.                 b.Add(0);
  355.             }
  356.             a[i] = U[i];
  357.             b[i] = 1;
  358.             while (i != 0)
  359.             {
  360.                 BigInteger znamenatel = a[i] * a[i] + D * b[i] * b[i];
  361.                 if ((U[i - 1] * a[i] + D * b[i]) % znamenatel == 0)
  362.                     a[i - 1] = (U[i - 1] * a[i] + D * b[i]) / znamenatel;
  363.                
  364.                 else
  365.                     a[i - 1] = (-U[i - 1] * a[i] + D * b[i]) / znamenatel;
  366.                
  367.                 if ((-a[i] + U[i - 1] * b[i]) % znamenatel == 0)
  368.                     b[i - 1] = (-a[i] + U[i - 1] * b[i]) / znamenatel;
  369.                 else
  370.                     b[i - 1] = (-a[i] - U[i - 1] * b[i]) / znamenatel;
  371.                
  372.                 i--;
  373.             }
  374.             List<BigInteger> answer = new List<BigInteger>();
  375.             answer.Add(a[0]);
  376.             answer.Add(b[0]);
  377.             return answer;
  378.         }
  379.  
  380.         public static bool CheckQuadraticResidue(BigInteger A, BigInteger p) =>
  381.         BigInteger.ModPow(A, (p - 1) / 2, p) == 1;
  382.  
  383.         private static void CheckA(ref bool t, ref BigInteger k, int n)
  384.         {
  385.             if (NR_[0] == NR_[1] * n)
  386.             {
  387.                 for (BigInteger i = k; ; i++)
  388.                 {
  389.                     if (i > 1000000)
  390.                     {
  391.                         t = false;
  392.                         break;
  393.                     }
  394.                     bool flag = CheckQuadraticResidue((i + 1) % p, NR_[0]);
  395.                     if (n == 4 && flag || n == 2 && !flag)
  396.                     {
  397.                         A = i;
  398.                         k = A + 1;
  399.                         break;
  400.                     }
  401.                 }
  402.             }
  403.         }
  404.  
  405.         private static List<BigInteger> NR_function(BigInteger a, BigInteger b, BigInteger p)
  406.         {
  407.             List<BigInteger> T = new List<BigInteger>();
  408.             T.Add(b * (-2));
  409.             T.Add(a * 2);
  410.             T.Add(b * 2);
  411.             T.Add(a * (-2));
  412.             for (int i = 0; i < T.Count; i++)
  413.             {
  414.                 T[i] += (1 + p);
  415.  
  416.                 if ((T[i] % 2).Equals(0) && IsPrime((T[i] / 2)))
  417.                     return new List<BigInteger>() {T[i],T[i] / 2};
  418.                
  419.                 else
  420.                     if ((T[i] % 4).Equals(0) && IsPrime((T[i] / 4)))
  421.                         return new List<BigInteger>() {T[i],T[i] / 4};
  422.             }
  423.             return new List<BigInteger>();
  424.         }
  425.  
  426.          public static List<BigInteger> SumPoints(List<BigInteger> P1, List<BigInteger> P2, BigInteger A, BigInteger p)
  427.         {
  428.             List<BigInteger> answer = new List<BigInteger>();
  429.             BigInteger x1 = P1[0],y1 = P1[1], x2 = P2[0], y2 = P2[1], alpha;
  430.             if (x1 == x2 && y1 == y2)
  431.             {
  432.                 BigInteger numerator = (3 * x1 * x1 + A) % p, denomerator = (2 * y1) % p;
  433.                 if (denomerator == 0)
  434.                     return answer;
  435.                 alpha = numerator * ReverseElement(denomerator, p) % p;
  436.             }
  437.             else
  438.             {
  439.                 BigInteger numerator = (y2 - y1) % p, denomerator = (x2 - x1) % p;
  440.                 denomerator = denomerator >= 0 ? denomerator : denomerator + p;
  441.                 if (denomerator == 0)
  442.                     return answer;
  443.                 alpha = numerator * ReverseElement(denomerator, p) % p;
  444.             }
  445.             BigInteger xr = (alpha * alpha - x1 - x2) % p, yr = (-y1 + alpha * (x1 - xr)) % p;
  446.             xr = xr >= 0 ? xr : xr + p;
  447.             yr = yr >= 0 ? yr : yr + p;
  448.             answer.Add(xr);
  449.             answer.Add(yr);
  450.             return answer;
  451.         }
  452.  
  453.         static void Main(string[] args)
  454.         {
  455.             int m = 5;
  456.             BigInteger D = 1;
  457.             bool t = true;
  458.             Console.Write("Введите длину характеристики поля l = ");
  459.             int l = int.Parse(Console.ReadLine());
  460.             if (l <= 4)
  461.             {
  462.                 Console.WriteLine("Длина характеристики поля <= 4. Введите корректную длину!");
  463.                 return;
  464.             }
  465.            
  466.             while (true)
  467.             {
  468.                 step1: while (true)
  469.                 {
  470.                     t = true;
  471.                     List<BigInteger> decomposition;
  472.                     FindPrimeNumberOfLength(l);
  473.                     decomposition = Decomposition_P(D, p);
  474.  
  475.                     NR_ = NR_function(decomposition[0], decomposition[1], p);
  476.  
  477.                     if (!NR_.Any())
  478.                         goto step1;
  479.  
  480.                     if (p != NR_[1])
  481.                     {
  482.                         for (int i = 1; i <= m; i++)
  483.                         {
  484.                             if (BigInteger.ModPow(p, i, NR_[1]) == 0)
  485.                             {
  486.                                 w = w + 1;
  487.                                 if (w > 10)
  488.                                 {
  489.                                     Console.WriteLine("Нет p, удовлятворяющего всем условиям");
  490.                                     return;
  491.                                 }
  492.                                 goto step1;
  493.                             }
  494.                         }
  495.                         break;
  496.                     }
  497.                     goto step1;
  498.                 }
  499.             int j = 1, counter = 0;
  500.             BigInteger k = 2;
  501.             List<BigInteger> x0y0 = new List<BigInteger>();
  502.        
  503.             step5: while (true)
  504.             {
  505.                 if (NR_[0] == NR_[1] * 2)
  506.                     CheckA(ref t, ref k, 2);
  507.                
  508.                 else
  509.                     CheckA(ref t, ref k, 4);
  510.                
  511.                 if (!t)
  512.                     goto step6;
  513.                 x0y0 = new List<BigInteger>();
  514.                 for (int i = j; ; i++, j++)
  515.                 {
  516.                     BigInteger z = (A * i + i * i * i) % p;
  517.                     if (Legendre(z, p) == 1)
  518.                     {
  519.                         if (Sqrt_N(z) == 0)
  520.                             continue;
  521.                         else
  522.                         {
  523.                             x0y0.Add(i);
  524.                             x0y0.Add(Sqrt_N(z));
  525.                         }
  526.                         i++;
  527.                         j++;
  528.                         break;
  529.                     }
  530.                 }
  531.                 BigInteger cnt = NR_[0];
  532.                 List<BigInteger> mulp1p2 = new List<BigInteger>();
  533.                 while (cnt != 0)
  534.                 {
  535.                     if (!mulp1p2.Any())
  536.                         mulp1p2 = x0y0;
  537.                     else
  538.                         mulp1p2 = SumPoints(mulp1p2, x0y0, A, p);
  539.                     cnt--;
  540.                 }
  541.                 if (mulp1p2.Any())
  542.                 {
  543.                     if (counter++ < 10)
  544.                         goto step5;
  545.                     else
  546.                         goto step1;      
  547.                 }
  548.                 break;
  549.             }
  550.                
  551.             step6:  if (!t)
  552.                         continue;
  553.                 NR = NR_[0] / NR_[1];
  554.                 List<BigInteger> mulp1p2_new = new List<BigInteger>();
  555.                 List<BigInteger> Q = new List<BigInteger>();
  556.                 if (NR != 0)
  557.                 {
  558.                     while (NR != 0)
  559.                     {
  560.                         if (!mulp1p2_new.Any())
  561.                             mulp1p2_new = x0y0;
  562.                         else
  563.                             mulp1p2_new = SumPoints(mulp1p2_new, x0y0, A, p);
  564.                         NR--;
  565.                     }
  566.                     Q = mulp1p2_new;
  567.                 }      
  568.                 else
  569.                     Q = SumPoints(x0y0, x0y0, A, p);
  570.                 if (!Q.Any())
  571.                     continue;
  572.                
  573.                 WriteToFiles(Q);
  574.                 break;
  575.             }
  576.             Console.Read();
  577.         }
  578.         private static void WriteToFiles(List<BigInteger> Q)
  579.         {
  580.             List<BigInteger> mulp1p2_new;
  581.             Console.WriteLine("Результат:");
  582.             Console.WriteLine("p = " + p);
  583.             Console.WriteLine("A = " + A);
  584.             Console.WriteLine("r = " + NR_[1]);
  585.             Console.WriteLine("Q = (" + Q[0] + ", " + Q[1] + ")");
  586.             StreamWriter Out = null, Out1 = null;
  587.             try
  588.             {
  589.                 Out = new StreamWriter(File.Open("x.txt", FileMode.Create));
  590.                 Out1 = new StreamWriter(File.Open("y.txt", FileMode.Create));
  591.             }
  592.             catch (IOException e)
  593.             {
  594.                 Console.WriteLine(e.Message);
  595.             }
  596.             BigInteger count = NR_[1];
  597.             try
  598.             {
  599.                 Out.WriteLine(Q[0]);
  600.                 Out1.WriteLine(Q[1]);
  601.             }
  602.             catch (IOException e)
  603.             {
  604.                 Console.WriteLine(e.Message);
  605.             }
  606.             mulp1p2_new = SumPoints(Q, Q, A, p);
  607.             try
  608.             {
  609.                 Out.WriteLine(mulp1p2_new[0]);
  610.                 Out1.WriteLine(mulp1p2_new[1]);
  611.             }
  612.             catch (IOException e)
  613.             {
  614.                 Console.WriteLine(e.Message);
  615.             }
  616.             while (count != 3)
  617.             {
  618.                 if (!mulp1p2_new.Any())
  619.                 {
  620.                     mulp1p2_new = Q;
  621.                     try
  622.                     {
  623.                         Out.WriteLine(mulp1p2_new[0]);
  624.                         Out1.WriteLine(mulp1p2_new[1]);
  625.                     }
  626.                     catch (IOException e)
  627.                     {
  628.                         Console.WriteLine(e.Message);
  629.                     }
  630.                 }
  631.                 else
  632.                 {
  633.                     mulp1p2_new = SumPoints(mulp1p2_new, Q, A, p);
  634.                     try
  635.                     {
  636.                         Out.WriteLine(mulp1p2_new[0]);
  637.                         Out1.WriteLine(mulp1p2_new[1]);
  638.                     }
  639.                     catch (IOException e)
  640.                     {
  641.                         Console.WriteLine(e.Message);
  642.                     }
  643.                 }
  644.                 count--;
  645.             }
  646.             Out.Close();
  647.             Out1.Close();
  648.         }
  649.     }
  650. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!