Advertisement
Guest User

Untitled

a guest
Dec 11th, 2017
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.97 KB | None | 0 0
  1. using System;
  2. using System.Numerics;
  3.  
  4. namespace Blum_Blum
  5. {
  6.  
  7.  
  8. class MainClass
  9. {
  10. static Random rnd;
  11. static BigInteger lcm(BigInteger a, BigInteger b)
  12. {
  13. return a * b / BigInteger.GreatestCommonDivisor(a, b);
  14. }
  15.  
  16.  
  17. public static BigInteger genParam(int bits)
  18. {
  19. BigInteger prime = genRand(bits);
  20. Console.WriteLine(prime);
  21. while (prime % 4 != 3)
  22. prime++;
  23. while (!checkprime(prime))
  24. {
  25. Console.WriteLine(prime);
  26. prime += 4;
  27. }
  28. return prime;
  29. }
  30.  
  31. public static bool checkprime(BigInteger n)// здесь тест на определние простое или нет
  32. {
  33. if (n < 2)
  34. return false;
  35. if (n == 2 || n == 3)
  36. return true;
  37. if (n % 2 == 0)
  38. return false;
  39. int bits = (int)BigInteger.Log(n, 2);
  40. int s = 0;
  41. BigInteger x = n - 1;
  42. while (x % 2 == 0)
  43. {
  44. s++;
  45. x /= 2;
  46. }
  47. BigInteger t = x;
  48.  
  49. for (int i = 0; i < bits; i++)
  50. {
  51. BigInteger a = genRand(2, n - 1);
  52.  
  53. x = BigInteger.ModPow(a, t, n);
  54. if (x == 1 || x == n - 1)
  55. continue;
  56. bool pr = false;
  57. for (int j = 0; !pr && j < s - 1; j++)
  58. {
  59. x = (x * x) % n;
  60. if (x == 1)
  61. return false;
  62. if (x == n - 1)
  63. pr = true;
  64.  
  65. }
  66. if (!pr)
  67. return false;
  68. }
  69. return true;
  70. }
  71.  
  72.  
  73. public static BigInteger genRand(BigInteger min, BigInteger max) // вот тут генерируем число так чтобы оно было больше равно min и меньше max
  74.  
  75. {
  76. int bits = (int)BigInteger.Log(max, 2);
  77. BigInteger res = 0, pow = 1;
  78. int[] b = new int[bits];
  79. do
  80. {
  81. res = 0;
  82. pow = 1;
  83. for (int i = 0; i < bits; i++)
  84. b[i] = rnd.Next(2);
  85.  
  86. for (int i = 0; i < bits; i++, pow *= 2)
  87. res += b[i] * pow;
  88. }
  89. while (res < min || res >= max);
  90.  
  91. return res;
  92. }
  93. public static BigInteger genRand(int bits)
  94.  
  95. {
  96.  
  97. BigInteger res = 0, pow = 1;
  98. int[] b = new int[bits];
  99. b[bits-1] = 1;
  100. for (int i = 0; i < bits-1; i++)
  101. b[i] = rnd.Next(2);
  102. for (int i = 0; i < bits; i++, pow *= 2)
  103. res += b[i] * pow;
  104.  
  105. return res;
  106. }
  107.  
  108.  
  109. static BigInteger nth_element(BigInteger x, BigInteger n, BigInteger p, BigInteger q)
  110. {
  111. BigInteger lambda = lcm(p - 1, q - 1);
  112.  
  113. BigInteger xn = BigInteger.ModPow(x, BigInteger.ModPow(2, n, lambda), p * q);
  114. return xn;
  115. }
  116.  
  117.  
  118. public static void Main(string[] args)
  119. {
  120. rnd = new Random();
  121. BigInteger p = genParam(4); // генерим 4 битное простое число которое сравнимо с 3 по модулю 4 то есть p%4==3
  122. BigInteger q = genParam(6);// тут тоже самое но с 6 битами. 4 и 6 на шару написал можно любые другие цифры
  123. Console.WriteLine("p = "+p);
  124. Console.WriteLine("q = "+q);
  125.  
  126. BigInteger M = p * q;
  127. Console.WriteLine("M = " + M);
  128. BigInteger x0 = genRand(2,M);
  129. while(BigInteger.GreatestCommonDivisor(M, x0) > 1) // x0 должно быть взаимнопростым с М то есть НОД(x0,M) должно быть = 1
  130. {
  131. x0 = genRand(2, M); // пока нод больше 1 генерим х0 по новой
  132. }
  133.  
  134. Console.WriteLine("x0 = " + x0);
  135.  
  136. Console.WriteLine("Введите длину последовательности: ");
  137. int sz = int.Parse(Console.ReadLine());
  138. BigInteger[] x = new BigInteger[sz + 1];
  139. x[0] = x0*x0 % M;
  140. for (int i = 1; i <= sz; i++)
  141. x[i] = x[i - 1] * x[i - 1] % M;
  142.  
  143. for (int i = 0; i <= sz; i++)
  144. Console.WriteLine(x[i]);
  145.  
  146.  
  147. Console.WriteLine("Введите n: ");
  148. int n = int.Parse(Console.ReadLine());
  149.  
  150. BigInteger xn = nth_element(x[0], n, p, q);
  151.  
  152. Console.WriteLine("n-тый элемент : "+xn);
  153. }
  154. }
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement