Mathematical_background_on_Blockchain__GenerativeAI.pptx

In both blockchain and generative AI, a solid mathematical background is essential for understanding the underlying principles, developing new algorithms, optimizing performance, and ensuring the security and reliability of the systems involved. Each field draws from various branches of mathematics to address its unique challenges and goals.
Blockchain relies heavily on cryptographic techniques such as hash functions, digital signatures, and public-key cryptography. These ensure security, privacy, and integrity of transactions and data stored on the blockchain. It is fundamentally a distributed ledger technology where consensus algorithms ensure that all nodes in the network agree on the state of the ledger. The block chain data structure, typically a linked list of blocks where each block contains a cryptographic hash of the previous block, relies on concepts from data structures and algorithms.
Probability and Statistics: Depending on the consensus algorithm (e.g., Proof of Work, Proof of Stake), understanding of probability theory and statistics is necessary to analyze the security and performance of blockchain networks. Many generative AI models are based on probabilistic models such as Gaussian processes, Bayesian networks, and probabilistic graphical models. Understanding probabilities is crucial for generating realistic outputs and estimating uncertainties. Techniques from machine learning, such as neural networks (deep learning), reinforcement learning, and evolutionary algorithms, form the basis of many generative models. Optimization methods like gradient descent and its variants are used for training these models.
Linear Algebra: Generative models often involve high-dimensional data and operations on matrices and vectors. Linear algebra is essential for understanding model architectures and optimizing operations.

1. Mathematical background on Blockchain & Generative AI Dr.A.TAMILARASI Professor, Department of MCA Kongu Engineering College Perundurai , Erode Tamilnadu - 638060 7/29/2024

2. Blockchain is a way of storing data through a network of nodes which work on a peer-to-peer basis, without any central authority, and in a secure way . Cryptography is based on the discrete logarithm problem of both finite fields and elliptic curves Introduction 7/29/2024

3. Basics of Generative AI Generative AI  is a broad term that can be used for any AI system whose primary function is content creation and writing assistance . ChatGpt Image generation : Generative AI tools generate images using text to image AI General Adversarial Networks (GAN) GAN is a combination of two neural network models namely generative and the discriminative. GAN have their root in Game Theory . The training of generators and discriminators is essentially two- player-game or min X max Y f( x,Y ) problem that allows the model to learn complex function N(0,1) Or U(0,1) p Model h q 7/29/2024

4. Matrices Rectangular array of m n numbers arranged in m rows and n columns. Vector is just a n x 1 matrix Linear Algebra & Matrices, MfD 2009 7/29/2024

5. Matrix multiplication Sum over product of respective rows and columns X = = = Define output matrix A B Linear Algebra & Matrices, MfD 2009 7/29/2024

6. Eigen Values and Eigen Vector Eigen values and Eigenvectors (characteristic) are the scalar and vector quantities associated with of a square matrix used for linear transformation. If A is a square matrix of order n × n. If there exists a non-zero column vector V and a scalar such that Av = λv or (A- λI )v = 0, then λ is called Eigen value and V is called Eigen vector corresponding to V Solving the above equation we get various values of λ as λ 1 , λ 2 , …, λ n  called the Eigen values and we get individual eigenvectors related to each Eigen value. 7/29/2024

7. 7/29/2024

8. 7/29/2024

9. Statistical Parametric Map Parameter estimates Deep Learning Model Pre processing Design matrix Statistical Inference p <0.05 7/29/2024

10. Design matrix. Manipulation of matrices enables unknown values to be calculated = + e + Y X data vector design matrix parameters error vector ´ = the betas (here : 1 to 9) Linear Algebra & Matrice , MfD 2009 +  = N of scans 7/29/2024 Y = X . β + ε Observed = Predictors * Parameters + Error = Design Matrix * Betas + Error

11. Number System Natural Number : N = { 1,2, 3,…} Construction of Integers from Natural Numbers : The familiar properties addition and multiplication in Z will be derived from those of N. In N, there is no element . So subtraction is not always possible . 7/29/2024

12. Integers Z Divisibility in Z: An integer a  0 is called a divisor of an integer b if there exists an integer c such that b = ac and b is called an integral multiple of a. In symbol we write a|b and read as a divides Division Algorithm and its Properties: Let a and b be integers with b > 0. Then there exist a unique integers q, r such that a = qb + r, where 0 ≤ r < b. The integer q is called quotient, r is called reminder . a is called the dividend , b is called the divisor. If r = 0 , then we say b divides a or a is divisible by b . The quotient and reminder can be expressed as : q =a div b, r = a mod b ( r = a- qb or a-r = qb or b|a -r ) + 1 and -1 divide all integers a|0 for all a  Z – {0} a|b , a|c  a | ( b+c ) a|b , a|c  a | bc a|b , a|c  a | (lb + mc) where l, m Z Numbers divisible by 2 is called even integers b 7/29/2024

13. Proof of Division Algorithm Proof : We need to prove two things. One is existence of q , r, second is they are unique . How can we be guaranteed that this smallest element exists? By well-ordering principle we know that any non-empty set of non-negative integers contains a least element . In general, for an arbitrary element a and b with b > 0, 7/29/2024 Construct S = { a – bx : a – bx  0}. If a  0, then a – 0b = a S. If a < 0, then a – 2ab = a (1 – 2b)  S, so S is non empty. By well ordering principle S has a least element, call as r. That is, r = a – bq for some integer q. Since r  S, r  0. We must show that r < b. On contrary we take r  b. Then r – b  0, but r = a – bq , so r-b = a- bq -b = a – b(1+q)  0, so a – b(1+q) S, but a – b(1+q) < r , which is a contradiction, since r is a smallest element. So r < b.

14. Relation on sets Relation: R: A  B is said to a binary relation if R  A  B. Any element in R is of the form (a, b) or aRb . Properties : 1) A binary relation on a set A is said to be reflexive if ( a,a ) R , for all a A . 2) A binary relation on a set A is said to be symmetric if ( a,b )  R implies ( b,a )  R, for all a,b  A. 3) A binary relation on a set A is said to be transitive if ( a,b )  R, (b, c)R implies ( a,c ) R, for all a,b , c A . A binary relation R on a set A is said to equivalence relation if R is reflexive, symmetric and transitive. Equivalence Class : For aA , the equivalence class determined by a is defined by [a] = = { b  A : ( a,b )R} Since ( a,a ) R, a[a], so any equivalence class is non-empty. The union of all equivalence classes are the given set A and [a]  [b] =    7/29/2024

15. Congruence Example : Consider the relation R defined on Z by xRy  x-y is multiple of 3. Then the equivalence classes are [0], [1], [2]. 0, 3, 6, 9, 12, 15,…… 3k 1, 4, 7, 10, 13, 16 …….. 3k +1 2, 5, 8, 11, 14, 17 …. 3k +2 The division algorithm defines a natural congruence relation on the integers. For a positive integer n , two integers a and b are said to be congruent modulo n (or a is congruent to b modulo n ), if a − b is divisible by n. It can be expressed as a ≡ b mod n . n is called the modulus . Example : 38 ≡ 23 mod 15, as 15|(38 -23) or 38 = 15*2 + 8 23 = 1*15+ 8, -8 ≡ 2 mod 5, as -8 = -2*5+2 and 2 = 0*5+2 ; Properties : 1. a ≡ a mod n. 2 . a ≡ b mod n then b ≡ a mod n. 3 . If a ≡ b mod n and b ≡ c mod n, then a ≡ c mod n  is an equivalence relation . 7/29/2024

16. Congruence So, for each positive integer n, congruence modulo n is an equivalence relation on Z. The equivalence classes are called congruence classes and denoted by Z n , Z n = { , , … , } They form a partition of Z Theorem : If a ≡ b mod m, c ≡ d mod m. Then a+c ≡ (b + d) mod m ac ≡ ( bd ) mod m Example : 7 ≡ 2 (mod 5) and 11 ≡ 1 (mod 5), it follows that 18 ≡ 3 (mod5) and 77 ≡ 2 (mod 5 ).   7/29/2024

17. Hash Function It is just application of the modulus operator. That is remainder of dividing the key by the total number of items that could be contained in the list A hashing function h assigns memory location h(k) to the record that has k as its key. h(k)  k mod m, where m is the number of available memory locations. Hash functions are mathematical functions that transform or "map" a given set of data into a bit string of fixed size, also known as the "hash value To accept an input of arbitrary length and output a fixed length result To manipulate data irreversibly. The input cannot be derived from the output 7/29/2024

18. Fundamental theorem of Arithmetic Any integer n > 1 can be written as a product 7/29/2024

19. Generalized Division Algorithm: Let a, b  Z and a  0. Then there exists integers q, r uniquely such that b = aq + r where 0  r < |a | Greatest Common Divisor : Let a|b & a|c , then a is called a common divisor of b and c. The greatest common divisor (GCD) of a, b is a non-negative integer d such that d|b , d|c , then a|d . Any two integers a and b have a unique GCD and it is of the form ax+by , where x, y  Z. The GCD of a and b is denoted by ( a,b ). Example : What is the greatest common divisor of 24 & 36. The positive common divisor of 24 and 36 is 1,2,3,4,6,12. Hence GCD(24,36) = 12 7/29/2024

20. GCD Definition : The integers a and b are relatively prime if their greatest common divisor is 1. Example : 17 and 22 are relatively prime. Definition : The integers a 1 , a 2 , ...,a n are pairwise relatively prime if GCD( a i , a j ) = 1 whenever 1≤ i <j ≤ n Determine whether the integer 10,17 and 21 are pairwise relatively prime and whether the integers 10,19 and 24 are pairwise relatively prime . GCD(10,17) = 1, GCD( 10,21) = 1, GCD(17,21) = 1, so the integers are pairwise relatively prime. But GCD(10,24) = 2>1, so 10,19,24 are not pairwise relatively prime. 7/29/2024

21. Another way to find greatest common divisor of two integer is to use the prime factorization of the integers a and b, neither equal to zero a =   …  , b =   …  where each exponent is a non-negative integer, and where all primes occurring in the prime factorization of either a or b are included in both factorizations, with zero exponents if necessary. Then GCD(a, b) =  …. where min( x,y ) represents the minimum of two integers x and y. Example : GCD(120,500) = 2 min(3,2) 3 min(1,0) 5 min(1,3) = 2 2  3  5 1 = 20   7/29/2024

