C# Online Compiler | .NET Fiddle

<no name> by Anonymous

using System;
using System.Collections.ObjectModel;
using System.Numerics;
using System.Text;

public class Program
{
	public static void Main()
	{
		int p = 53,
			q = 59,
			e = 3;
		
		var key = new RSAKey(p, q, e);
		byte[] message = Encoding.Default.GetBytes("abcdefghijk");
		
		Console.WriteLine($"Модуль n и закрытая экспонента d при множителях {p}, {q} и открытой экспоненте e = {e}:\n");
		Console.WriteLine($"n = {key.n}");
		Console.WriteLine($"d = {key.d}");
		
		Test(message, key);
		
		key = RSA.Generate(1024);
		message = Encoding.Default.GetBytes(
			"В основу криптографической системы с открытым ключом RSA положена сложность задачи " +
			"факторизации произведения двух больших простых чисел. Для шифрования используется " +
			"операция возведения в степень по модулю большого числа. Для дешифрования (обратной " +
			"операции) за разумное время необходимо уметь вычислять функцию Эйлера от данного " +
			"большого числа, для чего необходимо знать разложение числа на простые множители."
		);
		
		Console.WriteLine("\nЗначение n модуля:\n");       PrintBytes(key.n.ToByteArray(true, true));
		Console.WriteLine("\nОткрытая экспонента e:\n"); PrintBytes(key.e.ToByteArray(true, true));
		Console.WriteLine("\nЗакрытая экспонента d:\n"); PrintBytes(key.d.ToByteArray(true, true));
		
		Test(message, key);
		Test(message, key, paddingBytes: 4);
		Test(message, key, paddingBytes: 32);
	}
	
	static void Test(byte[] message, RSAKey key, int paddingBytes = 0)
	{
		byte[] cipher = RSA.Encrypt(message, key.n, key.e, paddingBytes);
		byte[] source = RSA.Decrypt(cipher, key.n, key.d, paddingBytes);
		
		Console.WriteLine(
			paddingBytes == 0
			?
			$"\nЗашифрованный текст длиной {cipher.Length} байт без вставки (одинаковые" +
			" исходные данные соответствуют одинаковым зашифрованным данным):\n"
			:
			$"\nЗашифрованный текст длиной {cipher.Length} байт со случайной" +
		    $" вставкой длиной {paddingBytes} байт перед каждым блоком данных:\n"
		);
		PrintBytes(cipher);
		Console.WriteLine("\nРасшифрованный текст:\n");
		PrintString(source);
		Console.WriteLine("\n" + new string('-', 149));
	}
	
	static void PrintBytes(byte[] bytes)
	{
		for (int i = 0; i < bytes.Length; i += 50)
		{
			for (int j = 0; j < 50 && i + j < bytes.Length; j++)
			{
				Console.Write(Convert.ToString(bytes[i + j], 16).PadLeft(2, '0') + " ");
			}
			Console.WriteLine();
		}
	}
	
	static void PrintString(byte[] bytes)
	{
		string s = Encoding.UTF8.GetString(bytes);
		bool breakLine = true;
		for (int i = 0; i < s.Length; i++)
		{
			if (i % 135 == 0) breakLine = !breakLine;
			if (breakLine && s[i] == ' ')
			{
				Console.Write('\n');
				breakLine = false;
			}
			else Console.Write(s[i]);
		}
		Console.WriteLine();
	}
}


public readonly struct RSAKey
{
	public BigInteger n { get; }
	public BigInteger e { get; }
	public BigInteger d { get; }
	
	public RSAKey(BigInteger p, BigInteger q, BigInteger e)
	{
		if (!PrimalityTest.General(p, 64) || !PrimalityTest.General(q, 64))
		{
			throw new ArgumentException("Числа p и q должны быть простыми.");
		}
		
		BigInteger phi = (p - 1) * (q - 1);
		if (e <= 1 || e >= phi || Utils.GCD(phi, e) != 1)
		{
			throw new ArgumentException("Открытая экспонента e должна находиться в диапазоне от 2 до \u03C6(pq) - 1 и быть взаимно простой с \u03C6(pq).");
		}
		
		BigInteger _, d;
		Utils.GCD(phi, e, out _, out d);
		if (d < 0) d += phi;
			
		this.n = p * q;
		this.e = e;
		this.d = d;
	}
}


public class RSA
{
	public static RSAKey Generate(int keyLength)
	{
		if (keyLength < 512 || keyLength % 256 != 0)
		{
			throw new ArgumentException("Длина ключа должна составлять не менее 512 бит и быть кратной 256.");
		}
		BigInteger e = 65537;
		BigInteger min = GetLowerBound(keyLength);
		BigInteger max = BigInteger.Pow(2, keyLength / 2) - 1;
		BigInteger p, q, phi;
		do
		{
			p = GeneratePrime(min, max);
			q = GeneratePrime(min, max);
			phi = (p - 1) * (q - 1);
		}
		while (Utils.GCD(phi, e) != 1);
		
		return new RSAKey(p, q, e);
	}
	
	private static BigInteger GetLowerBound(int exp)
	{
		string sqrt2 = Math.Sqrt(2).ToString().Remove(1, 1);
		return BigInteger.Pow(2, exp / 2 - 1) * BigInteger.Parse(sqrt2)
		       / BigInteger.Pow(10, sqrt2.Length - 1);
	}
	
	private static BigInteger GeneratePrime(BigInteger min, BigInteger max)
	{
		BigInteger num;
		Random seed = new Random();
		do
		{
			num = Utils.BigRandom(min, max, seed.Next());
		}
		while(!PrimalityTest.General(num, 64));
		return num;
	}
	
	public static byte[] Encrypt(byte[] source, BigInteger n, BigInteger e, int padding = 0)
	{
		int cipherBlockLength = n.GetByteCount(true);
		int sourceBlockLength = cipherBlockLength - 1 - padding;
		
		Validate(cipherBlockLength, sourceBlockLength);
		
		int blockCount = (source.Length + sourceBlockLength - 1 ) / sourceBlockLength;
		byte[] cipher = new byte[blockCount * cipherBlockLength];
		Random r = new Random();
		
		for (int i = 0; i < blockCount; i++)
		{
			int sourceOffset = i * sourceBlockLength;
			int cipherOffset = i * cipherBlockLength;
			BigInteger block = 0;
			
			for (int j = 0; j < padding; j++)
			{
				block += (BigInteger)r.Next(0, 256) << ((sourceBlockLength + padding - 1 - j) * 8);
			}
			
			for (int j = 0; j < sourceBlockLength && sourceOffset + j < source.Length; j++)
			{
				byte srcByte = source[sourceOffset + j];
				block += (BigInteger)srcByte << ((sourceBlockLength - 1 - j) * 8);
			}
			
			block = BigInteger.ModPow(block, e, n);
			
			byte[] blockBytes = block.ToByteArray(true, true);
			for (int j = 0; j < blockBytes.Length; j++)
			{
				cipher[cipherOffset + cipherBlockLength - 1 - j]
					= blockBytes[blockBytes.Length - 1 - j];
			}
		}
		
		return cipher;
	}
	
	
	public static byte[] Decrypt(byte[] cipher, BigInteger n, BigInteger d, int padding = 0)
	{
		int cipherBlockLength = n.GetByteCount(true);
		int sourceBlockLength = cipherBlockLength - 1 - padding;
		
		Validate(cipherBlockLength, sourceBlockLength, cipher.Length);
		
		int blockCount = cipher.Length / cipherBlockLength;
		byte[] source = new byte[blockCount * sourceBlockLength];
		Random r = new Random();
		
		for (int i = 0; i < blockCount; i++)
		{
			int sourceOffset = i * sourceBlockLength;
			int cipherOffset = i * cipherBlockLength;
			BigInteger block = 0;
			
			for (int j = 0; j < cipherBlockLength; j++)
			{
				byte cphByte = cipher[cipherOffset + j];
				block += (BigInteger)cphByte << ((cipherBlockLength - 1 - j) * 8);
			}
			
			block = BigInteger.ModPow(block, d, n);
			
			byte[] blockBytes = block.ToByteArray(true, true);
			for (int j = 0; j < sourceBlockLength; j++)
			{
				source[sourceOffset + sourceBlockLength - 1 - j]
					= blockBytes[blockBytes.Length - 1 - j];
			}
		}
		
		return source;
	}
	
	private static void Validate(int cipherBlockLength, int sourceBlockLength,
								 int dataLength = 0)
	{
		if (cipherBlockLength < 2)
		{
			throw new ArgumentException("Длина ключа должна составлять более одного байта.");
		}
		if (sourceBlockLength < 1)
		{
			throw new ArgumentException($"При длине ключа {cipherBlockLength} байт длина вставки " +
										$"не должна превышать {cipherBlockLength - 2} байт.");
		}
		if (dataLength % cipherBlockLength != 0)
		{
			throw new ArgumentException($"Некорректный формат зашифрованного текста.");
		}
	}
}


public static class PrimalityTest
{
	private static readonly int[] below1000 = new int[]
	{
		2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
		73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
		157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
		239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
		331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
		421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
		509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
		613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
		709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
		821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
		919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
	};
	
	public static ReadOnlyCollection<int> Below1000 => Array.AsReadOnly(below1000);
	
	public static bool General(BigInteger n, int iterations)
	{
		bool composite = false;
		for (int i = 0; i < below1000.Length; i++)
		{
			if (below1000[i] * below1000[i] > n)
			{
				break;
			}
			if (n % below1000[i] == 0 && n != below1000[i])
			{
				composite = true;
				break;
			}
		}
		return !composite && PrimalityTest.MillerRabin(n, iterations);
	}
	
	public static bool MillerRabin(BigInteger n, int iterations)
	{
		if (n < 2 || iterations < 1) return false;
		
		if (n - 3 < iterations)
			iterations = (int)n - 3;
		
		BigInteger d = n - 1;
		int s = 0;
		while (d % 2 == 0)
		{
			d /= 2;
			s++;
		}
		
		BigInteger a = 1;
		for (int i = 0; i < iterations; i++)
		{
			a = Utils.BigRandom(a + 1, 2 + (n - 4) * (i + 1) / iterations);
			BigInteger aExp = BigInteger.ModPow(a, d, n);
			
			if (aExp == 1)
				continue;
			
			bool strongProbablePrime = false;
			for (int r = 0; r < s; r++)
			{
				if (aExp == n - 1)
				{
					strongProbablePrime = true;
					break;
				}
				aExp = aExp * aExp % n;
			}
			if (!strongProbablePrime) return false;
		}
		
		return true;
	}
}


public static class Utils
{
    public static BigInteger BigRandom(BigInteger min, BigInteger max)
    {
		return BigRandom(min, max, (int)DateTime.Now.Ticks);
	}
	
    public static BigInteger BigRandom(BigInteger min, BigInteger max, int seed)
    {
		if (max <= min) return min;
		
		BigInteger shift = min;
		max -= min;
		min = 0;
        
		byte[] bytes = max.ToByteArray();
		int maskLength = Math.Max((int)Math.Log(bytes[bytes.Length - 1], 2) + 1, 0);
		Random r = new Random(seed);
		BigInteger n;
		do
		{
			r.NextBytes(bytes);
			bytes[bytes.Length - 1] &= (byte)(Math.Pow(2, maskLength) - 1);
			n = new BigInteger(bytes);
		}
		while (n > max);
		
		n += shift;
        return n;
    }
	
	public static BigInteger GCD(BigInteger n, BigInteger m)
	{
		while (n != 0)
		{
			BigInteger temp = n;
			n = m % n;
			m = temp;
		}
		return m;
	}
	
	public static BigInteger GCD(BigInteger n, BigInteger m,
								 out BigInteger x, out BigInteger y)
	{
		BigInteger x0 = 1, x1 = 0;
		BigInteger y0 = 0, y1 = 1;
		
		while (m != 0)
		{
			BigInteger q, r;
			q = BigInteger.DivRem(n, m, out r);
			
			n = m;
			m = r;
			
			BigInteger x2 = x0 - q * x1;
			x0 = x1;
			x1 = x2;
			
			BigInteger y2 = y0 - q * y1;
			y0 = y1;
			y1 = y2;
		}
		
		x = x0;
		y = y0;
		return n;
	}
}

​x
 
using System;
using System.Collections.ObjectModel;
using System.Numerics;
using System.Text;
​
public class Program
{
    public static void Main()
    {
        int p = 53,
            q = 59,
            e = 3;
        
        var key = new RSAKey(p, q, e);
        byte[] message = Encoding.Default.GetBytes("abcdefghijk");
        
        Console.WriteLine($"Модуль n и закрытая экспонента d при множителях {p}, {q} и открытой экспоненте e = {e}:\n");
        Console.WriteLine($"n = {key.n}");
        Console.WriteLine($"d = {key.d}");
        
        Test(message, key);
        
        key = RSA.Generate(1024);
        message = Encoding.Default.GetBytes(
            "В основу криптографической системы с открытым ключом RSA положена сложность задачи " +
            "факторизации произведения двух больших простых чисел. Для шифрования используется " +
            "операция возведения в степень по модулю большого числа. Для дешифрования (обратной " +
            "операции) за разумное время необходимо уметь вычислять функцию Эйлера от данного " +
            "большого числа, для чего необходимо знать разложение числа на простые множители."
        );
        
        Console.WriteLine("\nЗначение n модуля:\n");       PrintBytes(key.n.ToByteArray(true, true));
        Console.WriteLine("\nОткрытая экспонента e:\n"); PrintBytes(key.e.ToByteArray(true, true));
        Console.WriteLine("\nЗакрытая экспонента d:\n"); PrintBytes(key.d.ToByteArray(true, true));
        
        Test(message, key);
        Test(message, key, paddingBytes: 4);
        Test(message, key, paddingBytes: 32);
    }
    
    static void Test(byte[] message, RSAKey key, int paddingBytes = 0)
    {
        byte[] cipher = RSA.Encrypt(message, key.n, key.e, paddingBytes);
        byte[] source = RSA.Decrypt(cipher, key.n, key.d, paddingBytes);
        
        Console.WriteLine(
            paddingBytes == 0
            ?
            $"\nЗашифрованный текст длиной {cipher.Length} байт без вставки (одинаковые" +
            " исходные данные соответствуют одинаковым зашифрованным данным):\n"
            :
            $"\nЗашифрованный текст длиной {cipher.Length} байт со случайной" +
            $" вставкой длиной {paddingBytes} байт перед каждым блоком данных:\n"
        );
        PrintBytes(cipher);
        Console.WriteLine("\nРасшифрованный текст:\n");
        PrintString(source);
        Console.WriteLine("\n" + new string('-', 149));
    }
    
    static void PrintBytes(byte[] bytes)
    {
        for (int i = 0; i < bytes.Length; i += 50)
        {
            for (int j = 0; j < 50 && i + j < bytes.Length; j++)
            {
                Console.Write(Convert.ToString(bytes[i + j], 16).PadLeft(2, '0') + " ");
            }
            Console.WriteLine();
        }
    }
    
    static void PrintString(byte[] bytes)
    {
        string s = Encoding.UTF8.GetString(bytes);
        bool breakLine = true;
        for (int i = 0; i < s.Length; i++)
        {
            if (i % 135 == 0) breakLine = !breakLine;
            if (breakLine && s[i] == ' ')
            {
                Console.Write('\n');
                breakLine = false;
            }
            else Console.Write(s[i]);
        }
        Console.WriteLine();
    }
}
​
​
public readonly struct RSAKey
{
    public BigInteger n { get; }
    public BigInteger e { get; }
    public BigInteger d { get; }
    
    public RSAKey(BigInteger p, BigInteger q, BigInteger e)
    {
        if (!PrimalityTest.General(p, 64) || !PrimalityTest.General(q, 64))
        {
            throw new ArgumentException("Числа p и q должны быть простыми.");
        }
        
        BigInteger phi = (p - 1) * (q - 1);
        if (e <= 1 || e >= phi || Utils.GCD(phi, e) != 1)
        {
            throw new ArgumentException("Открытая экспонента e должна находиться в диапазоне от 2 до \u03C6(pq) - 1 и быть взаимно простой с \u03C6(pq).");
        }
        
        BigInteger _, d;
        Utils.GCD(phi, e, out _, out d);
        if (d < 0) d += phi;
            
        this.n = p * q;
        this.e = e;
        this.d = d;
    }
}
​
​
public class RSA
{
    public static RSAKey Generate(int keyLength)
    {
        if (keyLength < 512 || keyLength % 256 != 0)
        {
            throw new ArgumentException("Длина ключа должна составлять не менее 512 бит и быть кратной 256.");
        }
        BigInteger e = 65537;
        BigInteger min = GetLowerBound(keyLength);
        BigInteger max = BigInteger.Pow(2, keyLength / 2) - 1;
        BigInteger p, q, phi;
        do
        {
            p = GeneratePrime(min, max);
            q = GeneratePrime(min, max);
            phi = (p - 1) * (q - 1);
        }
        while (Utils.GCD(phi, e) != 1);
        
        return new RSAKey(p, q, e);
    }
    
    private static BigInteger GetLowerBound(int exp)
    {
        string sqrt2 = Math.Sqrt(2).ToString().Remove(1, 1);
        return BigInteger.Pow(2, exp / 2 - 1) * BigInteger.Parse(sqrt2)
               / BigInteger.Pow(10, sqrt2.Length - 1);
    }
    
    private static BigInteger GeneratePrime(BigInteger min, BigInteger max)
    {
        BigInteger num;
        Random seed = new Random();
        do
        {
            num = Utils.BigRandom(min, max, seed.Next());
        }
        while(!PrimalityTest.General(num, 64));
        return num;
    }
    
    public static byte[] Encrypt(byte[] source, BigInteger n, BigInteger e, int padding = 0)
    {
        int cipherBlockLength = n.GetByteCount(true);
        int sourceBlockLength = cipherBlockLength - 1 - padding;
        
        Validate(cipherBlockLength, sourceBlockLength);
        
        int blockCount = (source.Length + sourceBlockLength - 1 ) / sourceBlockLength;
        byte[] cipher = new byte[blockCount * cipherBlockLength];
        Random r = new Random();
        
        for (int i = 0; i < blockCount; i++)
        {
            int sourceOffset = i * sourceBlockLength;
            int cipherOffset = i * cipherBlockLength;
            BigInteger block = 0;
            
            for (int j = 0; j < padding; j++)
            {
                block += (BigInteger)r.Next(0, 256) << ((sourceBlockLength + padding - 1 - j) * 8);
            }
            
            for (int j = 0; j < sourceBlockLength && sourceOffset + j < source.Length; j++)
            {
                byte srcByte = source[sourceOffset + j];
                block += (BigInteger)srcByte << ((sourceBlockLength - 1 - j) * 8);
            }
            
            block = BigInteger.ModPow(block, e, n);
            
            byte[] blockBytes = block.ToByteArray(true, true);
            for (int j = 0; j < blockBytes.Length; j++)
            {
                cipher[cipherOffset + cipherBlockLength - 1 - j]
                    = blockBytes[blockBytes.Length - 1 - j];
            }
        }
        
        return cipher;
    }
    
    
    public static byte[] Decrypt(byte[] cipher, BigInteger n, BigInteger d, int padding = 0)
    {
        int cipherBlockLength = n.GetByteCount(true);
        int sourceBlockLength = cipherBlockLength - 1 - padding;
        
        Validate(cipherBlockLength, sourceBlockLength, cipher.Length);
        
        int blockCount = cipher.Length / cipherBlockLength;
        byte[] source = new byte[blockCount * sourceBlockLength];
        Random r = new Random();
        
        for (int i = 0; i < blockCount; i++)
        {
            int sourceOffset = i * sourceBlockLength;
            int cipherOffset = i * cipherBlockLength;
            BigInteger block = 0;
            
            for (int j = 0; j < cipherBlockLength; j++)
            {
                byte cphByte = cipher[cipherOffset + j];
                block += (BigInteger)cphByte << ((cipherBlockLength - 1 - j) * 8);
            }
            
            block = BigInteger.ModPow(block, d, n);
            
            byte[] blockBytes = block.ToByteArray(true, true);
            for (int j = 0; j < sourceBlockLength; j++)
            {
                source[sourceOffset + sourceBlockLength - 1 - j]
                    = blockBytes[blockBytes.Length - 1 - j];
            }
        }
        
        return source;
    }
    
    private static void Validate(int cipherBlockLength, int sourceBlockLength,
                                 int dataLength = 0)
    {
        if (cipherBlockLength < 2)
        {
            throw new ArgumentException("Длина ключа должна составлять более одного байта.");
        }
        if (sourceBlockLength < 1)
        {
            throw new ArgumentException($"При длине ключа {cipherBlockLength} байт длина вставки " +
                                        $"не должна превышать {cipherBlockLength - 2} байт.");
        }
        if (dataLength % cipherBlockLength != 0)
        {
            throw new ArgumentException($"Некорректный формат зашифрованного текста.");
        }
    }
}
​
​
public static class PrimalityTest
{
    private static readonly int[] below1000 = new int[]
    {
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
        73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
        157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
        239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
        331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
        421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
        509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
        613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
        709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
        821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
        919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
    };
    
    public static ReadOnlyCollection<int> Below1000 => Array.AsReadOnly(below1000);
    
    public static bool General(BigInteger n, int iterations)
    {
        bool composite = false;
        for (int i = 0; i < below1000.Length; i++)
        {
            if (below1000[i] * below1000[i] > n)
            {
                break;
            }
            if (n % below1000[i] == 0 && n != below1000[i])
            {
                composite = true;
                break;
            }
        }
        return !composite && PrimalityTest.MillerRabin(n, iterations);
    }
    
    public static bool MillerRabin(BigInteger n, int iterations)
    {
        if (n < 2 || iterations < 1) return false;
        
        if (n - 3 < iterations)
            iterations = (int)n - 3;
        
        BigInteger d = n - 1;
        int s = 0;
        while (d % 2 == 0)
        {
            d /= 2;
            s++;
        }
        
        BigInteger a = 1;
        for (int i = 0; i < iterations; i++)
        {
            a = Utils.BigRandom(a + 1, 2 + (n - 4) * (i + 1) / iterations);
            BigInteger aExp = BigInteger.ModPow(a, d, n);
            
            if (aExp == 1)
                continue;
            
            bool strongProbablePrime = false;
            for (int r = 0; r < s; r++)
            {
                if (aExp == n - 1)
                {
                    strongProbablePrime = true;
                    break;
                }
                aExp = aExp * aExp % n;
            }
            if (!strongProbablePrime) return false;
        }
        
        return true;
    }
}
​
​
public static class Utils
{
    public static BigInteger BigRandom(BigInteger min, BigInteger max)
    {
        return BigRandom(min, max, (int)DateTime.Now.Ticks);
    }
    
    public static BigInteger BigRandom(BigInteger min, BigInteger max, int seed)
    {
        if (max <= min) return min;
        
        BigInteger shift = min;
        max -= min;
        min = 0;
        
        byte[] bytes = max.ToByteArray();
        int maskLength = Math.Max((int)Math.Log(bytes[bytes.Length - 1], 2) + 1, 0);
        Random r = new Random(seed);
        BigInteger n;
        do
        {
            r.NextBytes(bytes);
            bytes[bytes.Length - 1] &= (byte)(Math.Pow(2, maskLength) - 1);
            n = new BigInteger(bytes);
        }
        while (n > max);
        
        n += shift;
        return n;
    }
    
    public static BigInteger GCD(BigInteger n, BigInteger m)
    {
        while (n != 0)
        {
            BigInteger temp = n;
            n = m % n;
            m = temp;
        }
        return m;
    }
    
    public static BigInteger GCD(BigInteger n, BigInteger m,
                                 out BigInteger x, out BigInteger y)
    {
        BigInteger x0 = 1, x1 = 0;
        BigInteger y0 = 0, y1 = 1;
        
        while (m != 0)
        {
            BigInteger q, r;
            q = BigInteger.DivRem(n, m, out r);
            
            n = m;
            m = r;
            
            BigInteger x2 = x0 - q * x1;
            x0 = x1;
            x1 = x2;
            
            BigInteger y2 = y0 - q * y1;
            y0 = y1;
            y1 = y2;
        }
        
        x = x0;
        y = y0;
        return n;
    }
}
​

Input
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
║ 5 │ 3 │ 0 ║ 0 │ 7 │ 0 ║ 0 │ 0 │ 0 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 6 │ 0 │ 0 ║ 1 │ 9 │ 5 ║ 0 │ 0 │ 0 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 0 │ 9 │ 8 ║ 0 │ 0 │ 0 ║ 0 │ 6 │ 0 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║ 8 │ 0 │ 0 ║ 0 │ 6 │ 0 ║ 0 │ 0 │ 3 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 4 │ 0 │ 0 ║ 8 │ 0 │ 3 ║ 0 │ 0 │ 1 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 7 │ 0 │ 0 ║ 0 │ 2 │ 0 ║ 0 │ 0 │ 6 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║ 0 │ 6 │ 0 ║ 0 │ 0 │ 0 ║ 2 │ 8 │ 0 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 0 │ 0 │ 0 ║ 4 │ 1 │ 9 ║ 0 │ 0 │ 5 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 0 │ 0 │ 0 ║ 0 │ 8 │ 0 ║ 0 │ 7 │ 9 ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝

Output
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
║ 5 │ 3 │ 4 ║ 6 │ 7 │ 8 ║ 9 │ 1 │ 2 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 6 │ 7 │ 2 ║ 1 │ 9 │ 5 ║ 3 │ 4 │ 8 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 1 │ 9 │ 8 ║ 3 │ 4 │ 2 ║ 5 │ 6 │ 7 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║ 8 │ 5 │ 9 ║ 7 │ 6 │ 1 ║ 4 │ 2 │ 3 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 4 │ 2 │ 6 ║ 8 │ 5 │ 3 ║ 7 │ 9 │ 1 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 7 │ 1 │ 3 ║ 9 │ 2 │ 4 ║ 8 │ 5 │ 6 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║ 9 │ 6 │ 1 ║ 5 │ 3 │ 7 ║ 2 │ 8 │ 4 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 2 │ 8 │ 7 ║ 4 │ 1 │ 9 ║ 6 │ 3 │ 5 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 3 │ 4 │ 5 ║ 2 │ 8 │ 6 ║ 1 │ 7 │ 9 ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝

Cached Result
Last Run:	6:09:05 pm
Compile:	0.737s
Execute:	0.021s
Memory:	1.39Mb
CPU:	0.141s

View IL Code