32 bit random numbers

Anything QL Software or Programming Related.
stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

32 bit random numbers

Post by stevepoole »

Hi Folks,

Does anyone know how to generate accurate 32_bit random numbers ?

I have been toying with the idea for decades, and have now come up with a fully tested routine, (in fact for numbers up to 31 bits, as 32 bits imply negative numbers).

Tested statistically, It works fine on QPC2 and my SGC QL, (although the latter runs 124 times slower !)

The worst case for numbers (in a range) is 3 times slower than the best case.

It would be interesting to know how it compares to other routines ?

I will put it on the forum after a little more tweaking of the associated graphical output, (which is not too easy to scale with 31 bit randoms).

Steve.
__________


User avatar
bwinkel67
QL Wafer Drive
Posts: 1187
Joined: Thu Oct 03, 2019 2:09 am

Re: 32 bit random numbers

Post by bwinkel67 »

Park-Miller is a 31 bit Linear Congruent Random Number Generator of the form:

s = ( s * p1 + P2 ) % N

where

P1 = 16807 (i.e. 7^5)
P2 = 1
N = 2147483647 (i.e. 2^31 - 1)

Note that % is the modulus operator (don't know what it is in SuperBASIC)


User avatar
XorA
Site Admin
Posts: 1359
Joined: Thu Jun 02, 2011 11:31 am
Location: Shotts, North Lanarkshire, Scotland, UK

Re: 32 bit random numbers

Post by XorA »

Random numbers are where DES/AES come in handy.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: 32 bit random numbers

Post by stevepoole »

Hi Bwinkel,

Congruent random number generators are for PSEUDO randoms... We want true random numbers.

The method I have devised could be adopted for ANY number of bits, but not on QPC2. ( But possible in C++ , on 64bit machines or better).

Is the park-Miller routine available for QL systems ?

What are DES & AES ?

Steve.
__________


User avatar
XorA
Site Admin
Posts: 1359
Joined: Thu Jun 02, 2011 11:31 am
Location: Shotts, North Lanarkshire, Scotland, UK

Re: 32 bit random numbers

Post by XorA »

stevepoole wrote:Hi Bwinkel,

Congruent random number generators are for PSEUDO randoms... We want true random numbers.

The method I have devised could be adopted for ANY number of bits, but not on QPC2. ( But possible in C++ , on 64bit machines or better).

Is the park-Miller routine available for QL systems ?

What are DES & AES ?
Encryption algorithms, you feed a little bit of entry to them, and because of the way they work they must increase the entropy of the output (otherwise they would be too easy to crack).

I've worked on certified security systems where all the randows were generated by this method.

Given that modern CPUs tend to contain true random generators and AES in hardware its a really quick and easy way to generate lots of high entropy data!


User avatar
tofro
Font of All Knowledge
Posts: 2688
Joined: Sun Feb 13, 2011 10:53 pm
Location: SW Germany

Re: 32 bit random numbers

Post by tofro »

stevepoole wrote: Congruent random number generators are for PSEUDO randoms... We want true random numbers.
If you have invented a "true random number" generator entirely in software (without an external source of entropy), you might have solved a problem that generations of computer scientists have proven to be unsolvable (a deterministic machine like a CPU can't produce non-deterministic results).


ʎɐqǝ ɯoɹɟ ǝq oʇ ƃuᴉoƃ ʇou sᴉ pɹɐoqʎǝʞ ʇxǝu ʎɯ 'ɹɐǝp ɥO
stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: 32 bit random numbers

Post by stevepoole »

Hi,
Here is the QL 31bit random number generator, which does not directly use a congruency method. It is deterministic, but only uses RND(1) in its core.
_______
UNZIP and LOAD, (120 QL=1 or QL=0 for emulators, 210 mn & mx set test rangs, m is number of test cycles. RUN !!
_______
At top_left see the numbers generated, by the lower & upper limits, Bottom_left see number of bits and time per test_cycle.
_______
upper and lower white lines show the mn & mx ranges, horizontal speccles show trace of rank_values, ( I have improved but complicated statistical bar charts).
_______
timings are done to compare ranges and machines relatively, No way yet to optimise loop2 without getting results horribly biased.
_______
It is not as fast as congruency methods, but I cannot detect any biases, and it is available for QL systems NOW.
_______
Steve.
random_31bit_bas.zip
(992 Bytes) Downloaded 57 times


User avatar
bwinkel67
QL Wafer Drive
Posts: 1187
Joined: Thu Oct 03, 2019 2:09 am

Re: 32 bit random numbers

Post by bwinkel67 »

stevepoole wrote:Hi Bwinkel,

Congruent random number generators are for PSEUDO randoms... We want true random numbers.

The method I have devised could be adopted for ANY number of bits, but not on QPC2. ( But possible in C++ , on 64bit machines or better).
Ah, didn't know you want true randomness. Generally speaking those aren't as useful in computing as pseudo random ones are since there is no repeatability and for cryptography and software engineering you want that. That said, true randomness is pretty intriguing and fun to implement. It will be neat to see your implementation.
stevepoole wrote: Is the park-Miller routine available for QL systems ?
It has not been implemented in any ROM if that's what you are asking. I think I had it briefly in ZXSimulator but went with a 16-bit equivalent that matches what the ZX81 used.
stevepoole wrote: What are DES & AES ?

Steve.
__________
DES stands for Data Encryption Standard and AES stands for Advanced Encryption Standard. They are both block ciphers with AES being the current standard used throughout the internet/web. Neither is a pseudo random number generator and neither directly uses one in their computation but may apply one when encrypting multiple blocks (various techniques for that).

Here's a good reference on cryptography (I use it in an introductory cryptography course). It briefly covers random number generators (pseudo, not real) but gives complete description of DES and AES. DES could be implemented on a QL as it is a pretty straightforward bit-twiddling algorithm (bit twiddling with purpose :-/)

These are the relevant chapters that cover the topics in this post (the remaining chapters cover public-key encryption.
Ch1-Ch5.pdf
(1.6 MiB) Downloaded 53 times


User avatar
XorA
Site Admin
Posts: 1359
Joined: Thu Jun 02, 2011 11:31 am
Location: Shotts, North Lanarkshire, Scotland, UK

Re: 32 bit random numbers

Post by XorA »

repeatability and for cryptography and software engineering you want that
Hell no, crypto really likes true random for exactly the opposite of that reason.


User avatar
bwinkel67
QL Wafer Drive
Posts: 1187
Joined: Thu Oct 03, 2019 2:09 am

Re: 32 bit random numbers

Post by bwinkel67 »

XorA wrote:
repeatability and for cryptography and software engineering you want that
Hell no, crypto really likes true random for exactly the opposite of that reason.
The problem with true randomness is that when you encrypt something you can't decrypt it. What you want is the appearance of true randomness. There are lots of tests in the field of cryptography (mathematics) to address that. But in the end, if you can'f find the needle in the haystack then it's kind of worthless. So you may be conflating the idea o true randomness with the idea of pseudo randomness having all the properties of true randomness, which is what you want.

Remember that cryptography is an algorithmic solution and implemented in software. Hardware implementations are just more efficient implementations of that but AES is implemented in your version of SSH and by that nature they can't be implementing true randomness, just the appearance of it.


Post Reply