22. Euclidean Algorithm Euclidean algorithm : It describes a method to find the GCD of any two integers a and b. Proof: Case 1 : If b = 0, then obviously (a,0) = |a|. Case 2 : If b  0, by the generalized division algorithm, b = aq 1 + r 1 , where 0  r 1 < |a|. If r 1 = 0, a|b , hence GCD ( a,b ) = a. If r 1 > 0, then we have the following steps . let a = r 1 q 2 + r 2 , where 0 ≤ r 2 < r 1 . If r 2 = 0, then r 1 |a and r 1 | aq 1 + r 1 = b. Thus r 1 |a and r 1 |b. Hence GCD( a,b ) = r 1 . If r 2 > 7/29/2024

23. r 1 = r 2 q 3 + r 3 , where 0 ≤ r 3 < r 2 . ------------------------------------ r k-2 = r k-1 q k + r k , where 0 ≤ + r k <r k-1 , where r 1 > r 2 > ...... be chain of descending non-negative integers, we get r n+1 = 0 for some n. In this case r n-1 = r n q n + 0. Hence r n |r n-1 where r n  r n-1  r n-2  … r 1  r . Thus GCD(a, b) = GCD(r 1, a) = GCD(r 2 , r 1 ) =.... = r n 7/29/2024

24. Theorems Extended Euclidean Theorem : Let a and b be integers, and d = gcd (a, b). Then, there are x, y ∈ Z such that ax + by = d. Theorem : If p is a prime integer and p | (a · b), then either p|a or p| b. If p/a, then theorem is satisfied. If p does not divide a . Since p is prime, GCD( p,a ) = 1, by above theorem px + ay = 1. Multiply both sides by b, then p( xb ) + ( a.b )y = b. Hence the result 7/29/2024

25. Example 1) Find GCD( 91, 287) using Euclidean algorithm . Solution : First divide the largest integer 287 by 91, to obtain 287 = 91 x 3 + 14, 0  14 < 91 . 91 = 14 x 6 + 7, 0  7< 14, 14 = 7x 2 + 0. So GCD(7,14) = 7 , further GCD(91, 287) = GCD(14, 91) = GCD(7,14) = 7 Find GCD( 414, 662) using Euclidean algorithm, Solution : 662 = 414 . 1 + 248, 0  414 < 248 414 = 248 .1 + 166, 0  166 < 248, 248 = 166 .1 + 82, 0  82 < 166 166 = 82 . 2 + 2, 0  2 < 82 82 = 41 . 2 + 0, 0  2 GCD(414 , 662) = 2, because 2 is a non-zero remainder. 7/29/2024

26. Modular exponentiation The operation of modular exponentiation calculates the remainder when b e is divided by a positive integer m In symbols, given base b, exponent e, and modulus m, the modular exponentiation c is: c = b e mod m , where 0 ≤ c < m . Ex: Given b = 5, e = 3 and m = 13, 8 = 5 3 mod 13, 0≤ 8 <13 Inverse of Modular exponentiation are given by c  b e mod m  d − e mod m, such that b⋅d ≡1mod m. Consider the problem 7/29/2024

27. Consider the situation to find the reminder of 10,100,1000,… dividing by 3 is 1. i.e : 10 1  1 mod 3; 10 2  1 mod 3; … What happened when we divide 10 51239209 by 3. Similarly 7 132561 divide it by 4? When we divide 7 by 4, we can get reminder as 3; 7 2 by 4 we get the reminder as 1; 7 3 by 4 we get the reminder as 3; If n is odd, 7 n  3 mod 4; and if n is even, 7 n  1 mod 4, and since 132561 is odd number, 7 132561 leaves the reminder as 3 when it is divided by 4. Every sequence of powers a 1 , a 2 , a 3 , … mod m, follows a repeating pattern. When we divide it by m the reminders are {0,1,2,…m-1} If 0 appears in the pattern, then all the subsequent reminders will be 0 7/29/2024

28. To understand better, let a n  mod m, then we compute a n+1 a n  a  (0  a) mod m  0 mod m It is easy to see any one of these m-1 numbers can appear at most once in a repeating pattern. Exponentiation is performed by repeated multiplication as in ordinary arithmetic Example: 11 7 mod 13 11 7 = 11  11 2  11 2  11 2 11 2  4 mod 13, 11 7 = 11  4 4 4 4 4 4 = 12 mod 13 11 7 = 11  12 = 2 mod 13 7/29/2024

29. Fermat’s Little Theorem If p is a prime number and a is a natural number, and if p a , p does not divide a, then  1 (mod p ) The theorem is easily proved using mathematical induction on a . Suppose p divides a p –a. i.e p divides a(a p-1 - 1). Then prove it for (a+1) p – (a+1). The proof uses the concept of binomial theorem . Examples : 1) a = 2, p =7, then 2 7-1 1 mod 7, i.e 64 -1 = 63 is divisible by 7. 2) What is the remainder of 50 72 when divided by 73? Since 73 is a prime number, and since 50 is not a multiple of 73, then we have 50 72 - 1  0 (mod 73). So the remainder of 50 72 when divided by 73 is 1.   7/29/2024

30. Euler Theorem Euler’s Totient function: The function :N  N defined by (n) = the number of integers less than n and relatively prime n is called Euler’s totient function . We define (1) = 1 . Euler's Theorem  states that if  GCD ( a , m ) = 1, then  a φ ( m )  ≡ 1 (mod  m ) Proof : Using fundamental theorem of arithmetic, we can prove the theorem. Example : (12) = 4, GCD(a,12) =1, then a 4  ≡ 1 mod12   7/29/2024

31. Algebraic structure Function of Sets: Let A and B be two sets and f is said to be a function from A to B, written as f: A  B, if for every element a A , there exists a unique element b B, such that f(a) = b . Inverse function is not always possible Example: f: Z  Z, f(x) = 2x, for every xZ 7/29/2024

32. Function of Sets.. In a public key cryptosystem, each member A of the network has two keys: a private key s A produced by himself, and a public key p A published in a directory. The public key p A is related to s A by a (publicly known) one way function. If some additional information is given, we can define f -1 : B  A f  is said to be a trapdoor function , if there exists some secret information  b , such that given  f(a)  and  b  it is easy to compute  a 7/29/2024

33. A group is a set G equipped with a binary operation ∗ such that the following properties hold:   For all a, b ∈ G, the element a ∗ b is in G; ( Closure ) For all a, b, c ∈ G, a ∗ (b ∗ c) = (a ∗ b) ∗ c ; ( Associativity ) For all a ∈ G, there exists e ∈ G such that a ∗ e = e ∗ a = a ;For each a ∈ G, there exists an inverse element a −1 ∈ G such that a ∗ a −1 = a −1 ∗ a = e; Moreover, the group is such that for all a, b ∈ G, a ∗ b = b ∗ a, then the group is called abelian (commutative ). Example : (Z, +) , (Q, +) , (R, +), (C,+) are groups (R, ), (Q, ), (C, ) are groups, (N, +) is not a group A subset H of a group is called a subgroup if H is closed under the binary operation in G, H itself is a group Example: (Q, +) is a subgroup of (R, +) nZ = { nx : x Z } is a subgroup of Z under the operation +   Group 7/29/2024

34. Cyclic group Let a  G . The least positive element n such that a n = e, is called order of a, denoted by O(a ) A group  G is said to be cyclic , if there exist an element g in G such that every elements of G generated by g. That is G = { g k  |  k  ∈  Z }. O(G) = O(g) = k, G = <g> For a  finite cyclic group   G  of order  n  we have  G  = { e ,  g ,  g 2 , ...   g n − 1 } A   cyclic group  has one or more than one generators Example: Consider the group (Z 12 , ) has exactly 4 generators, 1,5,7,11. Theorem : The generators of a cyclic group of order n are all the elements a p , p being prime to n and 0<p<n. Proof : ( a p ) n = (a n ) p = e. Hence the result 7/29/2024

35. Cyclic group Let G be a cyclic group generated by a of order n , then G is generated by a m if and only if (m , n) = 1, m and n are relatively prime. Hence the number of generators of a cyclic group of order n is (n ). Proof : Given G = (a) of order n . Also given that m, n are relatively prime. So there exist integers r & s such that ( rm + sn ) = 1 . Therefore, a = a¹ = a ( rm+sn ) = (a m ) r . (a n ) s = (a m ) r . Let H be a subgroup of a group G. Let aG . Then the set aH = {ah: h H} is called left coset of H defined in G. Similarly we define right coset by Ha = {ha: h H} 7/29/2024

36. G is a underlying set of a group. Coset gives the notion of how the cosets divide the set G. The number of elements in left coset and right coset are equal. For example take G = (Z 12 ,  ), H = {0,4,8} is a subgroup of G. Then the left cosets of H are 0+H= {0,4,8} = H, 1 +H = {1,5,9}, 2+H = {2, 6,10}, 3+H = {3,7,11}, 4+ H= {4,8,0} = H, 5 +H = { 5,9,1} = 1+H Theorem 1 : Let G be a group of order n, and aG . Then a n = e Proof : Let the order of a be m. Then m divides n. Hence n = mq . So a n = a mq = (a m ) q = e q = e Euler’s Theorem : If n is an integer and if  GCD ( a , n ) = 1, then  a φ ( n )  ≡ 1 (mod  n ) 7/29/2024

37. Proof : Let G = { m: m < n and GCD( m,n ) = 1}. Then G is a group under multiplication modulo n of order (n). Hence a  (n )  1 mod n Fermat’s Theorem : p is prime and a is an integer prime to p. Then a p-1  1 mod p. Proof : In Theorem 1, replace a by its reminder on division by n. If n and p are relatively prime, then (p) = p-1. Then apply Euler Theorem, we get a p-1  1 mod p Normal Subgroup A subgroup H of G is normal iff aH = Ha for all a  G Quotient group : Let G be a group H a normal subgroup of G. Then G/H the set of all right cosets of H in G. That is G/H = {Ha: aG }. Then G/H is a group under the operation (Ha)( Hb ) = Hab. We call the group as quotient group of G modulo H. The cosets are the residue classes of G modulo H Example : Z/3Z = { 0+3Z,1+3Z,2+3Z} is a factor group . 7/29/2024

38. 7/29/2024

39. The Discrete Logarithm Problem For a group G and an element g ∈ G. The Discrete Logarithm Problem (DLP) for G is stated as: Given an element h in the subgroup generated by g, find an integer m such that h = g m . The smallest element m satisfying h = g m is called logarithm or index of h with respect to g and is written as m = (h) The Discrete Logarithm Problem is used as in many cryptographic constructions, including key exchange, encryption, digital signatures, and hash functions .   7/29/2024

40. Rings & Field A ring (R, +, ·) is a set R together with two binary operations + and · such that: R is an abelian group with respect to + ; · is associative ; For all a, b, c ∈ R,   a · (b + c) = a · b + a · c and ( b + c) · a = b · a + c · a . A ring is commutative if · is commutative. A ring is called a division ring if the nonzero elements of R form a group under ·. A commutative division ring is called a field . If R is a commutative ring, then a  0 R is said to be a zero divisor if there exists b R, b  0, such that ab = 0. A commutative ring is an integral domain , if it has no zero divisors . A finite integral domain is a field . 7/29/2024

41. Field Examples of fields : R , Q , C , Z p (the field of integers modulo a prime p ). A finite field or Galois field is simply a field with a finite number of elements The  characteristic of a ring or Field R is defined to be the smallest number of times one must use the ring's multiplicative identity (1) in a sum to get the additive identity (0). If this sum never reaches the additive identity the ring is said to have characteristic zero. 7/29/2024

42. Characteristic of a field Consider the numbers 2 = 1+1, 3 = 1+1+1, 4 = 1+1+1+1, 5 = 1+1+1+1 +1, … p times = 0, p is a prime number, and we say that field K has characteristic p Theorem : Let F be a field. Then the characteristic of a field is either 0 or a prime. Proof: If Char(F)  0. Let the characteristic be n, not a prime. Then n = pq , where 0<p<n and 0<q<n. Now n.1 = pq.1 = (p.1)(q.1) = 0, since F is an integral domain either p.1 = 0 or q.1 = 0. Since p,q < n, this contradicts the characteristic of F .   7/29/2024

43. Finite Fields A finite field of order q exists  if and only if q is a prime power p k  (where p is a prime number and k is a positive integer). In a field of order p k , adding p copies of any element always results in zero; that is, the characteristic of the field is p. Example : Consider the field F 2 , the finite field with two elements. Let the elements be 0, 1. The addition law is given by 0 + a = a + 0 = a and 1 + 1 = 0. The multiplication law is given by 1 · a = a and 0 · a = 0. 1 is invertible and its inverse is given by 1 since 1 · 1 = 1. 7/29/2024

44. Finite field In general Z/ nZ is not in a field. Theorem : Z/ nZ is a field if and only if n is prime. Solution : Let n is prime. So any element a 0 in Z/ nZ are not multiple of n, i.e a and n are coprime, b y Extended Euclidean Theorem, there exist b, c in Z such that ba + cn =1, so ab  1 mod n. So b is a multiplicative inverse of a. Conversely, let Z/ nZ is a field. Let n is not prime. Then n = ab. So ab  mod n, That is [a] = 0 or [b] = 0, which contradicts that Z/ nZ is an integral domain. 7/29/2024

45. Elliptic curve Non- singluar Elliptic curve over R E = {( x,y )  R × R : y 2 = x 3 + ax + b, a,b R, 4a 3 + 27b 0}  { O called the point at infinity} Similarly we define Non- singluar Elliptic curve over Z p as E = {( x,y )  Z p × Z p : y 2 = (x 3 + ax + b) mod p, a,b  Z p , 4a 3 + 27b 0}  { O called the point at infinity} 7/29/2024

46. Given P = (x 1 , y 1 )  O and Q = (x 2 , y 2 )  O, then P + Q = O if and only if x 1 = x 2 and y 1 = −y 2 ; thus −(x , y) = (x , −y). λ as the slope of the line is λ = (y 1 − y 2 )/(x 1 − x 2 ) if P  Q (3x 1 2 + a)/(2y 1 ) if P = Q. Then P + Q = R, where R = (x 3 ,y 3 ) with x 3 = λ 2 − x 1 − x 2 and y 3 = −λx 3 − y 1 + λx 1 . Similarly we define addition of two points P + Q = R = (x 3 , y 3 )  Z p × Z p λ = (y 1 − y 2 )(x 1 − x 2 ) -1 mod p if P  Q (3x 1 2 + a) (2y 1 ) -1 mod p if P = Q E is an abelian group with identity element O 7/29/2024

47. Adding Points on an Elliptic Curve We define the sum of P and Q on E to be the reflected point. We denote it by P ⊕ Q or just P + Q. How do we add a point P to itself, since there are many different lines that go through P ?. If we think of adding P to Q and let Q approach P , then the line L becomes the tangent line to E at P . L is a tangent to E at P 7/29/2024

