API tools faq
paste
Advertisement
VNM24ix

LUI

VNM24ix
Jun 10th, 2025 (edited)
284
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 41.34 KB | Source Code | 0 0
raw download clone embed print report
  1. using System;
  2. using System.Linq;
  3. using System.Collections.Generic;
  4. using LUI;
  5. using System.Threading;
  6. using System.Data.Common;
  7.  
  8. namespace LUI;
  9. static class Prime {
  10.   public static uint[] p;
  11.   const int size = 20000;
  12.   static Prime() => P(size);
  13.   static void P(int n) {
  14.     p = new uint[n];
  15.     int cnt = 1;
  16.     p[0] = 2;
  17.     while (cnt < n) {
  18.       for (uint q = p[cnt - 1] + 1; ; q++) {
  19.         bool f = true;
  20.         for (int j = 0; j < cnt; j++)
  21.           if (p[j] * p[j] > q) break;
  22.           else if (q % p[j] == 0) { f = false; break; }
  23.         if (f) { p[cnt++] = q; break; }
  24.       }
  25.     }
  26.   }
  27.   public static LUI FindPrime(LUI n0, bool f = true) {
  28.     int m = Prime.p.Length;
  29.     uint[] r = new uint[m];
  30.     for (int i = 0; i < m; i++) {
  31.       //Console.Write(i + "  ");
  32.       LUI ρ = (n0 / p[i]).r;
  33.  
  34.       if (ρ.IsZero) r[i] = 0;
  35.       else r[i] = ρ.A[0];
  36.     }
  37.     //Console.WriteLine("Start\n");
  38.     //DateTime tm0 = DateTime.UtcNow;
  39.     for (uint d = 0; ; d++) {
  40.       bool ff = true;
  41.       for (int i = 1; i < m; i++) {
  42.         if ((r[i] + d * (f ? 1 : -1)) % Prime.p[i] == 0) { ff = false; break; }
  43.       }
  44.       if (ff) {
  45.         LUI n = f ? n0 + d : n0 - d;
  46.         if (n.FPTest(2)) {
  47.           //Console.WriteLine(DateTime.Now - tm0);
  48.           return n;
  49.         }
  50.         //else Console.WriteLine(d);
  51.       }
  52.     }
  53.   }
  54.   public static LUI FindSG(LUI n0, bool f = true) {
  55.     LUI n1 = n0 >> 1;
  56.     int cnt0 = 0, cnt1 = 0;
  57.     n1.SetBit(true, 0);
  58.     uint[] r = new uint[p.Length];
  59.     for (int i = 0; i < r.Length; i++) {
  60.       /*
  61.       LUI q = n1 % p[i];
  62.       r[i] = q.IsZero ? 0 : (n1 % p[i]).A[0];
  63.       */
  64.       r[i] = n1.RemDivShort(p[i]);
  65.     }
  66.     for (uint d = 0; ; d += 2) {
  67.       cnt0++;
  68.       bool ff = true;
  69.       for (int i = 0; i < p.Length; i++) {
  70.         uint r1 = (r[i] + d) % p[i];
  71.         ff &= r1 != 0;
  72.         if (ff) {
  73.           uint r2 = ((r[i] + d) * 2 + 1) % p[i];
  74.           ff &= r2 != 0;
  75.         }
  76.         if (!ff) break;
  77.       }
  78.       if (ff) {
  79.         Console.Clear();
  80.         Console.WriteLine("{0,10}{1,10}", cnt0, ++cnt1);
  81.       }
  82.  
  83.       if (ff) ff &= (n1 + d).FPTest(2);
  84.       if (ff) ff = ((n1 + d) * 2 + 1).FPTest(2);
  85.       if (ff) {
  86.         Console.Clear();
  87.         return (n1 + d) * 2 + 1;
  88.       }
  89.     }
  90.   }
  91. }
  92. static class Arr {
  93.   static Random rnd = new Random();
  94.   public static int NZ0(uint[] a) {
  95.     int res = a.Length;
  96.     for (int i = a.Length - 1; i >= 0; i--)
  97.       if (a[i] == 0) res--;
  98.       else break;
  99.     return res;
  100.   }
  101.   public static int NZ(uint[] a) {
  102.     int n = NZ0(a);
  103.     if (n == 0) return 0;
  104.     int res = n << 5;
  105.     for (uint m = (1u << 31); m > 0; m >>= 1)
  106.       if ((a[n - 1] & m) == 0) res--;
  107.       else break;
  108.     return res;
  109.   }
  110.   public static uint[] Copy(uint[] a, bool f = false) {
  111.     if (f) return Tr(a);
  112.     uint[] aa = new uint[a.Length];
  113.     a.CopyTo(aa, 0);
  114.     return aa;
  115.   }
  116.   public static uint[] Tr(uint[] a) {
  117.     uint[] aa = new uint[NZ0(a)];
  118.     for (int i = 0; i < aa.Length; i++)
  119.       aa[i] = a[i];
  120.     return aa;
  121.   }
  122.   public static uint[] ShL(uint[] a, int n) {
  123.     //Console.WriteLine("In ShL");
  124.     //ShowH(a, "A");
  125.     //Console.WriteLine("n = " + n);
  126.     int n0 = NZ(a) + n;
  127.     //Console.WriteLine("n0 = " + n0);
  128.     //int n0 = (a.Length << 5) + n;
  129.     // Console.WriteLine("n0 = " + n0);
  130.     int nn = ((n0 - 1) >> 5) + 1;
  131.     //Console.WriteLine("nn = " + nn);
  132.     if (nn < a.Length) nn = a.Length;
  133.     uint[] aa = new uint[nn];
  134.     //Console.WriteLine("nn = " + nn);
  135.     //a.CopyTo(aa, 0);
  136.     int m0 = n >> 5, m1 = n & 0x1f;
  137.     //Console.WriteLine("m0 = " + m0 + "  m1 = " + m1);
  138.     /*
  139.     if (m0 > 0)
  140.      
  141.         for (int i = a.Length - 1; i >= 0; i--) {
  142.           aa[i + m0] = aa[i]; aa[i] = 0;
  143.         }
  144.       */
  145.  
  146.     for (int i = NZ0(a) - 1; i >= 0; i--) {
  147.       aa[i + m0] = a[i];
  148.     }
  149.  
  150.     if (m1 > 0)
  151.       for (int i = aa.Length - 1; i >= 0; i--) {
  152.         ulong t = ((ulong)aa[i] << 32) | (i > 0 ? aa[i - 1] : 0);
  153.         aa[i] = (uint)((t << m1) >> 32);
  154.       }
  155.     //ShowH(aa, "Result of ShiftLeft");
  156.     return aa;
  157.   }
  158.   public static uint[] ShR(uint[] a, int n) {
  159.     int n0 = n >> 5, n1 = n & 0x1f;
  160.     uint[] aa = new uint[a.Length];
  161.     for (int i = 0; i < aa.Length; i++) {
  162.       int k = i - n0;
  163.       if (k >= 0) aa[k] = a[i];
  164.     }
  165.     if (n1 > 0)
  166.       for (int i = 0; i < aa.Length; i++) {
  167.         ulong x = ((ulong)(i < aa.Length - 1 ? aa[i + 1] : 0) << 32) | aa[i];
  168.         aa[i] = (uint)(x >> n1);
  169.       }
  170.     return aa;
  171.   }
  172.   public static bool GetBit(uint[] a, int n) {
  173.     int n0 = n >> 5, n1 = n & 0x1f;
  174.     return (a[n0] & (1u << n1)) > 0;
  175.   }
  176.   public static void SetBit(ref uint[] a, bool b, int n) {
  177.     int n0 = n >> 5, n1 = n & 0x1f;
  178.     if (b && n0 > a.Length - 1) {
  179.       uint[] aa = new uint[n0 + 1];
  180.       a.CopyTo(aa, 0);
  181.       a = aa;
  182.     }
  183.     a[n0] = b ? a[n0] | (1u << n1) : a[n0] & ~(1u << n1);
  184.   }
  185.   public static void SetLen(ref uint[] a, int n) {
  186.     uint[] aa = new uint[n];
  187.     if (n > a.Length)
  188.       a.CopyTo(aa, 0);
  189.     else
  190.       for (int i = 0; i < n; i++)
  191.         aa[i] = a[i];
  192.     a = aa;
  193.   }
  194.  
  195.   public static uint[] Add(uint[] a, uint[] b) {
  196.     int n = Math.Max(a.Length, b.Length);
  197.     uint[] res = new uint[n + 1];
  198.     uint c = 0;
  199.     for (int i = 0; i < res.Length; i++) {
  200.       ulong s = (ulong)c + (i < a.Length ? a[i] : 0) + (i < b.Length ? b[i] : 0);
  201.       res[i] = (uint)s;
  202.       c = (s > uint.MaxValue ? 1u : 0);
  203.     }
  204.     return res;
  205.   }
  206.   public static uint[] Sub(uint[] a, uint[] b) {
  207.     uint[] res = new uint[Math.Max(a.Length, b.Length)];
  208.     uint c = 0;
  209.     for (int i = 0; i < res.Length; i++) {
  210.       ulong x = (1ul << 32) + (i < a.Length ? a[i] : 0) -
  211.       (ulong)c - (i < b.Length ? b[i] : 0);
  212.       res[i] = (uint)x;
  213.       c = x > uint.MaxValue ? 0 : 1u;
  214.     }
  215.     return res;
  216.   }
  217.   public static int Cmp(uint[] a, uint[] b) {
  218.     uint[] aa = Tr(a), bb = Tr(b);
  219.     if (aa.Length != bb.Length)
  220.       return Math.Sign(aa.Length - bb.Length);
  221.     for (int i = aa.Length - 1; i >= 0; i--)
  222.       if (aa[i] < bb[i]) return -1;
  223.       else if (aa[i] > bb[i]) return 1;
  224.     return 0;
  225.   }
  226.   public static uint[] Mul(uint[] a, uint[] b) {
  227.     uint[] res = new uint[a.Length + b.Length];
  228.     for (int i = 0; i < NZ0(a); i++)
  229.       for (int j = 0; j < NZ0(b); j++) {
  230.         int k = i + j;
  231.         ulong x = (ulong)a[i] * b[j];
  232.         uint[] y = { (uint)x, (uint)(x >> 32) };
  233.         for (int t = 0; t < 2; t++) {
  234.           int kk = k + t;
  235.           while (y[t] > 0) {
  236.             ulong s = (ulong)res[kk] + y[t];
  237.             res[kk] = (uint)s;
  238.             y[t] = (s > uint.MaxValue ? 1u : 0);
  239.             kk++;
  240.           }
  241.         }
  242.       }
  243.     return res;
  244.   }
  245.   public static (uint[] q, uint[] r) Div(uint[] a, uint[] b) {
  246.     //Console.WriteLine("In Div");
  247.     //Arr.ShowH(a, "A");
  248.     //Arr.ShowH(b, "B");
  249.     //Console.ReadLine();
  250.     if (NZ0(b) == 0) return (null, null);
  251.     uint[] aa = Copy(a);
  252.     int k = NZ(b) - NZ(aa);
  253.     int n = k > 0 ? 0 : -k + 1;
  254.  
  255.  
  256.     //Console.WriteLine("n = " + n);
  257.     uint[] bb = ShL(b, n);
  258.     //ShowH(b, "B after shift");
  259.     //Console.ReadLine();
  260.     //Console.WriteLine("In Div");
  261.     uint[] q = { 0 };
  262.     while (true) {
  263.       q = ShL(q, 1);
  264.       if (Cmp(aa, bb) >= 0) {
  265.         aa = Sub(aa, bb);
  266.         q[0]++;
  267.       }
  268.       if (Cmp(bb, b) == 0) break;
  269.       else bb = ShR(bb, 1);
  270.     }
  271.     //ShowH(q, "Q");
  272.     return (q, aa);
  273.   }
  274.   public static (uint[] q, uint[] r) Div1(uint[] a, uint[] b) {
  275.     //Console.WriteLine("In Div1");
  276.     //ShowH(a, "A");
  277.     //ShowH(b, "B");
  278.     if (NZ0(b) == 0) return (null, null);
  279.     if (Cmp(a, b) == -1) return (new uint[0], Copy(a));
  280.     if (NZ0(a) < 3) {
  281.       ulong x = (a.Length == 2 ? (ulong)a[1] << 32 : 0) | a[0];
  282.       ulong y = (b.Length == 2 ? (ulong)b[1] << 32 : 0) | b[0];
  283.       ulong g = x / y, h = x % y;
  284.       return (new uint[] { (uint)g, (uint)(g >> 32) },
  285.       new uint[] { (uint)h, (uint)(h >> 32) });
  286.     }
  287.     int k0 = NZ(b) & 0x1f;
  288.     //int k0 = (32 - (NZ(b) & 0x1f)) & 0x1f;
  289.     if (k0 != 0) k0 = 32 - k0;
  290.     uint[] bb0 = ShL(b, k0);
  291.     uint[] aa = ShL(a, k0);
  292.     if (bb0.Length == 1) {
  293.       bb0 = ShL(bb0, 32);
  294.       aa = ShL(aa, 32);
  295.     }
  296.     int k1 = NZ0(aa) - NZ0(bb0);
  297.     if (k1 < 0) return (new uint[0], Copy(a));
  298.     uint[] bb = ShL(bb0, k1 << 5);
  299.     SetLen(ref aa, aa.Length + 1);
  300.     SetLen(ref bb, bb.Length + 1);
  301.     //ShowH(aa, "AA");
  302.     //ShowH(bb, "BB");
  303.     int l = aa.Length;
  304.     //ShowH(aa, "Aa");
  305.     //ShowH(bb, "Bb");
  306.     int p = aa.Length - 1;
  307.     uint[] q = new uint[0];
  308.     while (true) {
  309.       //Console.WriteLine("p=" + p);
  310.       uint[] u = { aa[p - 2], aa[p - 1], aa[p] };
  311.       uint[] v = { bb[p - 2], bb[p - 1], bb[p] };
  312.       //ShowH(u, "U");
  313.       //ShowH(v, "V");
  314.       uint[] w = Div(u, v).q;
  315.       //Console.WriteLine("Back in Div1");
  316.       //ShowH(w, "W0");
  317.  
  318.       uint[] bw = Mul(bb, w);
  319.       if (Cmp(aa, bw) == -1) {
  320.         w = Sub(w, new uint[] { 1 });
  321.         bw = Sub(bw, bb);
  322.       }
  323.       aa = Sub(aa, bw);
  324.       SetLen(ref aa, l);
  325.       //q = ShL(q, 32);
  326.       //q[0] = w[0];
  327.       q = Add(Mul(q, new uint[] { 0, 1 }), w);
  328.       if (Cmp(bb, bb0) == 1) {
  329.         bb = ShR(bb, 32);
  330.         //ShowH(aa, "Aa");
  331.         //ShowH(bb, "Bb");
  332.         p--;
  333.       } else break;
  334.     }
  335.     //Console.WriteLine("OK");
  336.     return (q, Sub(a, Mul(b, q)));
  337.   }
  338.   public static uint[] Rand(int n, int m = 0) {
  339.     uint[] a = new uint[n];
  340.     for (int i = 0; i < n * 8 - m; i++) {
  341.       a[i >> 3] |= (uint)rnd.Next(16) << (i & 7) * 4;
  342.     }
  343.     return a;
  344.   }
  345.   public static string StrH(uint[] a) {
  346.     string res = "";
  347.     for (int i = a.Length - 1; i >= 0; i--)
  348.       for (int j = 7; j >= 0; j--) {
  349.         int q = (int)(a[i] >> (j * 4)) & 0xf;
  350.         res += (char)(q < 10 ? (int)'0' + q : (int)'A' + (q - 10));
  351.       }
  352.     return res;
  353.   }
  354.   public static string StrD(uint[] a) {
  355.     if (NZ0(a) == 0) return "0";
  356.     uint[] aa = Copy(a);
  357.     uint[] b = { 1000000000 };
  358.     var l = new List<uint>();
  359.     while (NZ(aa) > 0) {
  360.       var x = Div(aa, b);
  361.       l.Add(x.r[0]);
  362.       aa = x.q;
  363.     }
  364.     string s = "";
  365.     for (int i = l.Count - 1; i >= 0; i--) {
  366.       string ss = l[i].ToString();
  367.       if (i < l.Count - 1) ss = new String('0', 9 - ss.Length) + ss;
  368.       s += ss;
  369.     }
  370.     return s;
  371.   }
  372.  
  373.   public static void ShowH(uint[] a, string name = "") {
  374.     if (name != "") Console.WriteLine(name + " =");
  375.     string s = StrH(a);
  376.     bool f = true;
  377.     for (int i = 0; i < s.Length; i++) {
  378.       if ((i & 3) == 0) f = !f;
  379.       Console.ForegroundColor = f ?
  380.       ConsoleColor.Yellow : ConsoleColor.Cyan;
  381.       Console.Write(s[i]);
  382.     }
  383.     Console.ForegroundColor = ConsoleColor.White;
  384.     Console.WriteLine("\n");
  385.   }
  386.   public static void ShowD(uint[] a, string name = "") {
  387.     if (name != "")
  388.       Console.WriteLine(name + " =");
  389.     Console.WriteLine(StrD(a) + "\n");
  390.   }
  391. }
  392. class LUI {
  393.   uint[] a;
  394.   public uint[] A => Arr.Copy(a);
  395.   public int N => a.Length;
  396.   public LUI(uint[] a) {
  397.     this.a = Arr.Tr(a);
  398.   }
  399.   public LUI Copy => new LUI(a);
  400.   public static LUI Rand(int size, int m = 0) => new LUI(Arr.Rand(size, m));
  401.   public static LUI Rand1(int size) {
  402.     LUI x = Rand(size);
  403.     x.SetBit(true, (size << 5) - 1);
  404.     return x;
  405.   }
  406.   public int NZ => Arr.NZ(a);
  407.   public static implicit operator LUI(ulong n) =>
  408.       new LUI(new uint[] { (uint)n, (uint)(n >> 32) });
  409.   public bool IsZero => N == 0;
  410.   public bool Eq(LUI x) => Arr.Cmp(a, x.a) == 0;
  411.   public bool NEq(LUI x) => !Eq(x);
  412.   public static bool operator >(LUI x, LUI y) =>
  413.   Arr.Cmp(x.a, y.a) == 1;
  414.   public static bool operator <(LUI x, LUI y) =>
  415.   Arr.Cmp(x.a, y.a) == -1;
  416.   public static bool operator >=(LUI x, LUI y) => !(x < y);
  417.   public static bool operator <=(LUI x, LUI y) => !(x > y);
  418.   public static LUI operator +(LUI x, LUI y) => new LUI(Arr.Add(x.a, y.a));
  419.   public static LUI operator -(LUI x, LUI y) => new LUI(Arr.Sub(x.a, y.a));
  420.   public static LUI operator *(LUI x, LUI y) => new LUI(Arr.Mul(x.a, y.a));
  421.   public static LUI operator <<(LUI x, int n) {
  422.     uint[] a = Arr.ShL(x.A, n);
  423.     return new LUI(a);
  424.   }
  425.   public static LUI operator >>(LUI x, int n) {
  426.     uint[] a = Arr.ShR(x.A, n);
  427.     return new LUI(a);
  428.   }
  429.   public static (LUI q, LUI r) operator /(LUI x, LUI y) {
  430.     var v = Arr.Div1(x.a, y.a);
  431.     return (new LUI(v.q), new LUI(v.r));
  432.   }
  433.   public static LUI operator %(LUI x, LUI y) => (x / y).r;
  434.   public uint RemDivShort(uint n) {
  435.     uint[] x = new uint[N];
  436.     x[0] = 1u % n;
  437.     for (int i = 1; i < N; i++)
  438.       x[i] = (uint)(((ulong)0x100000000 * x[i - 1]) % n);
  439.     ulong s = 0;
  440.     for (int i = 0; i < N; i++)
  441.       s += ((ulong)a[i] * x[i]) % n;
  442.     return (uint)(s % n);
  443.   }
  444.   public bool GetBit(int n) => Arr.GetBit(a, n);
  445.  
  446.   public void SetBit(bool b, int n) {
  447.     Arr.SetBit(ref a, b, n);
  448.     a = Arr.Tr(a);
  449.   }
  450.  
  451.   public LUI Pow(int n) {
  452.     if (n == 0) return 1;
  453.     else if (n == 1) return Copy;
  454.     LUI x = Pow(n / 2), y = x * x;
  455.     return (n % 2 == 1 ? y * this : y);
  456.   }
  457.   public LUI ExpMod(LUI exp, LUI mod) {
  458.     int n = exp.NZ;
  459.     LUI res = 1;
  460.     for (int i = n - 1; i >= 0; i--) {
  461.       res = ((res * res) / mod).r;
  462.       if (Arr.GetBit(exp.a, i))
  463.         res = ((res * this) / mod).r;
  464.     }
  465.     return res;
  466.   }
  467.   public bool FPTest(uint b) =>
  468.   ((LUI)b).ExpMod(this - 1, this).Eq(1);
  469.   public static LUI GCD(LUI p, LUI q) {
  470.     if (p.IsZero && q.IsZero) return null;
  471.     else if (p.IsZero) return q.Copy;
  472.     else if (q.IsZero) return p.Copy;
  473.     else return GCD(q, (p / q).r);
  474.   }
  475.   public bool CoPrime(LUI n) => GCD(this, n).Eq(1);
  476.  
  477.   public LUI InvMod(LUI mod) {
  478.     if (!CoPrime(mod)) return null;
  479.     var list = new List<LUI>();
  480.     LUI p = Copy, q = mod.Copy;
  481.     while (!q.IsZero) {
  482.       var x = p / q;
  483.       list.Add(x.q);
  484.       p = q.Copy;
  485.       q = x.r;
  486.     }
  487.     int k = list.Count & 1;
  488.     p = 1; q = 0;
  489.     list[list.Count - 1] -= 1;
  490.     for (int i = list.Count - 2 + k; i >= 0; i--) {
  491.       LUI t = list[i] * p + q;
  492.       q = p.Copy;
  493.       p = t;
  494.     }
  495.     return q;
  496.   }
  497.  
  498.   public void ShowH(string name = "") =>
  499.   Arr.ShowH(a, name);
  500.   public string StrD => Arr.StrD(A);
  501.   public void ShowD(string name = "") =>
  502.   Arr.ShowD(a, name);
  503.   public static implicit operator LUI(string txt) {
  504.     string txt1 = "";
  505.     for (int i = 0; i < txt.Length; i++)
  506.       if (Char.IsDigit(txt[i])) txt1 += txt[i];
  507.     txt = txt1;
  508.     int k = 0;
  509.     for (int i = 0; i < txt.Length; i++)
  510.       if (txt[i] != '0') break; else k++;
  511.     txt = txt.Substring(k, txt.Length - k);
  512.     if (txt == "") return 0;
  513.     int r = txt.Length % 9;
  514.     //Console.WriteLine("r = " + r);
  515.     string[] s = new string[txt.Length / 9 + (r > 0 ? 1 : 0)];
  516.     s[0] = txt.Substring(0, r > 0 ? r : 9);
  517.     //Console.WriteLine(s[0]);
  518.     if (txt.Length > s[0].Length) {
  519.       txt1 = txt.Substring(s[0].Length, txt.Length - s[0].Length);
  520.       for (int i = 1; i < s.Length; i++) {
  521.         s[i] = txt1.Substring((i - 1) * 9, 9);
  522.         //Console.WriteLine(s[i]);
  523.       }
  524.     }
  525.     LUI res = 0;
  526.     for (int i = 0; i < s.Length; i++) {
  527.       res *= 1000000000u;
  528.       res += uint.Parse(s[i]);
  529.     }
  530.     return res;
  531.   }
  532. }
  533. static class RSA {
  534.   public static (LUI p, LUI q, LUI n, LUI φ, LUI e, LUI d) PQ(int size, bool sg = false) {
  535.     LUI n0 = LUI.Rand(size);
  536.     n0.SetBit(true, (size << 5) - 1);
  537.     LUI r;
  538.     if ((size & 1) == 1) {
  539.       r = LUI.Rand((size + 1) / 2, 4);
  540.     } else r = LUI.Rand(size / 2);
  541.     r.SetBit(true, (r.N << 5) - 1);
  542.     LUI p = sg ? Prime.FindSG(r) : Prime.FindPrime(r);
  543.     //Console.Beep(400, 2000);
  544.     LUI q = sg ? Prime.FindSG((n0 / p).q) :
  545.     Prime.FindPrime((n0 / p).q);
  546.     //Console.Beep(800, 2000);
  547.     LUI n = p * q;
  548.     LUI φ = (p - 1) * (q - 1);
  549.     LUI e = Prime.FindPrime(LUI.Rand(1) + ((LUI)1u << 32));
  550.     while (!e.CoPrime(φ)) e += 2;
  551.     LUI d = e.InvMod(φ);
  552.     return (p, q, n, φ, e, d);
  553.   }
  554.   public static void Show(int size, bool hex, bool dcm, bool sg = false) {
  555.     var v1 = PQ(size, sg);
  556.     var v2 = PQ(size, sg);
  557.     if (hex) {
  558.       v1.p.ShowH("P1");
  559.       v1.q.ShowH("Q1");
  560.       v1.n.ShowH("N1 = P1·Q1");
  561.       v1.φ.ShowH("φ(N1) = (P1–1)(Q1–1)");
  562.       v1.e.ShowH("E1");
  563.       v1.d.ShowH("D1 = E1^–1 (mod φ(N1))");
  564.       v2.p.ShowH("P2");
  565.       v2.q.ShowH("Q2");
  566.       v2.n.ShowH("N2 = P2·Q2");
  567.       v2.φ.ShowH("φ(N2) = (P2–1)(Q2–1)");
  568.       v2.e.ShowH("E2");
  569.       v2.d.ShowH("D2 = E2^–1 (mod φ(N2))");
  570.     }
  571.     if (dcm) {
  572.       v1.p.ShowD("P1");
  573.       v1.q.ShowD("Q1");
  574.       v1.n.ShowD("N1 = P1·Q1");
  575.       v1.φ.ShowD("φ(N1) = (P1–1)(Q1–1)");
  576.       v1.e.ShowD("E1");
  577.       v1.d.ShowD("D1 = E1^–1 (mod φ(N1))");
  578.       v2.p.ShowD("P2");
  579.       v2.q.ShowD("Q2");
  580.       v2.n.ShowD("N2 = P2·Q2");
  581.       v2.φ.ShowD("φ(N2) = (P2–1)(Q2–1)");
  582.       v2.e.ShowD("E2");
  583.       v2.d.ShowD("D2 = E2^–1 (mod φ(N2))");
  584.     }
  585.     bool f = v1.n < v2.n;
  586.     LUI t0 = LUI.Rand(size) % (f ? v1.n : v2.n);
  587.     LUI t1 = t0.ExpMod(f ? v1.d : v2.e, f ? v1.n : v2.n);
  588.     string s1 = "T1 = T0^" + (f ? "D1" : "E2") + " mod N" + (f ? "1" : "2");
  589.     LUI t2 = t1.ExpMod(f ? v2.e : v1.d, f ? v2.n : v1.n);
  590.     string s2 = "T2 = T1^" + (f ? "E2" : "D1") + " mod N" + (f ? "2" : "1");
  591.     LUI t3 = t2.ExpMod(f ? v2.d : v1.e, f ? v2.n : v1.n);
  592.     string s3 = "T3 = T2^" + (f ? "D2" : "E1") + " mod N" + (f ? "2" : "1");
  593.     LUI t4 = t3.ExpMod(f ? v1.e : v2.d, f ? v1.n : v2.n);
  594.     string s4 = "T4 = T3^" + (f ? "E1" : "D2") + " mod N" + (f ? "1" : "2");
  595.     if (hex) {
  596.       t0.ShowH("T0");
  597.       t1.ShowH(s1);
  598.       t2.ShowH(s2);
  599.       t3.ShowH(s3);
  600.       t4.ShowH(s4);
  601.     }
  602.     if (dcm) {
  603.       t0.ShowD("T0");
  604.       t1.ShowD(s1);
  605.       t2.ShowD(s2);
  606.       t3.ShowD(s3);
  607.       t4.ShowD(s4);
  608.     }
  609.  
  610.   }
  611. }
  612.  
  613. static class ElGamal {
  614.   public static (LUI p, LUI g, LUI x, LUI gx, LUI y, LUI gy, LUI gxy, LUI gyx) Gen(int size) {
  615.     LUI p = Prime.FindSG(LUI.Rand1(size));
  616.     LUI g;
  617.     for (g = 2; ; g += 1) {
  618.       if (!g.ExpMod((p - 1) >> 1, p).Eq(1)) break;
  619.     }
  620.     LUI x;
  621.     x = LUI.Rand(size) % p;
  622.     LUI gx = g.ExpMod(x, p);
  623.     LUI y;
  624.     y = LUI.Rand(size) % p;
  625.     LUI gy = g.ExpMod(y, p);
  626.     LUI gxy = gx.ExpMod(y, p);
  627.     LUI gyx = gy.ExpMod(x, p);
  628.     return (p, g, x, gx, y, gy, gxy, gyx);
  629.   }
  630.   /*
  631.   public static (LUI r, LUI s) DSign(LUI p, LUI g, LUI y) {
  632.     LUI k = LUI.Rand(p.N);
  633.     while (!(p - 1).CoPrime(k)) k += 1;
  634.     LUI r=g.ExpMod()
  635.   }
  636.   */
  637. }
  638. class Ration {
  639.   LUI nom, den;
  640.   public LUI Nom => nom.Copy;
  641.   public LUI Den => den.Copy;
  642.   int sign;
  643.   public int Sign => sign;
  644.   public Ration(LUI nom, LUI den, int sign) {
  645.     if (nom.IsZero || sign == 0) {
  646.       this.nom = 0; this.den = 1; this.sign = 0;
  647.     } else {
  648.       LUI gcd = LUI.GCD(nom, den);
  649.       this.nom = (nom / gcd).q;
  650.       this.den = (den / gcd).q;
  651.       this.sign = sign;
  652.     }
  653.   }
  654.   public Ration(LUI x, int s) :
  655.   this(x, 1, s) { }
  656.   public Ration(long x, ulong y) :
  657.   this((LUI)(ulong)Math.Abs(x), (LUI)y, Math.Sign(x)) { }
  658.   public static implicit operator Ration(long x) => new Ration((ulong)Math.Abs(x), 1, Math.Sign(x));
  659.  
  660.   public Ration Copy =>
  661.   new Ration(nom, den, sign);
  662.   public bool IsZero => sign == 0;
  663.   public bool IsInt => den.Eq(1);
  664.   //public Ration Zero => new Ration(0, 0);
  665.   public static Ration operator -(Ration x) =>
  666.   new Ration(x.nom, x.den, -x.sign);
  667.   public static Ration operator +(Ration x, Ration y) {
  668.     //Console.WriteLine("In +");
  669.     //Console.WriteLine(x.sign + "  " + y.sign);
  670.     if (x.sign == 0) return y.Copy;
  671.     else if (y.sign == 0) return x.Copy;
  672.     else {
  673.       //Console.WriteLine("!?!");
  674.       LUI u1 = x.nom * y.den;
  675.       LUI u2 = x.den * y.nom;
  676.       LUI nom, den;
  677.       int sign;
  678.       if (x.sign == y.sign) {
  679.         nom = u1 + u2;
  680.         //nom.ShowD("Nom1");
  681.         sign = x.sign;
  682.       } else {
  683.         int s = Arr.Cmp(u1.A, u2.A);
  684.         if (s == 0) return 0;
  685.         else {
  686.           nom = s == 1 ? u1 - u2 : u2 - u1;
  687.           //nom.ShowD("Nom2");
  688.           sign = x.sign * s;
  689.         }
  690.       }
  691.       den = x.den * y.den;
  692.       return new Ration(nom, den, sign);
  693.     }
  694.   }
  695.   public static Ration operator -(Ration x, Ration y) => x + -y;
  696.   public static Ration operator *(Ration x, Ration y) =>
  697.   x.sign * y.sign == 0 ? 0 : new Ration(x.nom * y.nom, x.den * y.den, x.sign * y.sign);
  698.   public static Ration operator /(Ration x, Ration y)
  699.   => y.sign == 0 ? null : x * new Ration(y.den, y.nom, y.sign);
  700.   public bool Eq(Ration x) =>
  701.   nom.Eq(x.nom) && den.Eq(x.den) && sign == x.sign;
  702.   public bool NEq(Ration x) => !Eq(x);
  703.   public static bool operator >(Ration x, Ration y) => (x - y).sign == 1;
  704.   public static bool operator <(Ration x, Ration y) => y > x;
  705.   public string Str() {
  706.     return (sign >= 0 ? "" : "–") + nom.StrD + (den.NEq(1) ? " / " + den.StrD : "");
  707.   }
  708.   public void Show(string name) {
  709.     if (name != "") {
  710.       Console.ForegroundColor = ConsoleColor.White;
  711.       Console.Write(name + " = ");
  712.     }
  713.     Console.ForegroundColor = ConsoleColor.Yellow;
  714.     Console.Write(nom.StrD);
  715.     if (!IsInt) {
  716.       Console.ForegroundColor = ConsoleColor.White;
  717.       Console.Write("/");
  718.       Console.ForegroundColor = ConsoleColor.Cyan;
  719.       Console.WriteLine(den.StrD + "\n");
  720.     }
  721.     Console.ForegroundColor = ConsoleColor.White;
  722.   }
  723.   public static Ration[] SolveLinEq(Ration[,] m) {
  724.     int n = m.GetLength(0), nn = n + 1;
  725.     Ration[,] mm = new Ration[n, nn];
  726.     for (int i = 0; i < n; i++)
  727.       for (int j = 0; j < nn; j++)
  728.         mm[i, j] = m[i, j].Copy;
  729.     for (int i = 0; i < n; i++) {
  730.       if (mm[i, i].IsZero) {
  731.         int ii = i;
  732.         for (int j = i + 1; j < n; j++)
  733.           if (!mm[j, i].IsZero) { ii = j; break; }
  734.         if (ii == i) return null;
  735.         for (int j = i; j < nn; j++) {
  736.           Ration tmp = mm[i, j].Copy; mm[i, j] = mm[ii, j].Copy; mm[ii, j] = tmp;
  737.         }
  738.       }
  739.       Ration mii = mm[i, i].Copy;
  740.       for (int j = i; j < nn; j++) mm[i, j] /= mii;
  741.       for (int j = 0; j < n; j++)
  742.         if (i != j) {
  743.           Ration mji = mm[j, i].Copy;
  744.           for (int k = i; k < nn; k++)
  745.             mm[j, k] -= mm[i, k] * mji;
  746.         }
  747.     }
  748.     Ration[] res = new Ration[n];
  749.     for (int i = 0; i < n; i++) res[i] = mm[i, n];
  750.     return res;
  751.   }
  752.   public string FltVal(int n) {
  753.     if (IsZero) return "0";
  754.     var x = nom / den;
  755.     var q = x.q;
  756.     var r = x.r;
  757.     bool f = q > 0;
  758.     string resI = Arr.StrD(q.A) + ".";
  759.     int cnt = f ? resI.Length : 0;
  760.     string resF = "";
  761.     while (cnt < n) {
  762.       x = (r * 10) / den;
  763.       if (!x.q.IsZero) f = true;
  764.       resF += Arr.StrD(x.q.A);
  765.       if (f) cnt++;
  766.       r = x.r;
  767.     }
  768.     return sign == -1 ? "-" : " " + resI + resF;
  769.   }
  770.   public void ShowFltVal(string name, int n) {
  771.     if (name != "") Console.Write(name + " =");
  772.     Console.WriteLine(FltVal(n) + "\n");
  773.   }
  774. }
  775.  
  776. class Z {
  777.   public Ration[] a;
  778.   public Z(Ration[] a) {
  779.     this.a = new Ration[30];
  780.     for (int i = 0; i < 30; i++)
  781.       this.a[i] = a[i].Copy;
  782.   }
  783.   public static Z Z1() {
  784.     Ration[] a = new Ration[30];
  785.     for (int i = 0; i < 30; i++) a[i] = 0;
  786.     a[N(1, 0, 0)] = 1;
  787.     a[N(0, 1, 0)] = 1;
  788.     a[N(0, 0, 1)] = 1;
  789.     return new Z(a);
  790.   }
  791.   public static int N(int r2, int r3, int r5) =>
  792.   (15 * r2 + 10 * r3 + 6 * r5) % 30;
  793.   public static (int r2, int r3, int r5) R(int n) =>
  794.   (n % 2, n % 3, n % 5);
  795.   public static Z operator +(Z x, Z y) {
  796.     Ration[] a = new Ration[30];
  797.     for (int i = 0; i < 30; i++)
  798.       a[i] = x.a[i] + y.a[i];
  799.     return new Z(a);
  800.   }
  801.  
  802.   public static Z operator *(Z x, Z y) {
  803.     Ration[] a = new Ration[30];
  804.     for (int i = 0; i < 30; i++) a[i] = 0;
  805.     for (int i = 0; i < 30; i++)
  806.       for (int j = 0; j < 30; j++) {
  807.         Ration t = x.a[i] * y.a[j];
  808.         var rx = R(i);
  809.         var ry = R(j);
  810.         int r2 = rx.r2 + ry.r2;
  811.         if (r2 >= 2) { t *= 2; r2 -= 2; }
  812.         int r3 = rx.r3 + ry.r3;
  813.         if (r3 >= 3) { t *= 3; r3 -= 3; }
  814.         int r5 = rx.r5 + ry.r5;
  815.         if (r5 >= 5) { t *= 5; r5 -= 5; }
  816.         int n = N(r2, r3, r5);
  817.         a[n] += t;
  818.       }
  819.     return new Z(a);
  820.   }
  821.   public static Z Pow(int n) {
  822.     if (n == 0) {
  823.       Ration[] a = new Ration[30];
  824.       for (int i = 0; i < 30; i++)
  825.         a[i] = i == 0 ? 1 : 0;
  826.       return new Z(a);
  827.     } else if (n == 1) return Z1();
  828.     else if (n == 1) return Z1();
  829.     else {
  830.       int m = n >> 1;
  831.       Z z = Pow(m);
  832.       z *= z;
  833.       if ((n & 1) == 1) z *= Z1();
  834.       return z;
  835.     }
  836.   }
  837.   public void Show() {
  838.     for (int i = 0; i < 30; i++) {
  839.       Console.ForegroundColor = ConsoleColor.Yellow;
  840.       Console.Write("(" + a[i].Str() + ")");
  841.       Console.ForegroundColor = ConsoleColor.Cyan;
  842.       Console.Write("(" + R(i).r2 + "," + R(i).r3 + "," + R(i).r5 + ")");
  843.       Console.ForegroundColor = ConsoleColor.White;
  844.       Console.Write(i < 29 ? " + " : "\n\n");
  845.     }
  846.   }
  847. }
  848.  
  849. public static class Program {
  850.   static Random rnd = new Random();
  851.   public static void Main() {
  852.     int size = 32;
  853.     {
  854.       Ration a = 2, b = 1;
  855.       for (int i = 0; i < 7; i++) {
  856.         b = (a / b + b) / 2;
  857.       }
  858.       Ration aa = b * b;
  859.       aa.ShowFltVal("B²", 100);
  860.       return;
  861.     }
  862.     {
  863.       int S(int[] a) {
  864.         int s = 0;
  865.         for (int i = 0; i < a.Length; i++)
  866.           s += a[i];
  867.         return s;
  868.       }
  869.       Ration P2(int[] n, int[] q) {
  870.         int s = S(n), sq0 = S(q);
  871.         int sq = 0;
  872.         for (int i = 0; i < n.Length; i++) {
  873.           sq += q[i];
  874.           if (q[i] == 1 && n[i] == 1)
  875.             if (i > 0) return 0;
  876.             else if (sq == sq0) return (Ration)n[0] / s;
  877.             else return 0;
  878.         }
  879.         Ration p = 1;
  880.         int ss = s;
  881.         var nn = new int[n.Length];
  882.         for (int i = 0; i < n.Length; i++) {
  883.           nn[i] = n[i];
  884.           if (q[i] == 0) p *= (Ration)(ss - n[i]) / ss;
  885.           else {
  886.             p *= (Ration)n[i] / ss;
  887.             ss--;
  888.             nn[i]--;
  889.           }
  890.         }
  891.         return p * P1(nn);
  892.       }
  893.       Ration P1(int[] n) {
  894.         int s = S(n);
  895.         Ration a = 1;
  896.         for (int i = 0; i < n.Length; i++)
  897.           a *= (Ration)(s - n[i]) / s;
  898.         int m = 1 << n.Length;
  899.         Ration p = 0;
  900.         for (int i = 1; i < m; i++) {
  901.           var q = new int[n.Length];
  902.           for (int j = 0; j < n.Length; j++)
  903.             q[j] = (i >> j) & 1;
  904.           p += P2(n, q);
  905.         }
  906.         return p / (1 - a);
  907.       }
  908.       Ration P(int k, int[] n) {
  909.         int[] rot(int[] a, int t) {
  910.           var r = new int[a.Length];
  911.           for (int i = 0; i < a.Length; i++) {
  912.             int j = (i + t) % a.Length;
  913.             r[i] = a[j];
  914.           }
  915.           return r;
  916.         }
  917.         //if (k == 0) return P(n);
  918.         int m = 1 << k;
  919.         Ration p = 0;
  920.         for (int i = 0; i < m; i++) {
  921.           var q = new int[k];
  922.           for (int j = 0; j < k; j++)
  923.             q[j] = (i >> j) & 1;
  924.           Ration pp = 1;
  925.           int s = S(n);
  926.           var nn = new int[n.Length];
  927.           n.CopyTo(nn, 0);
  928.           for (int j = 0; j < k; j++) {
  929.             if (q[j] == 1) {
  930.               if (nn[j] == 1) {
  931.                 pp = 0;
  932.                 break;
  933.               } else {
  934.                 pp *= (Ration)nn[j] / s;
  935.                 nn[j]--;
  936.                 s--;
  937.               }
  938.             } else {
  939.               pp *= (Ration)(s - nn[j]) / s;
  940.             }
  941.           }
  942.           if (pp > 0) pp *= P1(rot(nn, k));
  943.           p += pp;
  944.         }
  945.         return p;
  946.       }
  947.       int[] n = { 4, 3, 2 };
  948.       Ration Σp = 0;
  949.       for (int i = 0; i < n.Length; i++) {
  950.         var p = P(i, n);
  951.         p.Show("P" + (i + 1));
  952.         p.ShowFltVal("P" + (i + 1), 25);
  953.         Σp += p;
  954.       }
  955.       Σp.Show("Σp");
  956.  
  957.       return;
  958.       /*
  959.       Ration P(Ration k, Ration l, Ration m) {
  960.         Ration s = k + l + m;
  961.         if (k > 1 && l > 1 && m > 1) {
  962.           //---
  963.           var a = (s - k) / s * (s - l) / s * (s - m) / s;
  964.           //--+
  965.           var b = (s - k) / s * (s - l) / s * m / s;
  966.           //-+-
  967.           var c = (s - k) / s * l / s * (s - 1 - m) / (s - 1);
  968.           //-++
  969.           var d = (s - k) / s * l / s * m / (s - 1);
  970.           //+--
  971.           var e = k / s * (s - 1 - l) / (s - 1) * (s - 1 - m) / (s - 1);
  972.           //+-+
  973.           var f = k / s * (s - 1 - l) / (s - 1) * m / (s - 1);
  974.           //++-
  975.           var g = k / s * l / (s - 1) * (s - 2 - m) / (s - 2);
  976.           //+++
  977.           var h = k / s * l / (s - 1) * m / (s - 2);
  978.           return (b * P(k, l, m - 1) + c * P(k, l - 1, m) + d * P(k, l - 1, m - 1) + e * P(k - 1, l, m) + f * P(k - 1, l, m - 1) + g * P(k - 1, l - 1, m) + h * P(k - 1, l - 1, m - 1)) / (1 - a);
  979.         } else if (k > 1 && l > 1 && m.Eq(1)) {
  980.           //---
  981.           var a = (s - k) / s * (s - l) / s * (s - m) / s;
  982.           //-+-
  983.           var b = (s - k) / s * l / s * (s - 1 - m) / (s - 1);
  984.           //+--
  985.           var c = k / s * (s - 1 - l) / (s - 1) * (s - 1 - m) / (s - 1);
  986.           //++-
  987.           var d = k / s * l / (s - 1) * (s - 2 - m) / (s - 2);
  988.           return (b * P(k, l - 1, m) + c * P(k - 1, l, m) + d * P(k - 1, l - 1, m)) / (1 - a);
  989.         } else if (k > 1 && l.Eq(1) && m > 1) {
  990.           //---
  991.           var a = (s - k) / s * (s - l) / s * (s - m) / s;
  992.           //--+
  993.           var b = (s - k) / s * (s - l) / s * m / s;
  994.           //+--
  995.           var c = k / s * (s - 1 - l) / (s - 1) * (s - 1 - m) / (s - 1);
  996.           //+-+
  997.           var d = k / s * (s - 1 - l) / (s - 1) * m / (s - 1);
  998.           return (b * P(k, l, m - 1) + c * P(k - 1, l, m) + d * P(k - 1, l, m - 1)) / (1 - a);
  999.         } else if (k.Eq(1) && l > 1 && m > 1) {
  1000.           //---
  1001.           var a = (s - k) / s * (s - l) / s * (s - m) / s;
  1002.           //--+
  1003.           var b = (s - k) / s * (s - l) / s * m / s;
  1004.           //-+-
  1005.           var c = (s - k) / s * l / s * (s - 1 - m) / (s - 1);
  1006.           //-++
  1007.           var d = (s - k) / s * l / s * m / (s - 1);
  1008.           return (k / s + b * P(k, l, m - 1) + c * P(k, l - 1, m) + d * P(k, l - 1, m - 1)) / (1 - a);
  1009.         } else if (k > 1 && l.Eq(1) && m.Eq(1)) {
  1010.           //---
  1011.           var a = (s - k) / s * (s - l) / s * (s - m) / s;
  1012.           //+--
  1013.           var b = k / s * (s - 1 - l) / (s - 1) * (s - 1 - m) / (s - 1);
  1014.           return (b * P(k - 1, l, m)) / (1 - a);
  1015.         } else if (k.Eq(1) && l > 1 && m.Eq(1)) {
  1016.           //---
  1017.           var a = (s - k) / s * (s - l) / s * (s - m) / s;
  1018.           //-+-
  1019.           var b = (s - k) / s * l / s * (s - 1 - m) / (s - 1);
  1020.           return (k / s + b * P(k, l - 1, m)) / (1 - a);
  1021.         } else if (k.Eq(1) && l.Eq(1) && m > 1) {
  1022.           //---
  1023.           var a = (s - k) / s * (s - l) / s * (s - m) / s;
  1024.           //--+
  1025.           var b = (s - k) / s * (s - l) / s * m / s;
  1026.           return (k / s + b * P(k, l, m - 1)) / (1 - a);
  1027.         } else {
  1028.           //---
  1029.           var a = (s - k) / s * (s - l) / s * (s - m) / s;
  1030.           return (k / s) / (1 - a);
  1031.         }
  1032.       }
  1033.       */
  1034.  
  1035.       //Console.WriteLine();
  1036.       //return;
  1037.       /*
  1038.             var p1 = P(4, 3, 2);
  1039.             Console.WriteLine(p1.Str() + "\n");
  1040.             var p2 = new Ration(4l, 9ul) * P(3, 2, 3) + new Ration(5l, 9ul) * P(3, 2, 4);
  1041.             Console.WriteLine(p2.Str() + "\n");
  1042.             var p3 = new Ration(4l, 9ul) * new Ration(3l, 8ul) * P(2, 3, 2) +
  1043.             new Ration(4l, 9ul) * new Ration(5l, 8ul) * P(2, 3, 3) + new Ration(5l, 9ul) * new Ration(3l, 9ul) * P(2, 4, 2) + new Ration(5l, 9ul) * new Ration(6l, 9ul) * P(2, 4, 3);
  1044.             Console.WriteLine(p3.Str() + "\n");
  1045.             Console.WriteLine((p1 + p2 + p3).Str() + "\n");
  1046.       */
  1047.       /*
  1048.       Ration k = 3, l = 4, m = 2, s = k + l + m;
  1049.       var p1 = P(k, l, m);
  1050.       p1.Show("P1");
  1051.       //Console.WriteLine(p1.Str() + "\n");
  1052.       var p2 =
  1053.        k / s * P(l, m, k - 1) +
  1054.       (s - k) / s * P(l, m, k);
  1055.       //Console.WriteLine(p2.Str() + "\n");
  1056.       p2.Show("P2");
  1057.       var p3 = k / s * l / (s - 1) * P(m, k - 1, l - 1) +
  1058.                k / s * (s - 1 - l) / (s - 1) * P(m, k - 1, l) +
  1059.                (s - k) / s * l / s * P(m, k, l - 1) +
  1060.                (s - k) / s * (s - l) / s * P(m, k, l);
  1061.       //Console.WriteLine(p3.Str() + "\n");
  1062.       p3.Show("P3");
  1063.       (p1 + p2 + p3).Show("P1 + P2 + P3");
  1064.       */
  1065.       return;
  1066.     }
  1067.  
  1068.     {
  1069.       //LUI p1 = "1042443771311239633413205559326281210808060675878177002445634643591787689255192449796971282493551506892638138246800852540130494467352800688977650758697725679057410608054679794944955023867278505654593907586461765174195228214914586283";
  1070.       //LUI p2 = "1215176752081434429245853189413984239769716343499290505892032427840248218030044596422573401149369786373776119185083811857169350074501076678373604084439000481696072429776618119456786683625872330685900209835383874974229742808167679907";
  1071.       //LUI p3 = "1115732040768242855356230620181871041901862061825902139505347985716338360539850494431733227529267279429978220744469165682423357430236501837432982915342647295526566114519526262803233363192058309682422079373409086020434213365704651547";
  1072.       LUI p = "104877538395683983366410382169067664128088998324969954776913609710709979673872106181302424272451630465255903890993699866432944529691302121829280875212192060249409981488097721928049610630033097449915456635611191146165881248842161083160683443076013973067893398700983745781152640174308826993566956033515645669283";
  1073.       LUI q = "133555787139965542016652020299042388774493285356924243918801203066549237266540858298157432621828743072406798037259250876162616325748283692572042900004902260407064923767113776920105687530531338672948803242326218839058724418795591109682123812450311938710290996517774382878398537530538544334387423518165986799247";
  1074.       p.ShowH("P");
  1075.       q.ShowH("Q");
  1076.       LUI n = p * q;
  1077.       LUI φ = (p - 1) * (q - 1);
  1078.       LUI e = Prime.FindPrime(LUI.Rand(1));
  1079.       LUI d = e.InvMod(φ);
  1080.       n.ShowD("N");
  1081.       e.ShowD("E");
  1082.       d.ShowD("D");
  1083.       LUI t0 = LUI.Rand(n.N) % n;
  1084.       t0.ShowD("T0");
  1085.       LUI t1 = t0.ExpMod(e, n);
  1086.       t1.ShowD("T1");
  1087.       LUI t2 = t1.ExpMod(d, n);
  1088.       t2.ShowD("T2");
  1089.       Console.WriteLine(t0.Eq(t2));
  1090.       return;
  1091.     }
  1092.     /*
  1093.     {
  1094.       LUI m = LUI.Rand(8);
  1095.       m.ShowD("M");
  1096.       //var v = ElGamal.Gen(size);
  1097.       LUI p = "104877538395683983366410382169067664128088998324969954776913609710709979673872106181302424272451630465255903890993699866432944529691302121829280875212192060249409981488097721928049610630033097449915456635611191146165881248842161083160683443076013973067893398700983745781152640174308826993566956033515645669283";
  1098.       //LUI q = "133555787139965542016652020299042388774493285356924243918801203066549237266540858298157432621828743072406798037259250876162616325748283692572042900004902260407064923767113776920105687530531338672948803242326218839058724418795591109682123812450311938710290996517774382878398537530538544334387423518165986799247";
  1099.       //LUI p = "1220251634350225977687049836324995396915571036663148756072312277613143771856010961360650116892529677586646678213189183903471802445096501264713053398827645108144546563333650685364968197955792005605450737325870584138986692939916339039";
  1100.       //LUI p = v.p;
  1101.       p.ShowD("P");
  1102.       Console.WriteLine($"({Arr.StrD(p.A).Length})");
  1103.       Console.WriteLine(p.FPTest((uint)LUI.Rand(1).A[0]));
  1104.       Console.WriteLine((p >> 1).FPTest((uint)LUI.Rand(1).A[0]));
  1105.       LUI g = 2;
  1106.       while (g.ExpMod((p - 1) >> 1, p).Eq(1)) g += 1;
  1107.       g.ShowD("G");
  1108.       LUI x = LUI.Rand(size) % p;
  1109.       x.ShowD("X");
  1110.       LUI y = g.ExpMod(x, p);
  1111.       y.ShowD("Y = (G^X mod P)");
  1112.       LUI k = LUI.Rand(p.N) % p;
  1113.       while (!k.CoPrime(p - 1)) k += 1;
  1114.       k.ShowD("K");
  1115.       LUI r = g.ExpMod(k, p);
  1116.       r.ShowD("R = (G^K mod P)");
  1117.       LUI t1 = m % (p - 1);
  1118.       LUI t2 = (r * x) % (p - 1);
  1119.       LUI t = (t1 > t2 ? t1 - t2 : (p - 1 + t1 - t2)) % (p - 1);
  1120.       LUI s = (t * k.InvMod(p - 1)) % (p - 1);
  1121.       s.ShowD("S = (M–RX)·K^–1 mod P–1");
  1122.       LUI w1, w2;
  1123.       (w1 = g.ExpMod(m, p)).ShowD("G^M mod P");
  1124.       (w2 = (y.ExpMod(r, p) * r.ExpMod(s, p)) % p).ShowD("(Y^R)·(R^S) mod P");
  1125.       Console.WriteLine(w1.Eq(w2));
  1126.       return;
  1127.     }
  1128.     */
  1129.     /*
  1130.         {
  1131.           DateTime tm0 = DateTime.Now;
  1132.           Z[] z = new Z[31];
  1133.           for (int i = 0; i <= 30; i++)
  1134.             z[i] = Z.Pow(i);
  1135.           Console.WriteLine("OK");
  1136.           //return;
  1137.           int n = 30;
  1138.           Ration[,] m = new Ration[n, n + 1];
  1139.           for (int i = 0; i < n; i++) {
  1140.             for (int j = 0; j < n; j++)
  1141.               m[i, j] = z[j].a[i];
  1142.             m[i, n] = -z[n].a[i];
  1143.           }
  1144.           Ration[] k = Ration.SolveLinEq(m);
  1145.           Ration[] α = new Ration[31];
  1146.           Console.WriteLine(DateTime.Now - tm0);
  1147.  
  1148.           string str = "";
  1149.           string txt0 = "0";
  1150.           string txt = "0";
  1151.           string X = "(2^(1/2)+3^(1/3)+5^(1/5))";
  1152.           string pw = "⁰¹²³⁴⁵⁶⁷⁸⁹";
  1153.           string Pow(int n) {
  1154.             string s = n.ToString(), res = "";
  1155.             foreach (char c in s)
  1156.               res += pw[(int)(c - '0')];
  1157.             return res;
  1158.           }
  1159.           long[] q = new long[31];
  1160.           for (int i = 30; i >= 0; i--) {
  1161.  
  1162.             α[i] = i == 30 ? new Ration(1, 1, 1) : k[i].Copy;
  1163.             bool f0 = α[i].Sign == 0;
  1164.             bool f1 = α[i].Nom.Eq(1);
  1165.             str += (f0 ? "" : (α[i].Sign < 0 ? " – " : (str == "" ? "" : " + ")) + (f1 ? "" : α[i].Nom.A[0].ToString()) + (i > 0 ? "x" : "") + (i > 1 ? Pow(i) : ""));
  1166.             long h = i == 30 ? 1 : (k[i].IsZero ? 0 : (long)k[i].Nom.A[0] * k[i].Sign);
  1167.             //q[i] = i == 30 ? 1 : (k[i].IsZero ? 0 : (long)k[i].Nom.A[0] * k[i].Sign);
  1168.             txt0 = "(" + txt0 + ")" + "t" + (h < 0 ? h : "+" + h);
  1169.             txt = "(" + txt + ")" + X + (h < 0 ? h : "+" + h);
  1170.           }
  1171.  
  1172.  
  1173.           Console.WriteLine(str);
  1174.           Console.WriteLine(txt0);
  1175.           Console.WriteLine(txt);
  1176.           Console.ReadLine();
  1177.  
  1178.           for (int i = 0; i < n; i++) {
  1179.             Console.ForegroundColor = ConsoleColor.Green;
  1180.             Console.WriteLine(m[i, n].Str());
  1181.             Ration s = 0;
  1182.             for (int j = 0; j < n; j++) s += m[i, j] * k[j];
  1183.             Console.ForegroundColor = ConsoleColor.Red;
  1184.             Console.WriteLine(s.Str() + "\n");
  1185.           }
  1186.           Console.ForegroundColor = ConsoleColor.White;
  1187.           //Z.Pow(30).Show();
  1188.           return;
  1189.  
  1190.         }
  1191.     */
  1192.     /*
  1193.     {
  1194.       LUI p = "37605860339154331679080579905998844540066114455761079119382916420484313254321328050681891452905231893193699510228303";
  1195.       p.ShowD("P");
  1196.       Console.WriteLine(p.FPTest(210));
  1197.       (p >> 1).ShowD("(P–1)/2");
  1198.       Console.WriteLine((p >> 1).FPTest(210));
  1199.       LUI q = "34376587942203771050451147160461810819833374251570386618341800117863423913380583670105177918021715768498881439527763";
  1200.       q.ShowD("Q");
  1201.       Console.WriteLine(q.FPTest(210));
  1202.       (q >> 1).ShowD("(Q–1)/2");
  1203.       Console.WriteLine((q >> 1).FPTest(210));
  1204.       return;
  1205.     }
  1206.     */
  1207.     /*
  1208.     {
  1209.       int size = 12;
  1210.       var v = ElGamal.Gen(size);
  1211.  
  1212.       while (true) {
  1213.         Console.Clear();
  1214.         v.p.ShowH("P");
  1215.         v.p.ShowD();
  1216.         v.g.ShowD("G");
  1217.         LUI k = LUI.Rand(size) % v.p;
  1218.         k.ShowH("K");
  1219.         k.ShowD();
  1220.         LUI a = v.g.ExpMod(k, v.p);
  1221.         a.ShowH("A");
  1222.         a.ShowD();
  1223.         LUI m0 = LUI.Rand(size) % v.p;
  1224.         m0.ShowH("M0");
  1225.         m0.ShowD();
  1226.         LUI b = (m0 * v.gx.ExpMod(k, v.p)) % v.p;
  1227.         b.ShowH("B");
  1228.         b.ShowD();
  1229.         LUI m1 = (b * a.InvMod(v.p).ExpMod(v.x, v.p)) % v.p;
  1230.         m1.ShowH("M1");
  1231.         m1.ShowD();
  1232.         Console.ReadLine();
  1233.       }
  1234.       return;
  1235.       */
  1236.  
  1237.  
  1238.     {
  1239.       var v = ElGamal.Gen(size);
  1240.       v.p.ShowH("P");
  1241.       v.p.ShowD();
  1242.       v.g.ShowH("G");
  1243.       v.g.ShowD();
  1244.       v.x.ShowH("X");
  1245.       v.x.ShowD();
  1246.       v.gx.ShowH("G^X mod P");
  1247.       v.gx.ShowD();
  1248.       v.y.ShowH("Y");
  1249.       v.y.ShowD();
  1250.       v.gy.ShowH("G^Y mod P");
  1251.       v.gy.ShowD();
  1252.       v.gxy.ShowH("(G^X)^Y mod P");
  1253.       v.gxy.ShowD();
  1254.       v.gyx.ShowH("(G^Y)^X mod P");
  1255.       v.gyx.ShowD();
  1256.       Console.WriteLine("\n\n");
  1257.       return;
  1258.     }
  1259.  
  1260.  
  1261.     /*
  1262.     {
  1263.       LUI n = Prime.FindSG(LUI.Rand1(size), true);
  1264.       n.ShowH("N");
  1265.       n.ShowD();
  1266.       LUI g;
  1267.       for (g = 2; ; g += 1) {
  1268.         if (!g.ExpMod(n >> 1, n).Eq(1)) break;
  1269.       }
  1270.       Console.WriteLine();
  1271.  
  1272.       g.ShowD("G");
  1273.       LUI x = LUI.Rand(size);
  1274.       x.ShowH("X");
  1275.       x.ShowD();
  1276.       LUI y = LUI.Rand(size);
  1277.       y.ShowH("Y");
  1278.       y.ShowD();
  1279.       LUI xx = g.ExpMod(x, n);
  1280.       xx.ShowH("G^X mod N");
  1281.       xx.ShowD();
  1282.       LUI yy = g.ExpMod(y, n);
  1283.       yy.ShowH("G^Y mod N");
  1284.       yy.ShowD();
  1285.       LUI k1 = yy.ExpMod(x, n);
  1286.       k1.ShowH("K1 = (G^Y mod N)^X mod N");
  1287.       k1.ShowD();
  1288.       LUI k2 = xx.ExpMod(y, n);
  1289.       k2.ShowH("K2 = (G^X mod N)^Y mod N");
  1290.       k2.ShowD();
  1291.       return;
  1292.     }
  1293.     */
  1294.  
  1295.     {
  1296.       RSA.Show(size, true, true, false);
  1297.       Console.WriteLine("\n\n\n");
  1298.       return;
  1299.     }
  1300.     {
  1301.  
  1302.       for (LUI x = ((LUI)10).Pow(50); ; x -= 1) {
  1303.         Console.Clear();
  1304.         x.ShowH();
  1305.         if (x.FPTest(2))
  1306.           break;
  1307.       }
  1308.       Console.WriteLine("OK");
  1309.     }
  1310.   }
  1311. }
  1312.  
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!