Генерация повторяемого псевдослучайного числа на основе координат

Question

Мне нужно генерировать повторяемые псевдослучайные числа на основе набора координат, чтобы при заданном начальном значении я всегда генерировал одно и то же значение для конкретной координаты.

Я подумал, что я бы использовал что-то вроде этого для семян:

/* 64bit seed value*/
struct seed_cord {
    uint16 seed;
    uint16 coord_x_int;
    uint16 coord_y_int;
    uint8  coord_x_frac;
    uint8  coord_y_frac;
}

Где coord_x_int - целочисленная часть координаты, а дробная часть задается как coord_x_frac / 0xFF. seed - это случайно заданное значение.

Но я должен признать, что пытаться понять все тонкости ГПНГ немного ошеломляет. Что будет хорошим генератором для того, что я пытаюсь?

Я протестировал PRNG в Java с использованием этой схемы в быстром скриптовом скрипте со следующим результатом:

Очевидно, это едва ли приличная случайность.

Я использовал скрипт:

import java.awt.image.BufferedImage
import javax.imageio.ImageIO

short shortSeed = new Random().next(16) as short

def image = new BufferedImage(512, 512, BufferedImage.TYPE_BYTE_GRAY)
def raster = image.getRaster()

//x
(0..1).each{ x ->
(0..255).each{ xFrac ->
//y
(0..1).each{ y ->
(0..255).each{ yFrac ->

long seed = (shortSeed as long) << 48 |
            (x as long)         << 32 |
            (y as long)         << 16 |
            (xFrac as long)     <<  8 |
            (yFrac as long)

def value = new Random(seed).next(8)
raster.setSample( (x? xFrac+256 : xFrac), (y? yFrac+256 : yFrac), 0 , value)

}}}}

ImageIO.write(image, "PNG", new File("randomCoord.png"))

Answer 1

Если вы на самом деле смотрите только на 512x512, то это эээ ... 2 ¹⁸ пикселей, которые вас интересуют.

Там достаточно места для такого рода населения схороший оле MD5 (выход 128 бит).

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

Теперь вы можете делать всякие забавные вещи, если вы параноик.Начните с хэша ваших координат, затем передайте результат в безопасный генератор случайных чисел (java.security.SecureRandom).Затем хешируйте его 1000 раз с солью, которая объединяется в ваш день рождения (x + y) раз.

Шутки в сторону, генераторы случайных чисел не обязательно имеют сильно отличающиеся результаты, основанные на небольших вариациях начального числа.Они спроектированы так, чтобы иметь действительно очень длинную цепочку сгенерированных чисел, прежде чем они начнут повторяться, при этом эти цепочки довольно равномерно распределены по пространству чисел.

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

Answer 2

Вы можете использовать шифрование для этой задачи, например, AES. Используйте ваше семя в качестве пароля, структурируйте с координатами как блок данных и зашифруйте его Зашифрованный блок будет вашим случайным числом (вы можете использовать любую его часть). Этот подход используется в Fortuna PRNG . Тот же подход можно использовать для шифрования диска, где требуется произвольный доступ к данным (см. Шифрование с произвольным доступом с помощью AES В режиме счетчика с использованием Fortuna PRNG: )

Answer 3

Я бы взял программу, подобную этой, которую я создал, и затем изменил бы ее, чтобы выбрать координаты:

REM $DYNAMIC
COMMON SHARED n%, rbuf%, sz%, sw%, p1$
DECLARE SUB initialize ()
DECLARE SUB filbuf ()
DECLARE SUB setup ()
DECLARE FUNCTION Drnd# ()
DECLARE SUB core ()
DECLARE SUB modify ()
DIM SHARED pad1(340) AS STRING * 1
DIM SHARED trnsltr(66) AS STRING * 1 ' translates a 0-67 value into a pad character
DIM SHARED trnslt(255) AS INTEGER  'translates a pad value to 0-67 value -1 if error
DIM SHARED moders(26) AS INTEGER 'modding function prim number array
DIM SHARED moders2(26) AS INTEGER 'modding function prim number array
DIM SHARED ranbuf(1 TO 42) AS DOUBLE 'random number buffer if this is full and rbuf %>0
REM then this buffer is used to get new random values
REM rbuf% holds the index of the next random number to be used
REM subroutine setup loads the prime number table
REM from the data statements to be used
REM as modifiers in two different ways (or more)
REM subroutine initialize primes the pad array with initial values
REM transfering the values from a string into an array then
REM makes the first initial scrambling of this array
REM initializing pad user input phase:
CLS
INPUT "full name of file to be encrypted"; nam1$
INPUT "full name of output file"; nam2$
INPUT "enter password"; p2$
rbuf% = 0
n% = 0: sw% = 0
p3$ = STRING$(341, "Y")
p1$ = "Tfwd+-$wiHEbeMN<wjUHEgwBEGwyIEGWYrg3uehrnnqbwurt+>Hdgefrywre"
p1$ = p2$ + p1$ + p3$
PRINT "hit any key to continue any time after a display and after the graphic display"
p1$ = LEFT$(p1$, 341)
sz% = LEN(p1$)
CALL setup
CALL initialize
CLS
ibfr$ = STRING$(512, 32)
postn& = 1
OPEN nam1$ FOR BINARY AS #1
OPEN nam2$ FOR BINARY AS #2
g& = LOF(1)
max& = g&
sbtrct% = 512
WHILE g& > 0
LOCATE 1, 1
PRINT INT(1000 * ((max& - g&) / max&)) / 10; "% done";
IF g& < 512 THEN
ibfr$ = STRING$(g&, 32)
sbtrct% = g&
END IF
GET #1, postn&, ibfr$
FOR ste% = 1 TO LEN(ibfr$)
geh% = INT(Drnd# * 256)
MID$(ibfr$, ste%, 1) = CHR$(geh% XOR ASC(MID$(ibfr$, ste%, 1)))
NEXT ste%
PUT #2, postn&, ibfr$
postn& = postn& + sbtrct%
g& = g& - sbtrct%
WEND
CLOSE #2
CLOSE #1
PRINT "hit any key to exit"
i$ = ""
WHILE i$ = "": i$ = INKEY$: WEND
SYSTEM
END
DATA 3,5,7,9,11,13,17,19
DATA 23,29,33,37,43,47
DATA 53,59,67,71,73,79,83
DATA 89,91,97,101,107,109
DATA 43,45,60,62,36

REM $STATIC
SUB core
REM shuffling algorythinm
FOR a% = 0 TO 339
m% = (a% + 340) MOD 341: bez% = trnslt(ASC(pad1(340)))
IF n% MOD 3 = 0 THEN pad1(340) = trnsltr((2 * trnslt(ASC(pad1(a%))) + 67 -   trnslt(ASC(pad1(m%)))) MOD 67)
IF n% MOD 3 = 1 THEN pad1(340) = trnsltr((2 * (67 - trnslt(ASC(pad1(a%)))) + 67 - trnslt(ASC(pad1(m%)))) MOD 67)
IF n% MOD 3 = 2 THEN pad1(340) = trnsltr(((2 * trnslt(ASC(pad1(a%))) + 67 - trnslt(ASC(pad1(m%)))) + moders(n% MOD 27)) MOD 67)
pad1(a% + 1) = pad1(m%): n% = (n% + 1) MOD 32767
pad1(a%) = trnsltr((bez% + trnslt(ASC(pad1(m%)))) MOD 67)
NEXT a%
sw% = (sw% + 1) MOD 32767
END SUB

FUNCTION Drnd#
IF rbuf% = 0 THEN
CALL core
CALL filbuf
IF sw% = 32767 THEN CALL modify
END IF
IF rbuf% > 0 THEN yut# = ranbuf(rbuf%)
rbuf% = rbuf% - 1
Drnd# = yut#
END FUNCTION

SUB filbuf
q% = 42: temp# = 0
WHILE q% > 0
FOR p% = 1 TO 42
k% = (p% - 1) * 8
FOR e% = k% TO k% + 7
temp# = temp# * 67: hug# = ABS(trnslt(ASC(pad1(e%)))): temp# = temp# + hug#
NEXT e%
IF temp# / (67 ^ 8) >= 0 AND q% < 43 THEN
ranbuf(q%) = temp# / (67 ^ 8): q% = q% - 1
END IF
temp# = 0
NEXT p%
WEND
rbuf% = 42
END SUB

SUB initialize
FOR a% = 0 TO 340
pad1(a%) = MID$(p1$, a% + 1, 1)
NEXT a%
FOR a% = 0 TO 340
LOCATE 1, 1
IF a% MOD 26 = 0 THEN PRINT INT((340 - a%) / 26)
sum% = 0
FOR b% = 0 TO 340
qn% = INT(Drnd# * 81)
op% = INT(qn% / 3)
qn% = qn% MOD 3
IF qn% = 0 THEN sum% = sum% + trnslt(ASC(pad1(b%)))
IF qn% = 1 THEN sum% = sum% + (67 + 66 - trnslt(ASC(pad1(b%)))) MOD 67
IF qn% = 2 THEN sum% = sum% + trnslt(ASC(pad1(b%))) + moders(op%)
NEXT b%
pad1(a%) = trnsltr(sum% MOD 67)
NEXT a%
n% = n% + 1
END SUB

SUB modify
REM modifier shuffling routine
q% = 26
temp# = 0
WHILE q% > -1
FOR p% = 1 TO 27
k% = (p% - 1) * 4 + 3
FOR e% = k% TO k% + 3
temp# = temp# * 67
hug# = ABS(trnslt(ASC(pad1(e%))))
temp# = temp# + hug#
NEXT e%
IF (temp# / (67 ^ 4)) >= 0 AND q% > -1 THEN
SWAP moders(q%), moders(INT(27 * (temp# / (67 ^ 4))))
q% = q% - 1
END IF
temp# = 0
NEXT p%
WEND
END SUB

SUB setup
FOR a% = 0 TO 26
READ moders(a%)
moders2(a%) = moders(a%)
NEXT a%
REM setting up tables and modder functions
FOR a% = 0 TO 25
trnsltr(a%) = CHR$(a% + 97)
trnsltr(a% + 26) = CHR$(a% + 65)
NEXT a%
FOR a% = 52 TO 61
trnsltr(a%) = CHR$(a% - 4)
NEXT a%
FOR a% = 62 TO 66
READ b%
trnsltr(a%) = CHR$(b%)
NEXT a%
FOR a% = 0 TO 255
trnslt(a%) = -1
NEXT a%
FOR a% = 0 TO 66
trnslt(ASC(trnsltr(a%))) = a%
NEXT a%
RESTORE
END SUB

вызов drand # дает вам случайные числа от 0 до 1, просто умножьте это на необходимый вам диапазон для каждого необходимого вектора. P2 $ - пароль, который передается в обработчик паролей, который объединяет его с некоторыми другими случайными символами, а затем с заглавными буквами размер до определенного предела p1 $ - это место, где содержится последний измененный пароль сам дранд # вызывает другую подпрограмму, которая на самом деле является клоном самой себя с некоторым перемешиванием Сортировки, которые работают для обеспечения того, чтобы производимые числа были действительно случайными, есть также таблица значений, которые добавляются к добавляемым значениям, и все это в целом делает ГСЧ намного более случайным, чем без.

этот RNG обладает очень высокой чувствительностью к небольшим различиям в первоначально установленном пароле, однако вы должны сделать первоначальный вызов для установки и инициализации, чтобы «загрузить» генератор случайных чисел, этот RNG будет генерировать действительно случайные числа, которые пройдут все тесты на случайность более случайным, чем перетасовывание колоды карт вручную, более случайным, чем бросание костей .. надеюсь, что это поможет с использованием того же пароля приведет к той же последовательности векторов

Эта программа должна быть немного изменена, чтобы выбирать случайные векторы, а не в настоящее время он используется в качестве генератора случайных чисел с безопасным шифрованием ...

Answer 4

Большинство языков имеют пакет PRNG (или два), который позволяет инициализировать генератор с определенным начальным числом. PRNG также часто можно найти как часть более крупного криптографического пакета; они, как правило, немного сильнее, чем в библиотеках общего назначения.