On Sun, 10 Jul 2005 15:28:17 GMT, 'steven' wrote: Hi, Can you explain in layman terms why the MT (e.g. MT19937) isn't suitable for encryption purposes? Because it is a linear non-secure pseudorandom number generator. Makoto Matsumoto et al have a submitted cryptographically improved version of MT to the ECRYPT Stream Cipher Project: Hope that helps Wolfgang - In order to e-mail me a reply to this message, you will have to remove PLEASE.REMOVE from the address shown in the header or get it from (Free AES, CRC, Hash, and HMAC source for Pascal/Delphi) steven 10/7/2005, 10:55 น. 'Wolfgang Ehrhardt' wrote in message news:[email protected].
Python script that performs and cracks the Mersenne Twister PRNG - x64x6a/MersenneTwister.
On Sun, 10 Jul 2005 15:28:17 GMT, 'steven' wrote: HiCan you explain in layman terms why the MT (e.g. MT19937) isn't suitable for encryption purposes?
Because it is a linear non-secure pseudorandom number generator. Makoto Matsumoto et al have a submitted cryptographically improved version of MT to the ECRYPT Stream Cipher Project: Hope that helps Not really:-( Maybe I should have posed my question differently: Why is MT non-secure (while e.g. BBS is secure)? Thanx for replying however.
Steven Paul Rubin 10/7/2005, 11:01 น. 'steven' writes: Maybe I should have posed my question differently: Why is MT non-secure (while e.g. BBS is secure)?
Um, why are oranges orange (while e.g. Lemons are yellow)? MT was not designed as a cryptographic generator.
There's a straightforward way (described in the MT paper) to reconstruct the internal state. Remember where it says something like it's equidistributed in 623 dimensions? That means that if you start counting in 624 or more dimensions, all bets are off. That's different from a cryptographic generator, which can't be distinguished from uniform no matter how many dimensions you use. Herman Rubin 10/7/2005, 12:41 น. In article, There can be no 'cryptographic generator' in that sense which uses a computer program. This includes BBS, which to be sure has more dimensions, and is not linear.
Some of the seed programs for the Mersenne generator have been too simple. Has anyone been able to crack it given random seeding for all of the input, which would make it more than 19,000 seed bits?
- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Department of Statistics, Purdue University Phone: (765)494-6054 FAX: (765)494-0558 Paul Rubin 10/7/2005, 12:53 น. (Herman Rubin) writes: counting in 624 or more dimensions, all bets are off. That's different from a cryptographic generator, which can't be distinguished from uniform no matter how many dimensions you use.
There can be no 'cryptographic generator' in that sense which uses a computer program. This includes BBS, which to be sure has more dimensions, and is not linear. Well, I mean in a feasible amount of time on a real computer. That means there's no P-time distinguishing algorithm.
Whether BBS fits that description is an open problem. Some of the seed programs for the Mersenne generator have been too simple. Has anyone been able to crack it given random seeding for all of the input, which would make it more than 19,000 seed bits? I believe the MT paper says how to do that. David Wagner 10/7/2005, 13:42 น. Steven wrote: Can you explain in layman terms why the MT (e.g. MT19937) isn't suitable for encryption purposes?
(I'm not a cryptologist, nor a mathematician, so please type slowly) As has been noted, it's a linear shift register. But that doesn't really answer the question. Why are linear shift registers insecure? It is because there is a simple relationship between the successive 32-bit words of pseudorandom data that the Mersenne Twister produces. The relationship will allow those words to be in a sequence that does not exactly repeat itself for a very long time, but it only takes a short time to determine all the information you need to duplicate the entire sequence. The successive words of data give the entire internal state; in a secure keystream generator, the internal state is nearly impossible to derive from the outputs.
John Savard steven 12/7/2005, 1:25 น. George Marsaglia wrote: 'steven' wrote in message news:[email protected]. HiCan you explain in layman terms why the MT (e.g. MT19937) isn't suitable for encryption purposes?
TIA Steven (I'm not a cryptologist, nor a mathematician, so please type slowly) I have never had much interest in cryptographybut some of the work I have done on producing and testing randomness seems to be of interest to people in that field. I have seen frequent mention of the Mersenne Twister, which does very well in tests of randomness such as in the Diehard battery. A good part of its appeal seems to be that it has a very long period.
Far less complicated methods can be used to get much longer periods and as good or better results in tests of randomness, with simpler programs, and-at least to me-more attractive theory. Here is an example in C, with period some 10^33000 times as long as that of the Mersenne Twister: Do you have proff to such statements? Can you provide us with a paper please? JLC Cristiano 14/7/2005, 14:06 น. George Marsaglia wrote: Here is an example in C, with period some 10^33000 times as long as that of the Mersenne Twister: That could be interesting, but there is the proof that MT has a very good k-distribution, for example it is: (623,32)-distributed (1246,16)-distributed (2492,8)-distributed (9968,2)-distributed which could be useful in some application. Please, could you post some value for your generator? static unsigned long Q4096,c=362436; You say that your generator requires an initial seed 0.
George Marsaglia wrote: An initial seed c in the static array Q4096 should be assigned values before calls to the function CMWC4096otherwise the first few thousand returned values will be zeros. (That is consistent with the view that the choice of seeds merely chooses a random starting point in a huge circle of over 10^39460 base-(2^32-1) digits, (all possible 32-bit integers except for FFFFFFFF)). Failing to initialize the Q4096 array (set by default to 0's) merely provides a starting point at a long string of zeros, which should be occasionally encountered in any random string.) I tested your generator using Qi=0 for 0. I asked for the right seeding method because I.always. get bad results with this seeding: Qi= RDTSC% 0xffffffff the RDTSC function reads the time-stamp counter (a 64-bit model specific register which is incremented every clock cycle) of my AthlonXP 3000+ processor.
I get Q's like these: D749D65 D749E1B D749E8C D749EFD. D7BCD19 D7BCD89 D7BCDF9 D7BCE69 or 18B090EA 18B091A0 18B0922. 18B7ECC0 18B7ED30 18B7EDA0 18B7EE10 we have many fixed high order bits. I can seed your generator using many different sequences and.sistematically. it will fail the test. If I use Qi= RDTSC.
RDTSC% 0xffffffff which generates Q's like these: 8C84B61F 6287F9C5 D18A895D 408DCFD8. 34C63518 AF686DC2 2A0B5D4F A4AF03BD I.always. get good results. Why the latter method is 'better' than the former? Cristiano Simon Johnson 16/7/2005, 10:54 น.
In the simplest possible terms there is a difference between something producing a random looking distrubtion of bytes and producing a stream of bytes that is indistinguishable from a random source. The MT is an algorithm that passes the first test but not the second. It is easy to distinguish MT from a random source and this fact alone is considered a break of the MT. Fufilling the indistinguishability criteria is neccessary and sufficient for producing a secure stream-cipher.
Cristiano 16/7/2005, 12:00 น. Simon Johnson wrote: In the simplest possible terms there is a difference between something producing a random looking distrubtion of bytes and producing a stream of bytes that is indistinguishable from a random source. To me, 'random looking' seems = 'indistinguishable from a random source'. What do you mean? The MT is an algorithm that passes the first test but not the second. It is easy to distinguish MT from a random source and this fact alone is considered a break of the MT.
No general purpose test can distinguish the MT sequences from a random source. Fufilling the indistinguishability criteria is neccessary and sufficient for producing a secure stream-cipher. It's necessary but.not.
sufficient; a crypto (P)RNG must be also unpredictable. Cristiano Paul Rubin 16/7/2005, 12:13 น. 'Cristiano' writes: To me, 'random looking' seems = 'indistinguishable from a random source'. What do you mean? 'indistinguishable' means you have no practical way to tell which is which. No general purpose test can distinguish the MT sequences from a random source.
I don't know what you mean by 'general purpose test', but 'indistinguishable' you can't tell the difference using ANY test, not just general purpose tests. If, after studying the MT algorithm and source code for a year or two, you can come up with an MT-specific test based on the intimate details of how MT works, that distinguishes an MT stream from a random stream, MT is distinguishable. That said, MT is getting a bad rap here; it was designed be very fast and to have reasonable statistical properties for physical simulations and stuff like that.
It was never intended to be a stream cipher and its designers specifically advised people that it wasn't suitable as one. It's necessary but.not. sufficient; a crypto (P)RNG must be also unpredictable. If it was predictable, you obviously could distinguish it from a random source, so indistinguishabability is sufficient. [email protected] 16/7/2005, 12:13 น. Unruh 16/7/2005, 14:09 น.
'Simon Johnson' writes: In the simplest possible terms there is a difference between something producing a random looking distrubtion of bytes and producing a stream of bytes that is indistinguishable from a random source. The MT is an algorithm that passes the first test but not the second. It is easy to distinguish MT from a random source and this fact alone is considered a break of the MT. Fufilling the indistinguishability criteria is neccessary and sufficient for producing a secure stream-cipher.
Well, I am not sure that the second is actually a criterion at all. How, given simply the stream do you decide if it has been satisfied? If tomorrow I break say RC4 or AES, do you then say that the test is no longer satisfied but today it is?
Ie, this would seem to be not a test but a hope. Herman Rubin 16/7/2005, 14:25 น.
In article, Cristiano wrote: George Marsaglia wrote: An initial seed c in the static array Q4096 should be assigned values before calls to the function CMWC4096, otherwise the first few thousand returned values will be zeros. (That is consistent with the view that the choice of seeds merely chooses a random starting point in a huge circle of over 10^39460 base-(2^32-1) digits, (all possible 32-bit integers except for FFFFFFFF)).
Failing to initialize the Q4096 array (set by default to 0's) merely provides a starting point at a long string of zeros, which should be occasionally encountered in any random string.) I tested your generator using Qi=0 for 0 because I get many 0's followed by many 0xfffffffe's. The test is failed also when I initialize Q with some sort of counter or clock. But if I discard the first 4096.10000 values or more, the generator seems to pass the test.
Is there any method to initialize Q in the right way or the best thing is to always discard the first few thousand returned values? I would always initialize any pseudo-random generator with the output of at least a fair physical generator.
This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Department of Statistics, Purdue University Phone: (765)494-6054 FAX: (765)494-0558 Paul Rubin 16/7/2005, 14:30 น.
Unruh writes: It is easy to distinguish MT from a random source and this fact alone is considered a break of the MT. Fufilling the indistinguishability criteria is neccessary and sufficient for producing a secure stream-cipher. Well, I am not sure that the second is actually a criterion at all. Howgiven simply the stream do you decide if it has been satisfied? You're at the point where maybe you should look at a formal mathematical treatment. Bellare and Rogaway's lecture notes are a good place to start: If tomorrow I break say RC4 or AES, do you then say that the test is no longer satisfied but today it is? Ie, this would seem to be not a test but a hope.
That's the best anyone can do with our current state of knowledge. It's conjectured that AES can't be distinguished from a random permutation, where 'conjecture' means 'unsolved math problem'. Sometimes an unsolved problem gets solved and then it's unsolved yesterday and solved today. So, three things can happen with AES: 1) Someone proves AES is distinguishable from random. That's considered a break of the cipher even if it doesn't lead to practical security compromises in fielded applications. It's happened with many other ciphers (including RC4 and more recently SHA1) and might happen with AES.
That's bad for users but not that big a deal in a theoretical sense. Nobody really expects this (especially for a very fast and definite distinguisher) but it might happen.
2) Someone proves AES is indistinguishable. That's a HUGE result because it means the P vs. NP problem is solved. Nobody expects this and it will be a big surprise if it happens anytime soon.
3) Nobody proves anything. We keep on thinking and hoping, without definite proof, that AES is strong. This is the most likely way things will continue for a while. Unruh 16/7/2005, 14:35 น. 'Cristiano' writes: Simon Johnson wrote: In the simplest possible terms there is a difference between something producing a random looking distrubtion of bytes and producing a stream of bytes that is indistinguishable from a random source. To me, 'random looking' seems = 'indistinguishable from a random source'.
What do you mean? The MT is an algorithm that passes the first test but not the second.
It is easy to distinguish MT from a random source and this fact alone is considered a break of the MT. No general purpose test can distinguish the MT sequences from a random source. If it can be broken then it can be distinguished from a random source.
It has patterns which a random source would not have. Note that ALL prngs are different from random sources. They can be predicted, which a random source cannot. Fufilling the indistinguishability criteria is neccessary and sufficient for producing a secure stream-cipher. It's necessary but.not. sufficient; a crypto (P)RNG must be also unpredictable. A random source cannot be predicted.
And no PRNG is unpredictable. Just give me the algorithm and the (short) key and I can predict it forever. Now, can I figure out how to predict it just given the output alone? I do not know but I do know that there are very very strong patterns in the output based on the fact that it is generated by a PRNG. Cristiano Paul Rubin 16/7/2005, 15:04 น. Unruh writes: A random source cannot be predicted. And no PRNG is unpredictable.
Just give me the algorithm and the (short) key and I can predict it forever. When we talk about PRNG's as stream ciphers, the idea is that you're given the algorithm but not the key. The distinguishability criterion means you get two streams of data. One comes from the (known) PRNG algorithm with an unknown key, and the other is random, and you're asked which is which.
If you can find a way to tell the difference a significant amount of the time, you've broken the cipher. Again, see Bellare and Rogaway's notes for formal definitions. Unruh 16/7/2005, 17:04 น. It is distiguishable from random. Given a tiny bit of knowledge, the key, all output is known. No random generator has that property.
I simply need to search through 2^128 bits of space ( a tiny amount compared to all strings of length a google) and I WILL discover the key and will discover that AES is completely predictable. 2) Someone proves AES is indistinguishable. That's a HUGE result because it means the P vs. NP problem is solved. Nobody expects this and it will be a big surprise if it happens anytime soon.
No, it has absolutely nothing to do with P and NP. 3) Nobody proves anything. We keep on thinking and hoping, without definite proof, that AES is strong.
This is the most likely way things will continue for a while. The strength of AES has nothing to do with either of the above. Paul Rubin 16/7/2005, 17:06 น.
Unruh writes: It is distiguishable from random. Given a tiny bit of knowledge, the keyall output is known. No random generator has that property. I simply need to search through 2^128 bits of space ( a tiny amount compared to all strings of length a google) and I WILL discover the key and will discover that AES is completely predictable. If we're talking about these terms as used in cryptography, the criterion is polynomial-time tests in the key size. A 2^128 search is considered infeasible.
'Polynomial time' is where P vs. Unruh 16/7/2005, 17:06 น.
Unruh wrote: Paul Rubin writes: You're at the point where maybe you should look at a formal mathematical treatment. Bellare and Rogaway's lecture notes are a good place to start: It is distiguishable from random. Given a tiny bit of knowledge, the key, all output is known. You really need to read Bellare and Rogaway.
They make it all formal. In particular, the usual notion of indistinguishability for cryptography is.computational. indistinguishability: no computationally bounded attacker should be able to distinguish. (e.g., no attacker using more less than 2^80 clock cycles should be able to distinguish with advantage better than 2^-32.) It's all spelled out there. You really would benefit from reading it. Right now, all I can say is that your comments make you appear to be a little unaware of some of the basic notions of theoretical cryptography.
Those comments are missing key points, points which have been already addressed in the basic literature. Bodo Moeller 16/7/2005, 19:28 น. Paul Rubin: Unruh writes: You are, of course, right that the 2^128 search can be considered infeasible so that the brute-force attack does not make AES distinguishable from a random permutation. However, this is not really about P and NP. The term 'polynomial time' only has a very fuzzy meaning here; this is not the strict notion from complexity theory.
There is no definition of AES for arbitrarily long keys, so it is meaningless to talk about asymptotics: there is no security parameter that can be increased to make the adversary's task harder. While the 2^128 step search talks a very long time indeed, it still is a constant-time attack. Bodo Moeller 16/7/2005, 19:32 น. Paul Rubin: Unruh writes: You are, of course, right that the 2^128 search can be considered infeasible so that the brute-force attack does not make AES distinguishable from a random permutation. However, this is not really about P and NP.
The term 'polynomial time' only has a very fuzzy meaning here; this is not the strict notion from complexity theory. There is no definition of AES for arbitrarily long keys, so it is meaningless to talk about asymptotics: there is no security parameter that can be increased to make the adversary's task harder. While the 2^128 step search takes a very long time indeed, it still is a constant-time attack. Paul Rubin 16/7/2005, 19:44 น.
Bodo Moeller writes: However, this is not really about P and NP. The term 'polynomial time' only has a very fuzzy meaning here; this is not the strict notion from complexity theory. There is no definition of AES for arbitrarily long keys, so it is meaningless to talk about asymptotics: there is no security parameter that can be increased to make the adversary's task harder.
While the 2^128 step search talks a very long time indeed, it still is a constant-time attack. However, AES reduces to (say) a SAT problem with at worst a few thousand terms, a relatively small problem. We (perhaps without justification) use 'SAT is in P' to mean 'SAT is tractable' even though the P-time algorithm for recognizing SAT could have a horrendously large exponent. If someone proves AES has no better distinguisher than brute force, it means that the corresponding SAT problem also has no faster solution than searching the AES keyspace, which goes against what we normally pretend it means for there to be a P-time SAT solver. Obviously there is a gap in this logic, as you point out: there could be a P-time SAT solver which is still so slow that using it to break AES is slower than using traditional brute force. In this flavor of complexity theory we just handwave that issue by only caring about the asymptotics and pretending all the constants are small.
So there is a certain amount of hope involved about the constants, but the relevance of P vs. NP comes from the existence of that SAT reduction, which is a definite thing. Joe Peschel 16/7/2005, 20:49 น. Paul Rubin wrote: 'Cristiano' writes: To me, 'random looking' seems = 'indistinguishable from a random source'. What do you mean?
'indistinguishable' means you have no practical way to tell which is which. No general purpose test can distinguish the MT sequences from a random source. I don't know what you mean by 'general purpose test', but 'indistinguishable' you can't tell the difference using ANY test, not just general purpose tests. When I talk about generators, I always have in mind the general purpose tests (RaBiGeTe, TESTU01, NIST, DH). 'Random looking' = 'indistinguishable' = sequence which looks like random because pass all the general purpose tests. But with the 'new' definition of 'indistinguishable' ('new' for me) obviously I totally agree with Simon Johnson. If, after studying the MT algorithm and source code for a year or two, you can come up with an MT-specific test based on the intimate details of how MT works, that distinguishes an MT stream from a random stream, MT is distinguishable.
I guess that it is always possible to come up with a specific test for.any. non-crypto PRNG. Cristiano Cristiano 17/7/2005, 1:28 น.
Unruh wrote: A random source cannot be predicted. And no PRNG is unpredictable. Just give me the algorithm and the (short) key and I can predict it forever.
If I use a CPRNG I will keep secret the key! You'll try to break the generator without any knowledge of the key. Now, can I figure out how to predict it just given the output alone? I do not know but I do know that there are very very strong patterns in the output based on the fact that it is generated by a PRNG. Are you sure? I'd say that the patterns are very very weak because it's very hard to write a test which is able to find a pattern. Even if you test many Gbits of a CPRNG using the most effective tests, you don't see any pattern.
![]()
Cristiano [email protected] 17/7/2005, 3:51 น. 'Cristiano' wrote: George Marsaglia wrote: 'Cristiano' wrote in message news:[email protected]. That could be interesting, but there is the proof that MT has a very good k-distribution, for example it is: (623,32)-distributed (1246,16)-distributed (2492,8)-distributed (9968,2)-distributed which could be useful in some application. Please, could you post some value for your generator? What are you on about? The (623, 32) distribution implies the others automatically. This is true whenever we compare larger with smaller word sizes in a perfectly packed code, and binary is of course a perfectly packed code.
Secondly, you should not use this notation. There is a standard definition of (m,k) distribution which goes back at least to the 1st edition of Knuth's famous book, The Art of Computer Programming (1969), and it has nothing in common with your notation. That is good, but the k-distribution is a 'stronger' distribution.
In the book mentioned above, Knuth put a lot of emphasis on the idea that infinite-distribution of a random variate was a strong criterion for 'randomness'. This seems to have led to a widespread belief that high orders of k-distribution are enough by themselves to say that a sequence of integers is 'as close as we can get' to random. It is easy to show that this is wrong. (Note that the various theorems proved by Knuth applied to continuous variates on 0,1), not to integers). First of all, consider pure multiplicative linear-congruential generator (MLCG) with a modulus P. It is trivial to find the parameters such that the output is at least k-distributed for 32 bit integers. This is true for any member of the family of LCGs with P = 2^(32.(k+m)) + 1.
In your case, the mininum desired k = 623, and with no effort at all (my freeware primality testing program shows run times of 623 - but every one is very non-random because of the failings of LCGs as a class. LCGs have values which cluster on hyperplanes, they fail the spectral test and other tests, their parameters can be discovered from only a few values from the sequence, etc etc. They are very NON-random and useless for cryptographic purposes: no matter how high the k-distribution (and this can be extended to infinity). Secondly, I'm sure it's not just LCGs. LCGs fail a variety of tests due to the high degree of pattern in the sequence, which is in turn due to the simple generator function. I assume that we can see the same scenario of (detectable non-randomness despite good distribution properties) with other PRNGs of simple structure: can someone else comment? Thirdly, there is more important way in which LCGs are non-random.
If the sequence values are integer (or more generally, quantised to q levels), a true random sequence should show some runs, with the probability of consecutive repeats being 1/q, 1/q^2, etc. Generators that have outputs that come close to this distribution are behaving much more like true random numbers than ones that don't. In this respect, full-period LCGs are the worst - their probability of a consecutive repeat of the same number is always exactly 0, regardless of generator period, output sequence length, and distribution order. The upshot is that the k-distribution is much weaker evidence of randomness than the behaviour Prof.
Marsaglia mentioned. Hadstate 17/7/2005, 7:10 น. Wrote: 'Cristiano' wrote: George Marsaglia wrote: 'Cristiano' wrote in message news:[email protected].
That could be interesting, but there is the proof that MT has a very good k-distribution, for example it is: (623,32)-distributed (1246,16)-distributed (2492,8)-distributed (9968,2)-distributed which could be useful in some application. Please, could you post some value for your generator?
What are you on about? The (623, 32) distribution implies the others automatically.
This is true whenever we compare larger with smaller word sizes in a perfectly packed code, and binary is of course a perfectly packed code. In a first moment I thought to post the entire table about the k-distribution of MT as in MT paper, then I posted just few values. What's the problem?
Secondly, you should not use this notation. There is a standard definition of (m,k) distribution which goes back at least to the 1st edition of Knuth's famous book, The Art of Computer Programming (1969), and it has nothing in common with your notation. Matsumoto, in his paper, uses the correct terminology: 'k-distribution to v-bit accuracy', but for simplicity I used that 'strange' notation. That is good, but the k-distribution is a 'stronger' distribution. Nonsense. In the book mentioned above, Knuth put a lot of emphasis on the idea that infinite-distribution of a random variate was a strong criterion for 'randomness'. This seems to have led to a widespread belief that high orders of k-distribution are enough by themselves to say that a sequence of integers is 'as close as we can get' to random.
It is easy to show that this is wrong. (Note that the various theorems proved by Knuth applied to continuous variates on 0,1), not to integers).
Try to understand why I wrote 'stronger' distribution with the quotation marks. Marsaglia said: '. the expansions of rationals k/p for large primes p are expected to pass extensive tests of randomness, in the sense that they may be reasonably considered the output of a sequence of iid variates taking values in 0,b-1) with equal probabilities.' Which should mean that in the whole period you see all the values from 0 to b-2 the same number of times.
I said 'stronger' because all the good generators output numbers which are uniformly distributed, but there could be some generator that has a low order k-distribution. The upshot is that the k-distribution is much weaker evidence of randomness than the behaviour Prof. Marsaglia mentioned. Your main problem is that you think I said 'high order k-distribution = randomness', but I've never said that; the only thing I said is that an high order k-distribution could be useful in some application.
My only mean to see if a sequence is random looking is to test it. So, back to my question: can you tell me, please, the order of the k-distribution of Prof. Marsaglia's generator? Cristiano Cristiano 17/7/2005, 8:24 น. 'Cristiano' writes: Yes, I will.
It is called the algorithm which is itself a test, with an unknown element, the key. Since the key is far far shorter than the stream I have, that key with the algorithm defines a pattern. Now I agree that it is not easy to find that pattern. It takes perhaps something like 2^128 attempts, but once I have found it the pattern is completely predictable and deterministic, and can be extended to an arbitrarily large piece of output. Or to use the Chaitin/Kolmogorov definition of randomness, the output is entirely non-random.
The length of the shortest program (the algorithm plus the key) is far far shorter than the output. And no matter which sample I take, this is always true for that PRNG. Ie, even the average length of the program required to output a large number of samples is far shorter than the output (whcih is not true of a true RNG) Cristiano Paul Rubin 17/7/2005, 11:06 น.
Mersenne Twister in C, C, C# Mersenne Twister in C, C, C# 1998-2007/2. If you want a twice to four times faster variant of MT, there is one designed for SIMD CPUs. It is faster than the original MT, even in non-SIMD CPUs, and has better assurance of randomenss.
Downloadable from. If you want the newest version of original authors, go. Old standard versions (do not use). (1998/4/9). (1999/10/29).: A small senior cousin of Mersenne Twister. It is also in: Salzburg University Random Number Research Team. A C version of MT is available from.
Rene Brun at CERN kindly implemented MT in their C framework Here is. by Richard Wagner: 'I have written a new C implementation of your Mersenne Twister random number generator. It is based mainly on Shawn Cokus' optimized C version with several improvements for easier use. For example, seeding can be performed automatically from the system time or, on a Linux system, /dev/urandom. Random numbers are easily obtained as real numbers or integers in default or user-defined ranges, and the state of the generator can be saved and restored.
It also includes changes you made after Cokus' version.' The code is faster than Cokus's version in some platform. kindly sent us another C class called. implemented a C#-version of MT19937 under the Artistic License. In the page, there are a direct translation to C# and a class which inherits System.Random in.Net library.
wrote a very fast C/C-version of MT19937, faster than Cokus' version (depending on the architecture). Moreover, it has many extended features, like to produce multiple independent streams of prns, etc. informed us that they use MT in their open-sourced neural network simulator.
They noticed several compilation problems, however, for Richard Wagner's C when compiling the code with certain versions of STLPort and while experimenting with static linkage. A Nutshell programmer Robert Berg fixed this. Here is the code. ported MT19937 to store the globals from mt19937.c in structs for parallel run. Also at this location is a parallel version of a Sobol' sequence generator. (updated 2007/6/1).
wrote a C code using Pentium MMX instruction. This is almost twice as fast as the original Wagner's C code. wrote a C code which permits several paralell streams of MT.
wrote a thread-safe DLL version of MT. Includes a DLL version as well as a thread-safe version, and a Makefile for Borland C Compiler 5.5. This page also includes MT19937ar.c ( improved initialization version, 2002/1/26) and its Cokus-type speed-up version MT19937ar-cok.c, and show a comparison of speed. Is also available. An implimentation of MT19937ar (new initialization, 2002/1/26) in C and C with various functions added. A.lzh file for the both C and C is available as.
Explanations (only in Japanese, sorry) and plain files can be found at. Agner Fog distributes a bunch of modern generators including mt19937ar.c (improved initialization version, 2002/1/26)in C and Assembler, for uniform and non-uniform random number generation. The code is very well optimized. See (2004/4/14).
Eric Landry informed me that is proved to be faster than the standard code, in some platform. (2004/3/15). (2005/2/23) Here is a C code of Mersenne Twister for 64 bit machines, with period 2^19937-1. The recursion is similar but different, so the output is totally different from the 32-bit versions. Kouhei Taketa kindly wrote an another C version of MT. His code is a header library, so one can use the functions by including the code as a header file using #include.
In addition, the code contains a 64-bit version of MT. Here is his code. Japanese explanation and same code is in.(2005/10/6). Diego Park kindly wrote an Visual C version of MT. He wrote a single class (through template) to provide 32 and 64-bit random integers alike.
This implementation has a speed-up of about 38% against the original implementation on 64-bit version, about 70% on 32-bit and about 500% against rand, generated by Microsoft Visual Studio 2005 Beta 2 targeted to x64 architecture, tested on a AMD Athlon 64 3000+ with Microsoft Windows XP Professional x64 Edition. Here is his code. (2005/12/16). Mitil Ooyama wrote a C# version of MT. Here is his code. It is in his (written in Japanese), too. (2006/1/23).
Zubin Dittia wrote a C version of MT. Here is the code. This code contains the genrandbuf function, which fills a buffer with random data. (2006/2/7). Loren Carpenter at Pixar Animation Studios kindly wrote a C version of Mersenne Twister using intel SSE2 instructions.
Here is his code. It's about 3.2 times as fast as the serial version on 3.4 GHz Xeon. Charles Karney kindly wrote a C version of Mersenne Twister. RandomLib is a C interface to the Mersenne Twister random number generator, MT19937.
It provides convenient access to random integers and reals at a variety of precisions. The emphasis in this implementation is on providing a reliable source of random numbers for scientific applications where there's a premium on accuracy, repeatability, portability, and ease of use. This library provides an improved method for seeding the generator with arrays and it allows access to both the 32- and 64-bit versions of MT19937. For more information, see.
Comments are closed.
|
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |