Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Numerics;
- namespace Laba
- {
- class MyRandom
- {
- static Random rand = new Random();
- public static BigInteger Next(BigInteger left, BigInteger right) // генерация числа в диапазоне [left,right)
- {
- int sz = (int)BigInteger.Log(right, 2);
- BigInteger ans = 0, p = 1;
- do
- {
- ans = 0;
- p = 1;
- for (int i = 0; i < sz; i++)
- {
- ans += rand.Next(2) * p;
- p *= 2;
- }
- }
- while (ans < left || ans >= right);
- return ans;
- }
- }
- class PrimeTest
- {
- static int Jac(BigInteger a, BigInteger n)
- {
- int ans = 1;
- while (a > 1)
- {
- int x = 0;
- while (a % 2 == 0)
- {
- x++;
- a /= 2;
- }
- if (a % 4 == 3 && n % 4 == 3)
- ans = -ans;
- if (x % 2 == 1 && (n % 8 == 3 || n % 8 == 5))
- ans = -ans;
- BigInteger temp = a;
- a = n % temp;
- n = temp;
- }
- return ans;
- }
- public static bool is_prime(BigInteger n)
- {
- if (n < 2 || n%2==0)
- return false;
- if (n == 2 || n == 3)
- return true;
- int k = (int)BigInteger.Log(n, 2);
- for (int i = 0; i < k; i++)
- {
- BigInteger a = MyRandom.Next(2, n);
- if (BigInteger.GreatestCommonDivisor(a, n) > 1)
- return false;
- BigInteger Jacoby = Jac(a, n);
- if (Jacoby == -1)
- Jacoby += n;
- if (BigInteger.ModPow(a, (n - 1) / 2, n) != Jacoby)
- return false;
- }
- return true;
- }
- }
- class Blum
- {
- public BigInteger P, Q, x0, M;
- public Blum(BigInteger p, BigInteger q, BigInteger x)
- {
- P = p;
- Q = q;
- x0 = x;
- M = p * q;
- }
- BigInteger lcm(BigInteger x, BigInteger y)
- {
- return x / BigInteger.GreatestCommonDivisor(x, y) * y;
- }
- public BigInteger[] GenerateSequence(int len)
- {
- BigInteger[] x = new BigInteger[len];
- x[0] = x0;
- for (int i = 1; i < len; i++)
- x[i] = x[i - 1] * x[i - 1] % M;
- return x;
- }
- public BigInteger GenerateIthElement(int i)
- {
- BigInteger l = lcm(P - 1, Q - 1);
- BigInteger pow = BigInteger.ModPow(2, i, l);
- BigInteger ans = BigInteger.ModPow(x0, pow, M);
- return ans;
- }
- }
- class MainClass
- {
- public static void Main(string[] args)
- {
- // это блум блум
- BigInteger p = 19;
- BigInteger q = 11;
- BigInteger x0 = 3;
- Blum bb = new Blum(p, q, x0);
- Console.WriteLine("p = {0}", bb.P);
- Console.WriteLine("q = {0}", bb.Q);
- Console.WriteLine("M = {0}", bb.M);
- Console.WriteLine("x0 = {0}", bb.x0);
- int i = 7;
- Console.WriteLine("{0} element of sequence is {1}", i, bb.GenerateIthElement(i));
- BigInteger[] x = bb.GenerateSequence(10);
- Console.WriteLine("Sequence:");
- for (int k = 0; k < 10; k++)
- Console.WriteLine(x[k]);
- // это Соловей
- Console.WriteLine();
- BigInteger n = 167; // число которое хотим проверить на простоту
- if (PrimeTest.is_prime(n))
- {
- Console.WriteLine("{0} простое", n);
- }
- else
- {
- Console.WriteLine("{0} состановное", n);
- }
- n = 147; // число которое хотим проверить на простоту
- if (PrimeTest.is_prime(n))
- {
- Console.WriteLine("{0} простое", n);
- }
- else
- {
- Console.WriteLine("{0} состановное", n);
- }
- Console.ReadKey();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement