Re: Math.random() algorithm

In comp.lang.javascript message <iN-dnUtm0u-efUDb4p2dnAA@xxxxxxxxxxxx>,
Tue, 4 Sep 2007 18:50:15, Randy Webb <HikksNotAtHome@xxxxxxx> posted:
Johannes Baagoe said the following on 9/4/2007 1:22 PM:
Erwin Moller:

Personally I WOULD go serverside if the 'quality' of the random
numbers
is important for your current task.
Yes, it does seem to be the only reliable way to go :-(

If all numbers are issued by a single server, the task is trivial, as
numbers can be issued in sequence. ISTM clear that the OP needs
uniqueness in numbers issued by independent, non-communicating machines;
and AFAICS great randomness is the only possibility for that.

Here, the reasons for using local servers can be that servers are less
likely to be suborned, or that greater computer-linguistic power can be
used there.

You didn't tell us why you need 256 bits of entropy,
I want a standard way to assign a unique id to every single XML
element
past, present and future. It makes DOM manipulations, XML database updates
and many other things so much safer and easier that I am quite prepared to
pay the price in inflated documents.

The only way to ensure that the ID will be unique - across documents -
is to predefine the list of all possible ID'es you want to use, then
remove them from the list as they are used. Otherwise, there is a
chance (albeit small) that it could get duplicated. The only way to
track that is on the server. Starting with a string 8 characters long,
limited to a-z and A-Z and issuing 100 of them every second, it would
take you roughly 16000 years to issue them all. How much more unique do
you need?

A list method means a single source of identifiers, for which issuing in
numerical order suffices (the bits can however be systematically
permuted or flipped so that the sequence is not obvious from samples).
Trivial, but IMHO inapplicable.

256 bits may be overkill, but with the birthday paradox, it seems prudent.
(Any thoughts on the proper number?)


There are of the general order of 2^256 particles in the observable
universe (check that), which sets a limit on the number of N-bit
identifiers that can possibly exist at any one time. Simultaneous
existence is a prerequisite for detectable collision. That gives an
upper limit.

If a computer is to generate a single unique ID unaided, the ID must be
properly random. But subsequent IDs can be in a pseudo-random sequence
starting from that, which could be quicker. The initial number might be
issued at manufacture (but consider that restoring a system needs a new
number), or at boot.

There's no great difficulty, as the OP probably has realised, in
generating a sequence of 256-bit pseudo-random numbers on a PC in
javascript. Such numbers can be stored in 16 Numbers, which can be
multiplied exactly, so the standard algorithm can be implemented by old-
style school arithmetic. A shift-register-based algorithm would be even
easier. Speed should be adequate. Theory may supply suitable constants
/ settings.

The problem lies in getting enough apparent randomness to initialise the
sequence locally.

IIRC, some CPUs do contain a true random-bit generator; it will be
inaccessible by standard javascript, but a ActiveX or other addition
might be able to use it.


--
(c) John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v6.05 IE 6
news:comp.lang.javascript FAQ <URL:http://www.jibbering.com/faq/index.html>.
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
.

Relevant Pages

  • Re: Tom Porterfield MS-MVP?
    ... > Let me begin with the fact that I have the utmost respect ... one reason only. ... to the posts by the server. ... Your first post (sequence 98349): ...
    (microsoft.public.windowsxp.security_admin)
  • Re: Pine sorting
    ... How does pine figure out when a message arrives at the server? ... it gets a new sequence number and UID. ... So do you know which method Pine uses -- sequence number or UID? ...
    (comp.mail.pine)
  • [NT] LiteServe URL Decoding DoS
    ... The following security advisory is sent to the securiteam mailing list, and can be found at the SecuriTeam web site: http://www.securiteam.com ... Web, email and FTP server. ... A vulnerability in the way the program decodes URL allows remote ... decode sequence does not specify a legitamite hexadecimal sequence. ...
    (Securiteam)
  • Re: Transaction processing advice
    ... the sequence is as follows: ... PayPal handles sending the emails to the customer and the seller. ... I set up something similar with the CC server and my server sending emails on confirmation, at least send yourself an email so you can see them come in pairs & know it all worked. ...
    (comp.lang.php)
  • =?iso-8859-1?q?Re:_Kolmorgorov_Complexity_and_Kim_=D8yhus?=
    ... >>Sure a protein string could be generated from by organic Turing machine ... >>For example, a proteins sequence, like a lactase sequence, could indeed ... > proper compression. ... >>The notion of randomness is dependent upon chaos. ...
    (talk.origins)