48. Example : y 2 = (x 3 + x + 1) mod 23 where x 3 + x + 1 mod 23 ranges from {0,1,2,..22}. If P =(13,7), then –P = (13,-7) = (13, 23 + (-7)) = (13,16) Let P =(3,10), Q = ( 9,7), find P +Q x 3 = [(7 – 10)/(9 – 3)] 2 -3-9 = ¼ - 12 = ¼ + (23 -12) = ¼ +11 = 1  + 11 = 17 , We find mod 23, we know 6  4 = 24  1 mod 23, so 6 and 4 are inverse to each other. y 3 = -10 + (-1/2) 3 - (-1/2) 17 -10 + (1/2) [17 -3] = 23 + (-10) + 7 = 13 + 7 = 20 Compute 2P. = (39 +1)/210 = 7/5; x 1 = (28/20) 2 – 3-3 = (5/20) 2 + 17 = (1/4) 2 +17 = 6 2 + 17 = 7; y 1 = 12   7/29/2024

49. Example How to find points on the elliptic curve y 2 = (x 3 + ax + b) mod 11 for a curve E 11 (1,6) = y 2 = (x 3 + x + 6) mod 11 (2, 4), (2,7), (3,5), (3,6) (5, 2), (5,9), (7,2), (7,9), (8,3), (8,8), (10, 2), (10,9) x x 3 + x +6 y y 2 6 1 8 1 1 2 5 2 4 3 3 3 9 4 8 4 5 5 4 5 3 6 8 6 3 7 4 7 5 8 9 8 9 9 7 9 4 10 4 10 1 7/29/2024

50. ECC Algorithm y 2 = x 3 + ax + b is an elliptic curve E q ( a,b ): Elliptic curve with parameters a , b and q a prime number or integer of the form 2 m . G: point on the elliptic curve whose order is large value of n. User A: key Generation : select private key n A < n Calculate public key p A = n A × G User B: key Generation : select private key n B < n Calculate public key p B = n B × G 7/29/2024

51. ECC Algorithm ECC Encryption : Let the message be M. First encode this message M into a point on the elliptic curve. Let this be P M . For encryption choose a random positive integer k, and public key of B. The cipher point will be C M = ( kG , P M + kp B ), This point will be send to the receiver Decryption : Here multiply 1 st point in the pair with receiver secret key, i.e kG × n B . For decryption use private key of B Then subtract it from 2 nd point in the above pair. That is, P M + kp B – ( kG × n B ) = P M + kp B – kp B = P M , as p B = G × n B So receiver get the same point. 7/29/2024

52. RSA Algorithm Key Generation: Select two large prime numbers p and q Calculate n = p  q Calculate (n) = (p-1)(q-1) Choose e such that 1< e < (n) and GCD( (n) ,e) = 1 Calculate d e -1 mod (n) such that ed  1 mod (n) 6. Public key = { e,n } 7. Private key = {d, n} Encryption: Let M < n // cipher text C  M e mod n Decryption: M  C d mod n Let p = 3, q= 11 Then n = 3 * 11 = 33 (n ) = 2 * 10 = 20 Choose e =7 as 1< 7< 20 and GCD(7,20) = 1 Now 7d 1 mod 20 7*3 -1 = 0 i.e d= 3 Let M = 31<33 C 31 7 mod 33 C= 4; M4 3 mod 33 M =31 7/29/2024

53. Diffie -Hellman Key Exchange Public Knowledge: Group G and element g, prime p B= g b mod p A = g a mod p 7/29/2024

54. Example x  9 4 mod 23 23| 6561  6561 = 23x 285 + r 6561 = 6555 + r  r = 6 y  9 3 mod 23 23| 729  y = 16 7/29/2024

55. Probability Used to quantify likelihood or chance Used to represent risk or uncertainty in engineering applications. It can be interpreted as our degree of belief or relative frequency Random experiment  is a mechanism that produces a definite outcome that cannot be predicted with certainty. The sample space associated with a random experiment is the set of all possible outcomes. An event is a subset of the sample space 7/29/2024

56. Basics  An event associated with a random experiment is a subset of the sample space. Example : The outcomes could be labeled H for head and   T for tail. Then the sample  space is the set: S={H,T} The sample  space is the set S={1,2,3,4,5,6} with a single die is thrown The probability of any outcome is a number between 0 and 1. The probability of any event A is the sum of the probabilities of the outcomes in A. Two events are said to be mutually exclusive if they cannot occur at the same time or simultaneously. If A and B are the two mutually exclusive events, then P( A  B) = 0 or A  B =  7/29/2024

57. The outcomes which make necessary the happening of an event in a trial are called favorable events . For example; if two dice are thrown, the number of favorable events of getting a sum 5 is four, i.e., (1, 4), (2, 3), (3, 2) and (4, 1). Exhaustive events in probability refer to a collection of events that together cover all possible outcomes of an experiment or situation Mathematically, if  E 1 ​,  E 2 ​, …….,  E n ​  are exhaustive events, their union ( E 1 ​ ∪  E 2 ​ ∪ …… ∪ E n ​) equals the entire sample space ( S ). 7/29/2024

58. Probability is the measure of likelihood of an event to occur P(A) = Favorable number of cases Exhaustive number of cases 7/29/2024

59. Probability is the measure of likelihood of an event to occur P(A) = Favorable number of cases Exhaustive number of cases 7/29/2024

60. | Example 1: What is the chance that a non-leap year should have 53 sundays ? Non-leap year = 365 days In 365 days, Number of weeks = 52 weeks and 1 day is remaining. For 52 weeks number of Sundays = 52 1 remaining day can be Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday. Total of 7 outcomes, the favourable outcome is 1. ∴ probability of getting 53 Sundays = 1 / 7. 7/29/2024

61. | Example 1: Similarly, What is the chance that a Leap year should have 53 sundays ? leap year = 366 days In 366 days, Number of weeks = 52 weeks and 2 days are remaining. For 52 weeks number of Sundays = 52 2 remaining days can be Sunday, Monday or Saturday, Sunday. Total of 7 outcomes, the favourable outcome is 2. ∴ probability of getting 53 Sundays = 2/ 7. 7/29/2024

62. | Example 2: A lot consists of 10 good articles, 4 articles with minor defects and 2 with major defects. Two articles are chosen at random. find the probability that : both are good At least 1 is good At most 1 is good Neither have major defects Solution The exhaustive no. of cases – 2 articles can be chosen from 16 articles in 16C 2 ways 7/29/2024

63. | ( a) both are good Exhaustive no. of cases = 16C 2 = 120 Both articles chosen need to be good articles (10 good articles), so favorable no. of cases = 10C 2 = 45 ∴ probability of both articles being good= 45/120 = 3/8. ( b) At least 1 is good Exhaustive no. of cases = 16C2 = 120 1 or more articles need to be good, So chance that 1 is good and 1 is defective = 10C1 . 6C1 chance that both are good = 10C 2 Favorable no. of cases = 1 is good or 2 are good = (10C 1 .6C 1 )+10C 2 ∴ probability of at least 1 article being good=7/8 7/29/2024

64. Two events A and B are said to be independent if: P(A  B ) = P(A)  P(B) Example : If a ball is drawn from a box which consists of number of colored balls and replace before the next ball is drawn. Here the second draw is independent of the first draw. 7/29/2024

65. Theorem: If A and B be Independent Events. Then the complement of A, namely A c and complement of B namely B c are independent Proof: Let A and B be independent Events. Then, P(A  B) = P(A). P(B) P(Ac  B c ) = P [ (A B) c ] = 1 – P(AB) = 1 – [ P(A) + P(B) –P(A  B) ] = 1 – [ P(A) + P(B) –P(A) P(B)] = [1 – P(A) ] - P(B)[ 1 –P(A)] = [1 – P(A) ] [1 – P(B) ] = P(A c ) P( B c ) Hence, A c and B c are independent 7/29/2024

66. The Conditional Probability of an event B assuming that the event A has happened already is defined by P(B/A) = P(A  B) P(A) Example: When a uniform die is thrown the conditional probability of getting 1 (Event B) , given that odd number has already obtained (Event A) is P(B/A) = P(A  B) = 1/3, P(A) Where S = {1,2,3,4,5,6}, A = {1,3,5}, B ={1}, P(A  B) = 1/6, P(A) = 3/6 7/29/2024

67. Example P(A  B) = 0.1, P(A  B c ) = 0.4, P(A c  B c ) = 0.3, find P(B) and P(B/A) Solution: We know that the total probability = 1. That is 0.4 + 0.1 +0.3 + P( B  A c ) = 1  P( B  A c ) = 0.2. Then P(B) = P( A  B) + P( B  A c ) = 0.3 P(B/A) = P(A  B) = 0.1/0.3 =0.333 P(A) A 0.1 B 0.4 0.3 7/29/2024

68. Probability Formulas Product rule Sum rule Bayes theorem Theorem of total probability, if event Ai is mutually exclusive and probability sum to 1 7/29/2024

69. 7/29/2024

70. Hypotheses:  Events happening in the sample space  E 1 , E 2 ,… E n  is called the hypotheses 7/29/2024 Given a hypothesis h and data D which bears on the hypothesis: P(h): independent probability of h: prior probability P(D): independent probability of D P( D|h ): conditional probability of D given h: likelihood P( h|D ): conditional probability of h given D: posterior probability

71. Example There are three urns containing 3 white and 2 black balls; 2 white and 3 black balls; 1 black and 4 white balls respectively. There is an equal probability of each urn being chosen. One ball is equal probability chosen at random. what is the probability that a white ball is drawn? Let E 1 , E 2 , and E 3  be the events of choosing the first, second, and third urn respectively. Then, P(E 1 ) = P(E 2 ) = P(E 3 ) =1/3 Let E be the event that a white ball is drawn. Then, P(E/E 1 ) = 3/5, P(E/E 2 ) = 2/5, P(E/E 3 ) = 4/5. By theorem of total probability, we have P(E) = P(E/E 1 ) . P(E 1 ) + P(E/E 2 ) . P(E 2 ) + P(E/E 3 ) . P(E 3 ) ⇒ P(E) = (3/5 × 1/3) + (2/5 × 1/3) + (4/5 × 1/3) ⇒ P(E) = 9/15 = 3/5 7/29/2024

72. Random Variable A random variable is a real valued function defined on a sample space S. In a particular experiment, a random variable X: S  R, would be some function that assigns a real number X(s) for each possible outcome s S A discrete random variable can take a countable number of values. A continuous random variable can take any value along a given interval of a number line. 7/29/2024

73. Probability Distributions, Mean and Variance for Discrete Random Variables The probability distribution of a discrete random variable is defined as a function that specifies the probability associated with each possible outcome the random variable can assume. i ) p(x) ≥ 0 for all values of x 2) p(x) = 1 The mean , or expected value , of a discrete random variable is The variance of a discrete random variable x is 7/29/2024

74. Bernoulli Distribution A trial with only two possible outcomes is used so frequently as a building block of a random experiment that it is called a Bernoulli trial . Let p denote the probability of success and q = 1-p is the probability of failure, then P(X = x) = p x (1-p) 1-x , x = 1, 0 0 otherwise 7/29/2024

75. Binomial Distribution 7/29/2024

76. 7/29/2024

77. Mean and Variance of Binomial Distribution 7/29/2024

78. Example Say 40% of the class is female. What is the probability that 6 of the first 10 students walking in will be female? 7/29/2024

79. The Poisson Distribution Evaluates the probability of a (usually small) number of occurrences out of many opportunities in a period of time, area, volume, weight, distance and other units of measurement  = mean number of occurrences in the given unit of time, area, volume, etc. Mean µ = , variance:  2 =  7/29/2024

80. Example 7/29/2024 Say in a given stream there are an average of 3 striped trout per 100 yards. What is the probability of seeing 5 striped trout in the next 100 yards, assuming a Poisson distribution?

81. Continuous Probability Distributions A continuous random variable can take any numerical value within some interval. A continuous distribution can be characterized by its probability density function . For example: for an interval (a, b], The function f (x) is called the probability density function of X. Every p.d.f . f ( x ) must satisfy 7/29/2024

82. Normal Distribution 7/29/2024

83. Continuous Random Variables … The probability determined from the area under the curve f(x) 7/29/2024 If a random variable X has a continuous distribution for which the p.d.f . is f(x), then the expectation E(X) and variance Var (X) are defined as follows:

84. The Uniform Distribution on an Interval For two values a and b Mean and Variance 7/29/2024

85. The Normal Distribution The probability density function f(x): µ = the mean of x,  = the standard deviation of x 7/29/2024

86. Standard Normal Variable 7/29/2024 Example: Say a toy car goes an average of 3,000 yards between recharges, with a standard deviation of 50 yards (i.e., µ = 3,000 and  = 50) . What is the probability that the car will go more than 3,100 yards without recharging?

87. 7/29/2024

88. Example 7/29/2024 P(x>13) = P(Z> (13-10)/ 2 ) = P(z>1.5) = 0.5 – P(0  z  1.5) = 0.5 – 0.4332 = 0.0668

89. Two dimensional Random Variable Joint Distributions 7/29/2024

90. Joint Probability Distributions In general, if X and Y are two random variables, the probability distribution that defines their simultaneous behavior is called a joint probability distribution . The joint probability distribution of two discrete random variables X,Y is usually written as f XY ( x,y )= Pr(X=x, Y=y). The joint probability function satisfies 7/29/2024

91. Example 1 X can take only 1 and 3; Y can take only 1,2 and 3 ; and the joint probability function of X and Y is: 7/29/2024 Compute P(X ≥2, Y≥2 ) P(X ≥2, Y≥2)=P(X=3,Y=2)+P(X=3,Y=3)=0.2+0.3=0.5 (2) Compute Pr(X=3) P(X =3)=P(X=3,Y=1)+P(X=3,Y=2)+P(X=3,Y=3)=0.2+0.2+0.3=0.7

92. Continuous Joint Distributions A joint probability density function for the continuous random variables X and Y, denotes as f XY ( x,y ), satisfies the following properties: 7/29/2024

93. Continuous Joint Distributions - Example Calculating probabilities from a joint p.d.f . 7/29/2024

94. Covariance and Correlation Coefficient The covariance between two RV’s X and Y is Properties: The correlation Coefficient of X and Y is 7/29/2024

95. Covariance and Correlation (Example 1) 7/29/2024

96. Zero Covariance and Independence However, in general, if Cov (X,Y)= , X and Y may not be independent. Example : X is uniformly distributed on [-1,1], Y=X 2 . Then, Cov (X,Y)= , but X determines Y, i.e., X and Y are not independent. If X and Y are independent, then Cov (X,Y)= . 7/29/2024

97. Functions of Random variable 7/29/2024 Central Limit Theorem

98. Statistical Inference 7/29/2024 Statistical Inference makes use of information from a sample to draw conclusions about the population from which the sample was taken Two ways of Inference Estimation of parameters * Point Estimation ( X or p) * Intervals Estimation Hypothesis Testing. What is Hypothesis? An assumption about the population parameter The standard deviation of a statistic is called a standard error

99. 7/29/2024

100. 7/29/2024

101. 7/29/2024

102. 7/29/2024 Z = X – E(X) S E(X)

103. 7/29/2024 Test for single mean

104. Thank You 7/29/2024