© Distribution of this video is restricted by its owner
Transcript ×
Auto highlight
Font-size
00:11 okay saying good works. It So they also have a little bit

00:27 grab the number of generators. mostly make you wear out problems and

00:37 you about a few simple ones. huh. To get really good quality

00:44 numbers. It's complicated business and so . Was trying to make you aware

00:50 . I nearly you should get familiar such things software and let's protest whatever

00:58 numbers generated you're using unless you want be very so that's kind of the

01:09 of today. Mm hmm. I of the rest of the course just

01:14 you aware of when things can go and be critical and then find ways

01:19 challenging very fine whatever you get. this is a little bit of background

01:28 everyone has transpired in the best. that was the system. Random number

01:37 kind of used everywhere. And we're much used in every day. Even

01:40 you don't think of it. I I was then there is then used

01:46 blood protocols. So they are dependent random numbers being good. The difficult

01:55 is when we test something and then don't data or but even she ha

02:05 it's common to generate contestant using random generator. And so in our case

02:17 , make sure that things kind of the way you intended. You may

02:21 need to know something about the quality the distribution of these random numbers.

02:28 other ones that's pretty much thank you understood doesn't need any explanations but in

02:35 things is, but people design all of, um, service things or

02:42 tropic close being forgotten. Sit down , statistical models of customers arriving and

02:51 times and all kinds of stuff from underlying statistics. Um when you're designing

02:59 for a variety. Um, other is people. The last company,

03:10 , chemistry, biology, chemistry also several Carlo methods that are based on

03:21 methods as well as in optimizations. things tends to be hard, sometimes

03:28 resort to statistical methods are very Two hold it may be harder to

03:36 how good they are and solutions have be understood in the percent. So

03:44 the third that TCP and DNS use and modern design. So you're being

03:52 from everything. Just as a way where things play out. The only

04:01 to be aware of. Everybody talks random number generators but they are not

04:06 random numbers and that's part of their . So most of their best they

04:13 the Foreign Minister. We just try make sure that for practical purposes in

04:20 of behavior as if they were random it's limited. The property is by

04:28 word length on the computer or the that you're using. So it's certainly

04:36 a short time range of numbers that be represented and eventually things start to

04:42 . They have a period determinist is both by the detector algorithm you use

04:48 well as the how many dates you in your bank account What this one

04:58 . So someone has to watch out these things and there will be an

05:03 . So things that people thought were and they turned out not to be

05:07 in the past and that's problems. the chance. So that's a problem

05:16 finding random good random number generators is trivial. People, I'm in a

05:28 come up with something new that now trying to figure it out and it

05:33 out that is not the case. , um, so one thing to

05:41 the US and something called this, National Institute of Standards and Technology.

05:49 continuous ongoing effort trying to come up random number generators as well as

06:00 for figuring out what properties it seems a little more than they have.

06:06 then the recommendation, they give recommendations companies and the public at large for

06:12 type of generators to use and Um, so again, pretty much

06:23 home message today to make you aware kind of to find tests of which

06:31 are many to try to assess your number generator. So there is one

06:42 we talked about in the garden and in the beginning and for a long

06:48 close in elimination or opposition was used breaking computers in terms of speed the

06:58 performance impact, which is basically a composition. And so companies in particular

07:06 bragging rights on two around this link access to try to then claim that

07:13 have the fastest material. Yeah. in that case, what people who

07:22 the initialized the major since using a number generator numbers. So random numbers

07:29 kind of a good thing. It's some sense, it's kind of an

07:32 right behavior that as you may hopefully come solving linear systems of equations

07:44 the matrix is singular, it kind doesn't work whether it's a riveting or

07:50 , it doesn't work. We got elimination whether you that composition, so

07:56 is the basis for the site performance . So at one It's about 20

08:04 years ago now, I think there so companies necessarily want to run this

08:09 for bragging rights. So they used generator, random number generator of this

08:16 . I'll talk more about that Um and it turns out that this

08:24 , the number generator, the way used it with particular initialization will come

08:33 , it turns out that they generate matrices. So people and just the

08:37 benchmark didn't work out. So I the tremendous error that they thought there

08:44 be somebody in the toe or maybe hard work. None of that's

08:49 Software was fine, it was it was fine, but the data

08:54 was not cool. So, And is matrices up to 500,000. This

09:00 table here shows a particular size nature for which there is at least two

09:09 or rows in this matrix that are . So there are repeated for the

09:15 is singular and depending a little bit initialized in the midday Sun policies,

09:22 it may be more than two rows columns that are the same. So

09:26 numbers one inference, is that the place telling you know how many copies

09:32 the same? No more column, is a matrix of the so it

09:39 . So and then it took about people think it up that the matrix

09:44 singular and there's nothing wrong with anything . There was a random number generator

09:47 was bad for clinicians station. So other things in terms of ssL for

09:57 inscription protocol, the early version of , one of the houses dominating browser

10:06 whatever. Also technology also had So we have to try to figure

10:13 how to fix it. Um, another one from the Windows 2000 Windows

10:22 have problems and usually, thanks, don't usually publishes after what they're

10:29 Um, some of these guys something have to do, reverse engineering to

10:35 out what was wrong and then companies to and it's asked for the one

10:42 somebody figures out it just didn't And here's one that's actually even from

10:49 standards institute that recommended a particular type and the number generator and some

11:01 Now this is not the great for things because that is why you saw

11:04 cracking the algorithm and get the back down here is anyone knows what then

11:13 it is. No, yes. agency and get some sports in the

11:23 . So they wanted a backdoor. they bribed this company With 10 million

11:27 use this perfectly random number generator. then my dad was discovered, missed

11:34 standards, people decided not recommended Um and here is another one that's

11:45 too long ago. Again, there's problem. Again, we're going to

11:49 to generate random numbers and as I , there are stds and other things

11:59 somebody developer about something went wrong and the code etcetera and try to fix

12:05 things. So they combined it into in the process based quality.

12:15 it was one of the dominated the public key factors schemes are safe

12:22 they also figured out depending upon other numbers for the factory in Pakistan,

12:27 is a waste of figuring in knots to raise the security. So a

12:37 bit of what you want. So of the thing is you want the

12:42 number generator obviously to generate good quality numbers, they want them to have

12:49 distribution, you want to The long 6000 repeat as I said, there's

12:55 maximum here, depending on the Portland the data type you're using but of

13:02 the period may be much shorter than . So I tried to design it

13:07 . So you get the long that's the uniform it is all depending

13:13 and a subsequent picked out of the sequence around the numbers. They should

13:18 be correlated and repeated. So it be very hard to find repeating patterns

13:24 the screen And of course the one to be fast. So um this

13:34 the reason that they wanted to generate of the headache in terms of for

13:39 failures in the past that you know that is computational simple but it turns

13:45 not to work too. So there a good moment. That's hopefully everyone

13:54 that more or less the partner of But and it was a mathematician that

14:03 to point out that as soon as used. Uh huh. That's the

14:10 procedures. You can't So then I to just show you these are not

14:22 per se, but it's a way conduct yet a sentence for how this

14:30 of random numbers finished. Um So are fairly simple um ways of mhm

14:43 potential qualities or lack thereof of random on this line. Three different versions

14:52 is known as the face based representations enlisted Take a sequence of four numbers

14:58 them for 10 -3 to end. you look at the three different Paraguay's

15:05 kind of in the succession of the numbers and you look at these three

15:11 as coordinates in free space and then project can figure out what you

15:17 Sometimes it is from the you probably expect. And I'll show examples from

15:24 . And another one is just to a sequence of three numbers and treat

15:27 as X one c coordinates of this . And that's kind of the common

15:32 is space representation. And then we we can work polar representation as well

15:38 three successive friendly numbers from these I'm sure many examples of that.

15:47 he was just a long less than couple of slides. Again, this

15:53 this National Institute of Standards and Technologies come up with a bunch of tests

15:58 can download, I think for all these tests stealing from their website.

16:04 they do have just suddenly come down constructive themselves. But one thing is

16:13 look at the distribution of zeros and , uh, and the random numbers

16:21 have suggested that I should have taking opportunity to speak the crap on

16:26 So, so a little bit decide and thanks stuff. So yeah,

16:34 has been a lot not as a A. But as a grad student

16:41 . And one of the projects that's doing and discovered that that test using

16:48 numbers consumed a lot more our energy other forms of initialization. So we'll

16:57 interested to understand that a little bit part of that. Also look at

17:02 distribution of zeros and ones and check out. Flowers. Do you remember

17:09 number generators? Almost the same birds and it's kind of Yeah, pretty

17:16 normal. But it's not centered at so the main point and their differences

17:24 little bit still respect the anyway, that there is this distribution that people

17:32 at in terms of how many zeros months there are. I can kind

17:36 the strain of whatever lemons. another is to do things that said one

17:44 interested in potentially blocks or sub sequences trying to figure out how correlated correlated

17:55 plots. So that's kind of behind block frequency test and spectral test and

18:03 young best we're looking at the frequency for them branches on the occurrence of

18:08 and ones or if you have blocks or numbers or that's what there's been

18:19 . I don't think that we looked the test that is anatomically non decreasing

18:27 increasing. So it just goes up goes down. And what is the

18:32 of such sequences related is kind of at the length of the strengths with

18:40 ends up covering consecutive bits being the . How many zeros that were there

18:46 one shows up for commerce. Once zero shows up. And depending upon

18:52 properties that um, and show it . Mm hmm. The run length

19:00 no too large. There is something is very common and used that is

19:06 as practice. I'll show you an of that and that's one thing that

19:12 useful for and then there's a whole of other tests exists. So they

19:23 15. All them adjust at some of miniature if they changed the number

19:28 or in recent months. So this some time ago and then there's some

19:34 not for further tests that um people at to find different properties of this

19:42 number sequences. So it's just this service. But to actually go to

19:50 website and do anything that potentially depends whether you actually have put random numbers

19:57 not familiarize yourself with the tests and out which ones make sense for an

20:05 . Mhm Or just for fun and some of these tests on whatever comes

20:11 or limericks or windows or anyone. let me see what the property looks

20:20 . Still more here and start. , please frank test that I talked

20:24 . Some of those could take the and then turn it into a kind

20:30 M x two blocks based on So basically did sequence. Hmm,

20:37 and two columns and from the little matrix. And then you've got a

20:42 of these blocks for the entire stream benefits, security, subsequent choices And

20:51 are these don't not overlapping and again this box and then you best to

20:58 out when you're right and this rank comes in tend to figure out whether

21:06 collection years or m rows and two and all of the bits And whether

21:11 has full rank in this case 4 or in this case the from

21:18 rolls of the same in this So as I said, typical 33

21:26 two and I don't remember from which night random number generator discourse example was

21:35 up but you can see enough in case Of this 32 x two sub

21:43 of the cars and bits. not even the third. That's cool

21:51 I'm supposed to 60%. So we deficient but only honestly. So and

22:00 there is not too bad, but minutes plus percent that has the rank

22:07 at most. I don't know how have Iran it's match. So the

22:13 is to get to try to there is no this petition basically they

22:23 so all the subsidies to all the . Um, just the bits around

22:33 . So now I want to show what has been after and these examples

22:40 from using here that they, what the latest version of illustrating things or

22:49 space or the polar. So you see different illustrations or probably is random

22:55 generators. Good news from numbers. hmm. So, so here's an

23:06 from IBM quite a few years ago . So. So what do you

23:14 about this thing? Doesn't look friendly . It seems like there's,

23:21 it's more likely to choose a number closer to the middle. Okay.

23:28 that would represent? That is And uh now, so this is

23:37 just sort of a few spots of then I wanted to do this.

23:41 me face. That's what you So then I'm very special for some

23:47 marked by elements and it means random . So this is by the

23:58 the three numbers and treat them as free space you can see. But

24:05 this institution is totally uniform negative numbers falling on streets. So this

24:14 they're not not pretty good. And we'll have to excellent. It took

24:20 while and to understand what was but they don't use this and they

24:25 using academy quickly after the discovery began some ways of testing in this government

24:33 I remember this and that's, here's another one From Windows 95 and

24:41 is the TCP protocol and as one see in this case is by no

24:48 are reminded. Okay, correlated over plants give some notion that space is

24:56 uniform the field. So it's really that good in this case is even

25:00 of the status property that already in of the lack of quality ah Trying

25:09 brought us another 1-98 to fix it they've got something else that wasn't so

25:17 cannot melt down. It's hard. So and then when has also had

25:24 involving um, Another four. Then safety protocol and it's finally, so

25:37 in the student 1000 we've got something . And then its service package

25:42 there was an update. No, doesn't pull the space, but it's

25:48 least much better distribution of previous And there's another one that's on stood

26:00 . Um, but anyway, you see it's, it's not final means

26:05 this now it's fair blocks. It's , but against um, not

26:14 it's better than they had before. predicting that facebook can tell by those

26:24 . Um, 2003 adult, there's , there's another one or it's not

26:35 nicely. And you can see here that that's starts in the corner.

26:42 more Windows XP. So, Well, so I'm just making your

26:52 the, this is a difficult Companies don't take it like that and

26:58 hard and here's another one. Service to try to fix things. How

27:06 is that better? It's different. , there's more, you can see

27:11 , try this one. Yeah. side down. Um, And the

27:17 one year is 2000 month yesterday you can see kind of parliament similar

27:24 them or something. Another random number . This kind of shape and a

27:31 kind of cute. There's other ones exports From the were not just speaking

27:39 5%. Again, they're all from and this is fun. Some of

27:45 Solaris operating system ah, generating and another one. No, and this

27:56 considerably better. Um hmm, I'm showing you here, you know,

28:04 they're trying to fix things and you tell the people, all the companies

28:08 learning, nobody wants to tell the one is what they're doing. But

28:12 this case the platform to taken from and so on the generations of the

28:17 generators and this was from silicon fixed that doesn't exist anymore. Not because

28:26 the random number generators, but there not a business kind of for the

28:33 . Uh huh. Also picking on , they also have problems. So

28:40 , I miss the sale. Everybody about fiscal, but also again,

28:49 be an internet protocol. They are important factor and they also have

28:55 you know, they ran the Here's more examples, tons of

29:01 I think ah, the previous C operating system, open source, I

29:08 have issues, things are changing and just try and so I think right

29:15 , okay, sure. Being and of the strong sequence of our

29:23 of other random numbers tend to fail generate good numbers here is another one

29:30 shows parents. Um, so, , so this is pretty much showing

29:39 little bit lower. Again, a of it, despite of the

29:45 The defense couldn't agree on five friend my efforts, but, but was

29:52 in terms of examples, so open convincing. You have to be conscientious

30:00 the quality depending on what to It may not be very nice important

30:04 all. But that's a charming in previous. Sometimes things are awfully wrong

30:16 many of the so the more complex for either your optimization of things depends

30:26 to have a good sampling of the you're in. And if you don't

30:33 kind of a nice uniform sampling your answers may talk to the kind of

30:39 you want. It's not representative of problems with no. The linear conventional

30:49 are the most popular and on the new RGM that didn't work too well

30:53 with the impact that didn't work too . And an example of this then

31:01 conventional generators and they they work with . Okay. But it's very tricky

31:07 figure out how to initialize them and on what numbers you use in the

31:16 function. So here is the there's a list of things that has

31:22 used. Um so the form is multiply with and you provide a.

31:30 and starting seed, which should say is 10. So the first argument

31:38 yeah. Bring your numbers on the you're using And a is the multiplier

31:45 one, Number two The next and be it's kind of they have in

31:50 . So this is what you see this expressions here for the Congress of

31:58 statisticians Says he used to do this , which is kind of a 10

32:03 one because the supplier of to make very simple um, to do the

32:09 function. That is not a good . And then here is your

32:15 here's a C. I mean, part of the starting scene for the

32:21 , random number generators, but and is this other one that uses the

32:29 That is one of these former seven numbers. So that is a lot

32:35 in terms of limiting the period of extending the period of the statements and

32:46 uh, here's around, Uganda said didn't work well and part with those

32:51 didn't For the car of two. it the computer that was again they

32:56 to pass one is in the computer didn't work well. And then it

33:01 also using that's such a great multiplier using this particular number. So,

33:12 the next one year's December seven, prime means another one that is to

33:18 this kind of programming language. right. And here is the accidents

33:28 America algorithms group that's kind of a to math lab. They have a

33:34 focus but they do math software, then focus more on software for solving

33:41 differential equations and optimization. Yeah, kind of a little bit more complex

33:50 outside. They won't respond to these manipulation languages. Start America. So

34:05 is, has shown that the they have been popular and they are

34:10 They lost the simplicity, um, in the sense that fairly easily to

34:16 depending upon the month function. They more or less insane from the

34:23 Sorry, it's just from the books the book discusses around the number generator

34:29 chapter can so much. So what told is not covered. So here

34:38 that this happens to be in the and this was one of those minimum

34:44 generator and stuff things. So in book, it's very simple procedure

34:50 contravention of efficient except as of this function. It's a bar of two

34:57 trivial, but if it's not, for the prime number is not

35:06 And this is very much just summarizing to show on the pictures of their

35:13 random. And so one way that used to stage a sequence and new

35:21 into the higher dimensional space. And kind of a common trick,

35:27 to kind of expose profit. Is enough? So it's easy to

35:33 And so we're just sitting here or this place. Oh, what is

35:44 funny song? So this first, we remember the random thing, there

35:53 a bunch of planes and free space two D planes and this just shows

35:59 , depending upon what in this case that's used for the mod function.

36:07 . It shows to the number of is that contains. Um, so

36:13 ended up also the sequence of these . So that's going to fall

36:19 So all that's the specials are by means kind of random. They wanted

36:24 be extreme as possible here. Once around here we got the registration and

36:34 the body. It doesn't look too in terms of the random numbers but

36:39 the status box instead, uh, the three departments. Then we need

36:45 see that the following. And here kind of another one that was using

36:55 same script. One is to, . This was a minimal and I

36:59 that things costs and fines and it's gonna be going on screens and to

37:06 . Ah, this is a lot and that it's the same script and

37:11 another cent right. But the not supplier that this guy and that

37:16 be the difference. Otherwise They won't no B0. The same starting point

37:25 shows the difference. Um, given same month function, the multiplier,

37:30 makes a big difference. And how come up with this multiplier. So

37:34 has been, how do you figure out? And here is kind of

37:41 slice again, show on that for of them you get very clear

37:47 It's not such a long. So is a lot better. Again,

37:56 know, finding different initialization or So this. Hmm. And so

38:07 were often in their confidential showing Yeah. First that we can get

38:14 of the numbers if they are very and take the seed and the ma

38:18 be used for B and B family in your interest. And I can't

38:23 what it was. Okay. Yeah. So in terms of what

38:33 kind of an assembly brian based, have gotten left today. Six.

38:47 . Kind of for that. So thing to try to improve this fairly

38:55 generator is to use some of the alter. So in this case instead

39:01 just having one and then just the value, we depend on the sequence

39:06 previous values and then you do them after having a bunch of multipliers.

39:12 so in that case it does improve period of someone that case depending on

39:19 many um previous random numbers you use your winning a congress that generated and

39:30 security. So on the other ones can do not linear ones. But

39:35 could work for squares. Mm Or have been there inspires. So

39:42 are many tricks people play to try improve the rental numbers and characters and

39:47 see what it is. Just scaling from some other interval. That standard

39:54 That's becoming between zero and 1. it's not shift and scale and stretch

40:03 shift. So now it's okay. don't want to talk about the

40:16 I just want to show a few . So for that and the computer

40:28 part of a computer. So even phone that must of course. And

40:34 um, if you trying to, run cold and you want to do

40:39 coal bores or things like busters, best ever production of parable operations.

40:52 . Now it is important to try make sure either who are having,

40:59 can not to generate and examining long of random numbers and then you have

41:09 different threads in your execution. This create samples from this very long

41:17 So they do subsets on the single or in the other way you try

41:23 generate physically the sequence for each Now, if you do the

41:32 then if you see they random number in the same way you've got identical

41:45 for each one of their friends And are 100% correlation and that's probably not

41:53 you want. And then the others sub samples for each one of the

42:02 . The even though the cold it has a very long period

42:11 The subsequent servant of certain point obviously significantly shorter. So I interviewed for

42:23 state that they are computers the young have a few 100,000 friends. So

42:35 one sequence and generally hundreds or thousands subsequent is out of it. It

42:41 that the period gets short and there's whole also risk of the different subsequent

42:46 according. So it's very tricky. is even more tricky than it used

