Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #27012

Re: LC53, a respectable random generator?

Show all headers | View raw

Albert van der Horst wrote:

> (I cancelled a post where I said that an LC53 type always has
> a period of p-1. What was I thinking?)

Don't know, but actually it is pretty simple to check candidates for 
primitive roots of LC53.  Faktor p-1:

22605091*19*5*2 = 2^32-5

So for all four prime factors q, you have to test if your candidate g is

g^{(p-1)/q} mod p !== 1.

This can be done quickly.  You don't have to search that long to find a 
primitive root.

Note that Hugh's g is 2^32-333333333, don't confuse things, the sign matters 
(writing it as a negative number as Hugh does is confusing, though).  It 
*is* a primitive root of 2^32-5.  If you want to find primitive roots for 
LC53-style generators quickly, here's some code (factoring done by an 
external program, you migth want to add a sieve up to 2^16 to do the 
factoring right in the program itself):

\ Check primitive roots for lc53

$100000000 5 - Constant m

: *z ( a b -- c ) um* m um/mod drop ;
: a^b ( a b -- result ) >r 1 swap
    BEGIN  r@ 1 and IF  tuck *z swap  THEN
	dup *z r> 2/ dup WHILE  >r  REPEAT
    2drop ;

: u/ ( a b -- q )  0 swap um/mod nip ;

: checkprim ( a -- flag )
    dup m 1- 22605091 u/ a^b 1 = >r
    dup m 1-       19 u/ a^b 1 = r> or >r
    dup m 1-        5 u/ a^b 1 = r> or >r
        m 1-        2 u/ a^b 1 = r> or 0= ;

BTW: Chances are good that the prime factors of p-1 are primitive roots.  In 
this case, only 5 isn't a primitive root.  This is why people who calculate 
numbers for Diffie Hellman key exchange use a prime p in the form that 
(p-1)/2 is another prime, *and* a primitive root of p (that's just one check 
more).  This reduces the search space, and you can transmit the two 
parameters needed for Diffie Hellman in just one number - you derive the 
root g from the modulus p.

In these cases, p is a number with several thousand bits, and we still know 
that (p-1)/2 is a primitive root, and can check that quite fast.

LC53 is a maximum period linear congruent random number generator - so far, 
so good.  It has the usual problems of LCGs, so it doesn't pass any serious 
randomness test suite.  It is certainly not worse than others, but it 
definitely is slower than the mod 2^cellbits ones.  It is just a bit faster 
as the hash-based PRNG I use in Gforth-git now (benchmarked on 64 bit 
machines), which does return 64 bit numbers on a 64 bit machine, and so far 
passed all randomness tests I ran from the TestU01 suite (I didn't run the 
very time consuming DieHarder test).

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-23 16:25 +0000
  Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-23 17:34 -0800
    Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-23 19:03 -0800
    Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-24 04:58 +0000
  Re: LC53, a respectable random generator? "Rod Pemberton" <dont_use_email@xnohavenotit.cnm> - 2013-11-24 04:57 -0500
    Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-24 14:17 +0000
      Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-24 08:12 -0800
        Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-24 16:46 +0000
        Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-24 23:53 +0100
          Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-24 15:41 -0800
            Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 17:57 -0800
            Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-25 19:32 +0000
              Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-25 14:22 -0800
              Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-26 00:20 +0100
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-26 03:29 +0000
                Re: LC53, a respectable random generator? thomas.bartscher@gmail.com - 2013-11-25 23:08 -0800
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 05:06 -0800
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-26 14:03 +0000
                Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-26 21:59 +0100
                Re: LC53, a respectable random generator? thomas.bartscher@gmail.com - 2013-11-28 01:32 -0800
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-25 19:43 -0800
              Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-25 19:31 -0800
              Re: LC53, a respectable random generator? "Elizabeth D. Rather" <erather@forth.com> - 2013-11-25 19:24 -1000
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 05:17 -0800
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-26 14:21 +0000
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-28 18:49 -0800
            Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-25 13:52 -0800
          Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 18:03 -0800
          Re: LC53, a respectable random generator? Matthias Koch <matthias.koch@hot.uni-hannover.de> - 2013-11-25 13:41 +0100
            Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-25 10:23 -0800
              Re: LC53, a respectable random generator? Howerd <howerdo@yahoo.co.uk> - 2013-11-25 13:43 -0800
                Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-25 15:16 -0800
                Re: LC53, a respectable random generator? Howerd <howerdo@yahoo.co.uk> - 2013-11-26 13:38 -0800
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 20:42 -0800
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 11:46 +0000
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-27 18:35 -0800
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 21:41 -0800
                Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-27 03:21 -0600
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 15:37 +0000
                Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-27 23:01 +0100
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 23:39 +0000
                Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-28 05:41 -0600
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-28 13:47 +0000
                Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-28 09:10 -0600
                Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-28 16:22 +0100
                Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-28 09:34 -0600
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-28 18:39 -0800
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 16:44 +0000
            Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-25 19:51 +0100
      Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 11:13 -0800
        Re: LC53, a respectable random generator? Hans Bezemer <the.beez.speaks@gmail.com> - 2013-11-25 09:52 +0100
  Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 13:07 -0800
    Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-25 02:18 +0000
      Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 19:36 -0800
  Re: LC53, a respectable random generator? "Ed" <invalid@invalid.com> - 2013-11-26 12:57 +1100
    Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 21:25 -0800
    Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 15:48 +0000
  Re: LC53, a respectable random generator? Mark Wills <markrobertwills@yahoo.co.uk> - 2013-11-27 01:10 -0800
    Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-27 03:29 -0600
      Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-27 19:49 -0800
        Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-28 15:57 +0100
          Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-28 18:14 -0800

csiph-web