Question

Problem 8 (Pseudorandom Numbers). Randomly chosen numbers are often needed for computer simulations of physical phenomena, and they are needed to generate random keys for cryptography. Different methods have been devised for generating numbers that have certain properties of randomly chosen numbers. Because numbers generated by systematic methods are not truly random, they are called pseudorandom numbers. There are fundamental properties we would like the pseudorandom sequence/pseudorandom number generator to possess for cryptographic purposes. 1. It is easy to compute values in the sequence. 2. Given any list of integers 11, i2, i3, ., ik and given all values of T'in, Viz, Liz,' ,tik it is hard to guess the value of xj with better than a 50% chance of success for any value of j not already in the list. Although no one has yet conclusively proven that pseudorandom number generators exists, many candidates have been suggested, and some of these proposals have withstood the test of time. a. Linear Recurrence: The most commonly used procedure is the linear congruential method. We choose four integers: The modulus n, multiplier a, 2 <a<n, increment c, 0<c<m, seed co, 0 < O<m We generate a sequence of pseudorandom numbers {k}, with 0 <I<n, by successively using the recursively defined function **+1 = (a2k + c) mod n. i. Find the sequence of pseudorandom numbers generated by the linear congruential method with modulus n = 16 = 24, multiplier a = 7, increment c=5, and seed to = 1. (List 16 terms - what do you notice?) ii. Find the sequence of pseudorandom numbers generated by the linear congruential method with modulus n = 16 = 2', multiplier a = 3, increment c=5, and seed Xo = 1. (List 16 terms - what do you notice?) iii. Find the sequence of pseudorandom numbers generated by the linear congruential method with modulus n = 32 = 25, multiplier a = 3, increment c= 7, and seed Xo = 1. (List 16 terms - what do you notice?)

Answer 1

(1) Given Xxx1 = (adx+c) modne No=1, a=7,c=s, n=16, Then Ukt1 = +5) mod 16 ,= (722+5)mod 16 = 12 , 72 = (7x1275) mod 16-9 23 = (749+5) mod 16 = 4, y = (744+5) mod/6 = 1 12=17X1+5) mod 16 = 12 ,et start reapeting elset. so random Numbers are (12, 9, 4, 1, 12, 9,4, 1, 12, 9, 4, 1, 12,3,4, 1). we only have 4 dandam Numbers, where n=16=24 Xo=1, a=3 cas, n=16, Then - Nx+1= (3x + 5) mod 16 7,= (3+5) mod 16 = 8, X2= (3x8 +5 )mod 16 = 13 93 = (3x13+5) mod 16 = 12, ny = (3x12+5) mod 16 = 9 15 = (3x9+S) mod 16 = 0,'= (3x0+5) mod 16=5 27- (385+5) mod16=4 , = (3x475) mod 16 = 1 ng = (3x1+5) mad16=8, it starts reapeting itself. so randan Numbers are (8, 13, 12, 9, 0,5, 4, 1,8,13,12 3, 0, 5, 4, 17. (2) (3) no=1, a=3 c=7, n= 32, Then = (3x1+7) mod32= 10, 12 = (3x10+7) mod32 - 5 23 = (3x5+7/mod32=22, ny=13422+7) mod3229 as = 13x9+7) mod32=2 no= (3x2+7) mod32 = 13

17 = (3x13+7) mod 32=14 x 8=13x14+7) mod32=17 X g = (3x17+7) mod 32=26 No= (3x26+7) mod32221 21= (3x21+7) mod 32= 6 x 12= (3x6+7) mod32= 25 N3 = (3x25+77 mod32=18 Ny = (3x18+7) mad 32= 29 His =(3+29+7) mod2=30 , 116= (3x30+7) mod 32=1 then et start scapetong ilself.