42:53 be run your town to do things currently people struggled today trying to figure

43:04 what's a good way of doing But I'm just pointing out that the

43:09 has gotten much worse with increased resources and we're gonna show a couple of

43:19 and that's um, I think you me already. So let's see what

43:28 . So one thing, yes, can ask is a non centralized one

43:32 number generator that can things out to or replicated and distributed from that place

43:40 on how the generation is done. then there's the question, if they

43:43 on one sequence on multiple sequences. you. Multiple sequences, significant

43:50 You have to be very careful to sure that the seeds doesn't call because

43:55 that we did. So ah What's up and this advantage. Mm

44:14 . So these are the kind of um, depending upon on ah this

44:22 santa was thinking in the first quarter a chronicle survey client model. Then

44:29 central guy have potential no control or one of the cost disease gets what

44:37 on that place. The best reproducibility can suffer. So that's another part

44:46 been touched upon. So to have reproducibility, you may also all those

44:55 , experiments what you do ah make either if you want to get statistics

45:04 make sure that saving the statistical if you want to to kind of

45:15 and make sure things are correct, we want to ensure that the ceiling

45:19 the random number generator, it's always same. So you always worked with

45:23 same random sequence than it is for What You Want. So listen,

45:38 this is the second part of the that it's tough and don't make

45:45 Yeah. Mhm. So it I understand. So, there are

45:55 considerations. Again, in terms of that the collection of random number generators

46:04 the parallel environment has the properties actually that to happen. Mm hmm.

46:13 the different animals of our state systems I think the number of friends can

46:21 carried out. So, so um here is kind of Yes, currently

46:35 briefly just be aware of people have trying. Ah so this is kind

46:45 what they call the random tree method basically have two sequences. I kind

46:50 wonder. General seats for the um secret that right from the seeds and

47:00 the report, it's one of them around the sequence based on what the

47:09 generates and just 1%. Mm That's so, so it's fairly simple

47:20 implement. Well, yes. So response because it can happen.

47:32 So you can get this warning sequences sequences. Mm hmm. The following

47:43 based on skipping things. So this what you can see here that ah

47:50 sequence gets handed over and then on point it's a baby around Robin is

47:56 , so the right sequence and uh can see some of the properties for

48:04 , they start from that. I no statement or no real hard evidence

48:11 which one works better. What so that needs to do do it,

48:17 need to go extinct from the Yes, it is. So

48:26 Early process. Yes. And that's you can do can change their all

48:32 the left and right guys, which generate seats for the other one for

48:39 ? This is different. So playing with this thing seeding and different having

48:46 different generators. What do you want ? Yeah. Um check this

48:54 Show you this one and what I . So you can see there's a

49:00 list here of standard number generators out . So somewhere in here, I

49:07 they should be here. This crystal has become quite popular. Um So

49:16 this case, as I said, is, it's reproducible and start,

49:22 kind of a single perfect person. a good because it has a very

49:27 period um Yeah, and it's, it's not entirely simple and its

49:38 Your comments relatively large space um the um that are, so this one

49:50 also after um but I guess at point at this point properties or not

50:03 entirely well understood. Mhm. The is not very large. So that's

50:10 of potentially a problem with this one and another one again, in terms

50:18 things being uh, easy not taking lot of space. And they passed

50:28 , these two things are obvious. then that's a problem. Only one

50:37 number generators much completely structures alerted to fact that it's hard to get good

50:46 and software protest under a nominally generates of us I guess just use it

50:54 we need and use whatever to the system or some software and pay attention

51:00 it. And the film itself safe good. They don't know. So

51:09 here length, structural properties that, correlation and subsequent cases. Mm

51:19 Check the literature into Japan quality. that was it short. Thanks to

51:29 answer. But so on monday. . Yes. For the finals.

51:43 . It's very, so after I no friday, friday. No,

51:56 this. Yeah. You know what saying? There's not much time between

52:01 last lecture, the finalists. It's time than mine. Thank you so

52:15 for today. Thank you. Thank . Yeah, we'll try to do

52:23 review. I will not cover any material. I would just trying to

52:27 through things and remind you what we done after the midterm. So,

52:34 will not remind you about that. course. Just. Mm

-
+