Discrete Math Notes - April 12, 14
Discrete Math Notes - April 12, 14 CS 2305
Popular in Discrete Math for Computing I
Popular in ComputerScienence
This 2 page Class Notes was uploaded by Aaron Maynard on Monday April 18, 2016. The Class Notes belongs to CS 2305 at a university taught by Timothy Farage in Spring 2016. Since its upload, it has received 28 views.
Reviews for Discrete Math Notes - April 12, 14
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 04/18/16
DISCRETEMATH SPRINGSEMESTER2016 INSTRUCTOR:DR.TIMFARAGE firstname.lastname@example.org 12-14 APRIL 2016 Pseudo - Random Number Generator Linear Congruence Method A method for generating random (pseudorandom) numbers using the linear recurrence relation: where a and c must assume certain fixed values, m is some chosen modulus, and X_0 is an initial number known as the seed. Using examples m=9, a=7, c=4, ann5: n+17xn4)mod9 xn 5 -> xn 5 Fermat's Little Theorem The theorem is sometimes also simply known as "Fermat's theorem" P-1 If P>2 is prime, and 1<B<P, then BmodP = 1; OR If P is a prime number, then for any integer A, the nu− A is an integer multiple of P. 1 Proof: Start by listing t-1 positive multiplea:of a, a,3a, .p-1a Suppose thatraandsaare the same modulp, then we havr=s(mod p), so tp-1 multiples aabove are distinct and nonzero; that is, they must be congruent to 1, 2, 3, ..p-1 in some order. Multiply all these congruences together and we find a23a..p-1a= 123..(1) (modp) or bettea (p-1) =p-1)! (mop). Divide both sidp-1) to complete the proof. Probability Primality Test A primality test: an algorithm which determines whether a given number is prime. (a)/2) if b is even and b > 0 a= a*(a)b-1)if b is odd 1 if b = 0 Miller-Rabin Primality Test If p is prime and x2 = 1 ( mod p ), then x = +1 or -1 ( mod p ). We could prove this as follows: x= 1 ( mod p ) x- 1 = 0 ( mod p ) (x-1)(x+1) = 0 ( mod p ) Solovay-Strassen Primality Test 2
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'