Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Numerics;
- namespace Blum_Blum
- {
- class MainClass
- {
- static Random rnd;
- static BigInteger lcm(BigInteger a, BigInteger b)
- {
- return a * b / BigInteger.GreatestCommonDivisor(a, b);
- }
- public static BigInteger genParam(int bits)
- {
- BigInteger prime = genRand(bits);
- Console.WriteLine(prime);
- while (prime % 4 != 3)
- prime++;
- while (!checkprime(prime))
- {
- Console.WriteLine(prime);
- prime += 4;
- }
- return prime;
- }
- public static bool checkprime(BigInteger n)// здесь тест на определние простое или нет
- {
- if (n < 2)
- return false;
- if (n == 2 || n == 3)
- return true;
- if (n % 2 == 0)
- return false;
- int bits = (int)BigInteger.Log(n, 2);
- int s = 0;
- BigInteger x = n - 1;
- while (x % 2 == 0)
- {
- s++;
- x /= 2;
- }
- BigInteger t = x;
- for (int i = 0; i < bits; i++)
- {
- BigInteger a = genRand(2, n - 1);
- x = BigInteger.ModPow(a, t, n);
- if (x == 1 || x == n - 1)
- continue;
- bool pr = false;
- for (int j = 0; !pr && j < s - 1; j++)
- {
- x = (x * x) % n;
- if (x == 1)
- return false;
- if (x == n - 1)
- pr = true;
- }
- if (!pr)
- return false;
- }
- return true;
- }
- public static BigInteger genRand(BigInteger min, BigInteger max) // вот тут генерируем число так чтобы оно было больше равно min и меньше max
- {
- int bits = (int)BigInteger.Log(max, 2);
- BigInteger res = 0, pow = 1;
- int[] b = new int[bits];
- do
- {
- res = 0;
- pow = 1;
- for (int i = 0; i < bits; i++)
- b[i] = rnd.Next(2);
- for (int i = 0; i < bits; i++, pow *= 2)
- res += b[i] * pow;
- }
- while (res < min || res >= max);
- return res;
- }
- public static BigInteger genRand(int bits)
- {
- BigInteger res = 0, pow = 1;
- int[] b = new int[bits];
- b[bits-1] = 1;
- for (int i = 0; i < bits-1; i++)
- b[i] = rnd.Next(2);
- for (int i = 0; i < bits; i++, pow *= 2)
- res += b[i] * pow;
- return res;
- }
- static BigInteger nth_element(BigInteger x, BigInteger n, BigInteger p, BigInteger q)
- {
- BigInteger lambda = lcm(p - 1, q - 1);
- BigInteger xn = BigInteger.ModPow(x, BigInteger.ModPow(2, n, lambda), p * q);
- return xn;
- }
- public static void Main(string[] args)
- {
- rnd = new Random();
- BigInteger p = genParam(4); // генерим 4 битное простое число которое сравнимо с 3 по модулю 4 то есть p%4==3
- BigInteger q = genParam(6);// тут тоже самое но с 6 битами. 4 и 6 на шару написал можно любые другие цифры
- Console.WriteLine("p = "+p);
- Console.WriteLine("q = "+q);
- BigInteger M = p * q;
- Console.WriteLine("M = " + M);
- BigInteger x0 = genRand(2,M);
- while(BigInteger.GreatestCommonDivisor(M, x0) > 1) // x0 должно быть взаимнопростым с М то есть НОД(x0,M) должно быть = 1
- {
- x0 = genRand(2, M); // пока нод больше 1 генерим х0 по новой
- }
- Console.WriteLine("x0 = " + x0);
- Console.WriteLine("Введите длину последовательности: ");
- int sz = int.Parse(Console.ReadLine());
- BigInteger[] x = new BigInteger[sz + 1];
- x[0] = x0*x0 % M;
- for (int i = 1; i <= sz; i++)
- x[i] = x[i - 1] * x[i - 1] % M;
- for (int i = 0; i <= sz; i++)
- Console.WriteLine(x[i]);
- Console.WriteLine("Введите n: ");
- int n = int.Parse(Console.ReadLine());
- BigInteger xn = nth_element(x[0], n, p, q);
- Console.WriteLine("n-тый элемент : "+xn);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement