Генератор псевдослучайных чисел с использованием алгоритма Blum Blum Shub - PullRequest
Новая
       51

Генератор псевдослучайных чисел с использованием алгоритма Blum Blum Shub

3 голосов
/ 01 июня 2019

Нам необходимо реализовать алгоритм Blum Shum Shub в генераторе псевдослучайных чисел.Я пытался найти реализации в C #, чтобы получить представление, но безуспешно.Некоторые методы, которые мы должны реализовать, недостаточно ясны (или, может быть, я не совсем понимаю, о чем они просят).

Кто-нибудь может помочь с кодом или, может быть, примером подобным образом?Мне сложнее понять концепции из текста. Любая помощь будет принята!

Сначала я попытался следовать логике вопроса.С небольшим прогрессом я начал искать в Интернете лучшие объяснения и, возможно, найти реализации для лучшего понимания.Наконец, я попытался заполнить некоторые из запрошенных методов тем, что, по моему мнению, имело смысл. 

static long seed = 6367859;
static long p = 3263849;
static long q = 1302498943;
static long m = p*q;

// Generates a random bit i.e. 0 or 1 using the Blum Blum Shub Algorithm and the Least Significant Bit
private byte generateRandomBit(){ }

// Method to generate a single positive 32 bit random number using the Blum Blum Shub Algorithm.
// The generateRandomBit() method is used to generate the random bits that make up the random number
// Not complete!!
public int GenerateNextRandomNumber()
{
    int nextRandomNumber = (int)((p * seed + q) % m);

    seed = nextRandomNumber;

    return nextRandomNumber;
}

// Generates a random number between min and max.
// The GenerateNextRandomNumber() method must be used to generate the initial random number which must then be manipulated (if necessary) to be between min and max
public int GenerateNextRandomNumber(int min, int max){ }

// Uses the GenerateNextRandomNumber Method to generate a sequence of Random Numbers between the minimum and the maximum value using the Blum Blum Shub Algorithm
public int[] GenerateRadmonSequence(int n, int min, int max)
{
    int[] sequence = new int[n];

    for (int i = 0; i < n; i++)
    {
        int randNum = Math.Abs(GenerateNextRandomNumber());

        randNum = min + randNum % (max + 1 +- min);
        sequence[i] = randNum;
    }

    return sequence;
}

Результатом должно быть создание последовательности чисел от мин до макс.

Ответы [ 2 ]

0 голосов
/ 02 июня 2019

А как насчет этой реализации: 

public class BlumBlumShub
{
    private readonly ulong m;
    private ulong x;

    public BlumBlumShub(int m, int seed)
    {
        this.m = (ulong) m;
        x = (ulong)seed;
    }

    public int Next()
    {
        x = (x * x) % m;
        return (int)x;
    }
}

ссылка

Редактировать: Если вам действительно нужно очень большое число, вы можете легко адаптировать его: 

public class BlumBlumShub
{
    private readonly BigInteger m;
    private BigInteger x;

    public BlumBlumShub(BigInteger m, BigInteger seed)
    {
        this.m = m;
        x = seed;
    }

    public BigInteger Next()
    {
        x = (x * x) % m;
        return x;
    }
}
0 голосов
/ 02 июня 2019

Нет, вы не можете использовать длинные для этого типа ГСЧ, это в значительной степени требует математики произвольной точности.А то, что вы реализовали, на самом деле выглядит как линейный конгруэнтный генератор , а не алгоритм Blum Blum Shub .

Вот код для запуска, .NET Core 2.2,x64 Win10.Я использую BigInteger, правильный алгоритм и четность, чтобы получить следующий случайный бит.Вы также можете использовать младший бит для случайного бита. 

using System;
using System.Numerics;

namespace BlumBlumSnub
{
    class Program
    {
        public static readonly BigInteger p = 3263849;
        public static readonly BigInteger q = 1302498943;
        public static readonly BigInteger m = p*q;

        public static BigInteger next(BigInteger prev) {
            return (prev*prev) % m;
        }

        public static int parity(BigInteger n) {
            BigInteger q = n;
            BigInteger count = 0;
            while (q != BigInteger.Zero) {
                count += q & BigInteger.One;
                q >>= 1;
            }
            return ((count & BigInteger.One) != BigInteger.Zero) ? 1 : 0; // even parity
        }

        public static int LSB(BigInteger n) {
            return ((n & BigInteger.One) != BigInteger.Zero) ? 1 : 0;
        }

        static void Main(string[] args)
        {
            BigInteger seed = 6367859;

            BigInteger xprev = seed;
            for(int k = 0; k != 100; ++k) {
                BigInteger xnext = next(xprev);
                int bit = parity(xnext); // extract random bit from generated BBS number using parity,
                // or just int bit = LSB(xnext);
                Console.WriteLine($"Bit = {bit}");
                xprev = xnext;
            }
        }
    }
}
...