{"id":1400,"date":"2010-12-11T22:34:23","date_gmt":"2010-12-12T02:34:23","guid":{"rendered":"http:\/\/www.acarlstein.com\/?p=1400"},"modified":"2010-12-16T14:53:32","modified_gmt":"2010-12-16T18:53:32","slug":"introduction-to-network-security-%e2%80%93-part-9","status":"publish","type":"post","link":"http:\/\/blog.acarlstein.com\/?p=1400","title":{"rendered":"Introduction to Network Security \u2013 Part 9"},"content":{"rendered":"

NOTIFICATION:<\/strong> <\/strong>These examples are provided for educational purposes. The use of this code and\/or information is under your own responsibility and risk. The information and\/or code is given \u2018as is\u2019. I do not take responsibilities of how they are used. You are welcome to point out any mistakes in my posting and\/or leave a comment.<\/p>\n

Some of the mathematical tools (known as number theory) use in network security are prime numbers, greatest common divisor (GCD), Fermat’s theorem, Euler Totient function and theorem, primality testing and Miller Rabin algorithm.<\/p>\n

Prime Number<\/strong><\/p>\n

A prime number is an integer p<\/em> greater than 1 which can only be divided by 1 and itself.<\/p>\n

Formally speaking:<\/p>\n

“A prime number (or prime integer, often simply called a “prime” for short) is a\u00a0positive integer<\/a> \"p>1\" that has no positive integer\u00a0divisors<\/a> other than 1 and\u00a0\"p\" itself. ” <http:\/\/mathworld.wolfram.com\/PrimeNumber.html<\/a>><\/p>\n

An example of prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, …<\/p>\n

An example of numbers that are not prime: 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, …<\/p>\n

In the website Math.com you can find a prime number calculator that can tell you if a number is prime or not: <http:\/\/www.math.com\/students\/calculators\/source\/prime-number.htm<\/a>><\/p>\n

One of the ways we can use prime numbers is to factorize a number in a unique way:<\/p>\n

Any number a<\/em> greater than 1 can be factored in a unique way using prime p<\/em> numbers while each consecutive prime number is greater than the previous prime number and their consecutive exponents b<\/em> are one greater that then previous:<\/p>\n

a = p1^b1 * p2^b2 * ... * pn^bn while p1 < p2 < ... < pn and (b1, b2, ..., bn) > 0<\/pre>\n
For example:<\/p>\n
    \n
  1. \n
    a = 91 = p1 ^ b1 * p2 ^ b2 = 7 ^ 1 * 13 ^ 1 = 7 * 13\r\nTherefore, P1 = 7 and P2 = 13<\/pre>\n<\/li>\n
  2. \n
    a = 3600 = p1 ^ b1 * p2 ^ b2 * p3 ^ b3 = 2^4 * 3^2 * 5^2\r\nTherefore, P1 = 2, P2 = 3, and P3 = 5<\/pre>\n<\/li>\n<\/ol>\n
    Greatest Common Divisor (GCD)<\/strong><\/p>\n
    The greatest common divisor (gcd) is a number in which you can divide two positive numbers a<\/em> and b<\/em> and at the same time is common in a<\/em> and b<\/em>.<\/p>\n
    Formally Speaking:<\/p>\n
    “The greatest common divisor … of two positive integers\u00a0\"a\" and\u00a0\"b\" is the largest divisor<\/a> common to\u00a0\"a\" and\u00a0\"b\". ” <http:\/\/mathworld.wolfram.com\/GreatestCommonDivisor.html<\/a>><\/p>\n
    There are different ways to obtain the greatest common divisor such as using prime factorizations, Euclid’s algorithm, and others <http:\/\/en.wikipedia.org\/wiki\/Greatest_common_divisor<\/a>>.<\/p>\n
    Approach 1:<\/span><\/p>\n
    A way to determine the greatest common divisor of two integers a<\/em> and b<\/em> is by
    \ncomparing the prime factorization of a<\/em> and b<\/em> and using their least powers.<\/p>\n
    Lets assume we wish to obtain the greatest common divisor of 12 and 30, gcd(12, 30).<\/p>\n
    For 300, we obtain the following prime numbers:<\/p>\n
    30 = 2^1 * 3^1 * 5^1<\/pre>\n
    For 12, we obtain the following prime numbers:<\/p>\n
    12 = 2^1 * 3^1 = 2^1 * 3^1 * 5^0<\/pre>\n
    In both cases, we have that 2 and 3 are the prime numbers used in a<\/em> and b<\/em>.
    \nAlso, we have that 2^1 and 3^1 are their least powers. Therefore,<\/p>\n
    gcd(12, 30) = 2^1 * 3^1 = 6<\/pre>\n
    Approach 2:<\/span><\/p>\n
    The follow is a more friendly approach to obtain the greates common divisor.
    \nLets assume we wish to know the greatest common denominator of 7 and 160, gcd(7, 160)<\/p>\n
      \n
    1. Write down this formula:
      \n (Dividend) = (Divisor) * (Quotient) + (Remainder)<\/em><\/li>\n
    2. The greatest number will be the dividend:
      \nDividend = 160
      \n (160<\/span>) = (Divisor) * (Quotient) + (Remainder)<\/em><\/li>\n
    3. The other number will be the divisor:
      \nDivisor = 7
      \n (160<\/span>) = (7<\/span>) * (Quotient) + (Remainder)<\/em><\/li>\n
    4. Multiply the divisor with a quotient that would get you a number as close as possible to the dividend
      \nIf 160\/7 = 22.8571429 then use 22 for the quotient
      \n (160<\/span>) = (7<\/span>) * (22<\/span>) + (Remainder)<\/em><\/li>\n
    5. The remainder will be the number that you need to reach 160. Since 7 * 22 is 154 the remainder is 6
      \n(160<\/span>) = (7<\/span>) * (22<\/span>) + (6<\/span>)<\/em><\/li>\n
    6. Now the Divisor became the new dividend and the remainder became the new divisor:
      \nNew dividend = 7 (previous divisor)
      \nNew divisor = 6 (previous remainder)
      \n (7<\/span>) = (6<\/span>) * (Quotient) + (Remainder)<\/em><\/li>\n
    7. Repeat the process, get a quotient that would multiply the divisor (6) as close as possible to the dividend (7)
      \n(7<\/span>) = (6<\/span>) * (1<\/span>) + (Remainder)<\/em><\/li>\n
    8. The remainder would be 1. This remainder is the greatest common divisor between 7 and 160
      \n gcd(7, 160) = 1<\/span><\/em><\/li>\n<\/ol>\n
      Y<\/em>ou can find a gcd calculator here:<\/span>
      \n<      http:\/\/britton.disted.camosun.bc.ca\/gcdlcm\/jbgcdlcm.htm<\/a>><\/p>\n
       Fermat’s Theorem<\/strong><\/p>\n
      Before going over the Fermat’s theorem, let review an old concept related with this topic, modular arithmetic.<\/p>\n
      Modular arithmetic (also known as clock arithmetic), is a system in which numbers “wrap around” after reaching a certain value. Of this system, we use the congruence relation on integer known as modulus.<\/p>\n
      Formally speaking:
      \n“For a positive integer n<\/em>, two integers a<\/em> and b<\/em> are said to be congruent modulo n<\/em>, (a = b mod n<\/em>),
      \nif their difference a \u2212 b<\/em> is an integer multiple of n<\/em>. The number n is called the modulus of the congruence” <      http:\/\/en.wikipedia.org\/wiki\/Modular_arithmetic#Congruence_relation<\/a>><\/p>\n
      For Example:<\/p>\n
        \n
      1. \n
        Lets assume we have a = 100, b = 86, and n = 7 such that 100 = 86 (mod 7).<\/pre>\n<\/li>\n
      2. \n
        100 - 86 = 14 in which 14 has 7 as a divisor.<\/pre>\n<\/li>\n
      3. \n
        If we divide 100 by 7,\r\nwe find out that the quwootient is 14 and remainder is 2.<\/pre>\n<\/li>\n
      4. \n
        Just coincidence, if we have 100 = 2 (mod 7),\r\nwe also find out that the remainder (b) is two too.<\/pre>\n<\/li>\n<\/ol>\n
        Another way to see the previous example is as follows:<\/p>\n
        100 = 86 (mod 7)\r\n\r\nMeans that 100 and 86 leave the same remainder when you divide by\r\n7; or, equivalently, that their difference is a multiple of 7.\r\n\r\nHere is a link in which you can find the quotient and remainder of a division:\r\n<http:\/\/www.analyzemath.com\/Calculators_3\/quotient_remainder.html<\/a>><\/pre>\n
        Another example:<\/p>\n
          \n
        1. \n
          For a = 0 mod 5, If a = 0 mod 5 then a^4 = 0^4 = 0 mod 5<\/pre>\n<\/li>\n
        2. \n
          For a = 1 mod 5, if a = 1 mod 5 then a^4 = 1^4 = 1 mod 5<\/pre>\n<\/li>\n
        3. \n
          For a = 2 mod 5, if a = 2 mod 5 then a^4 = 2^4 = 16 = 1 mod 5<\/pre>\n<\/li>\n
        4. \n
          For a = 3 mod 5, if a = 3 mod 5 then a^4 = 3^4 = 81 = 1 mod 5<\/pre>\n<\/li>\n
        5. \n
          For a = 4 mod 5, if a = 4 mod 5 then a^4 = 4^4 = 256 = 1 mod 5<\/pre>\n<\/li>\n<\/ol>\n
          Now that we have an idea about modulus, we can begin talking about Fermat’s Theorem.<\/p>\n
          Fermat’s theorem also known as “Fermat’s little theorem” (do not confuse with “Fermat’s last theorem”), establish that:<\/p>\n
            \n
          1.  If p<\/em> is a prime number and for any integer a<\/em> lower than the prime number p, a<p<\/em> is a positive integer not divisible by the prime number p.
            \n\"\"<\/a>
            \n<\/em><\/li>\n
          2. Or, <\/em>if p<\/em> is a prime number then for any integer a<\/em>, a^p<\/em> – a<\/em> will be evenly divisible by p<\/em>.
            \n\"a^p<\/li>\n
          3. Or, if p<\/em> is a prime and a<\/em> is an integer relatively prime to p<\/em>, then [a^(p\u22121)] \u2212 1<\/em> will be evenly divisible by p<\/em>.
            \n\"a^{p-1}<\/li>\n<\/ol>\n
            (<http:\/\/en.wikipedia.org\/wiki\/Fermat’s_little_theorem<\/a>>)<\/p>\n
            For example:<\/p>\n
              \n
            1. \n
              Lets assume p = 3 and a = 2Fermat's little theorem establish that<\/pre>\n<\/li>\n
            2. \n
              \"\"<\/a><\/em><\/pre>\n<\/li>\n
            3. \n
              Then a^(p-1) = 2^(3 - 1) = 2^2 = 4<\/pre>\n<\/li>\n
            4. \n
              So, 1 = a^(p-1) mod p = 4 mod 3 = 1<\/pre>\n<\/li>\n<\/ol>\n
              In network security, Fermat’s little theorem is used in public key and primality testing.<\/p>\n
              Euler Totient Function \u00f8(n)<\/em><\/strong><\/p>\n
              The Euler Totient function is represented by \u00f8<\/em>(n<\/em>) or \u03c6(n<\/em>) depending the author.<\/p>\n
              The Euler Totient function establish that:<\/p>\n
                \n
              1. \u00f8<\/em>(n<\/em>) is the number of possitive integers less than n<\/em> and coprime (also known as relatively prime) to n<\/em><\/li>\n
              2. Or the number of positive integers less or equal to n<\/em> that are relatively prime to n<\/em>, where 1 is counted as being coprime (relatively prime) to all numbers.<\/li>\n
              3. Or, \u00f8<\/em>(n<\/em>) returns the number of integers less than n<\/em> (including 1) that are relatively prime to n<\/em>.<\/li>\n<\/ol>\n
                Note: we say that two integers a<\/em> and b<\/em> are relatively prime if a<\/em> and b<\/em> have no common positive factor other than 1 or, if their greatest common divisor is 1. a<\/em> is relatively prime to b<\/em> if gcd(a<\/em>, b<\/em>) = 1.<\/p>\n
                A list of Euler’s Totient Function Values For n = 1 to 500, with divisor lists can be found in the following URL address: <http:\/\/primefan.tripod.com\/Phi500.html<\/a>><\/p>\n
                For example:<\/p>\n
                  \n
                1. Lets n = 37 so \u00f8<\/em>(n<\/em>) = \u00f8<\/em>(37<\/em>) = 35. 37 can be divided by 1 and by 37.
                  \nTherefore, all integers from 1 to 36 are relatively prime to 37<\/li>\n
                2. Lets n = 35 so \u00f8<\/em>(n<\/em>) = \u00f8<\/em>(35<\/em>) = 24. 35 can be divided by 1, 5, 7, and 35.
                  \nTherefore, integers 1, 2, 1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26,
                  \n27, 29, 31, 32, 33, 34 are relatively prime to 35.<\/li>\n<\/ol>\n
                  You may ask, I did you found these values (such as \u00f8<\/em>(35<\/em>) = 24)?<\/p>\n
                  To find these values:<\/p>\n
                    \n
                  1. (Case 1) For n<\/em> = p<\/em> (a prime), we have that \u00f8<\/em>(p<\/em>) = p<\/em> – 1.
                    \nFor Example: Lets p<\/em> = 7 so \u00f8<\/em> <\/em>(p<\/em>) = \u00f8<\/em>(7<\/em>), then \u00f8<\/em> <\/em>(7<\/em><\/em>) = 7<\/em> – 1 = 6.
                    \nTherefore \u00f8<\/em>(7<\/em><\/em>) = 6<\/li>\n
                  2. (Case 2) When n<\/em> = p^a<\/em> (power of a prime).
                    \nThe numbers with common factor with n are: p, 2p, 3p, . . . ,p^(a-1) * p<\/em>
                    \nsince there are p^(a-1)<\/em> of them.
                    \nFor example: Lets assume we have a prime number p<\/em> = 5 and a<\/em> is 2:
                    \n<\/em>\u00f8<\/em>(p^a<\/em>) = p^a – p^(a-1)<\/em> = (p<\/em>^(a<\/em>-1)) * (p<\/em> – 1) = (p^a<\/em>) * (1 – 1\/p<\/em>)
                    \n<\/em>\u00f8<\/em>(5^2) = 5^2 – 5^(2 -1) = (5^(2 – 1)) * (5 – 1) = (5^2) * (1 – 1\/5)
                    \n<\/em>\u00f8<\/em>(25) = 5^2 – 5 = 5 * (5 – 1) = (5^2) * (1 – 1\/5) = 20
                    \n\u00f8<\/em>(25) = 20 and all integers relative prime to 25 are
                    \n1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24.<\/li>\n<\/ol>\n
                    As a general case for the Euler’t Totient function \u00f8<\/em>(n<\/em>), we have that:<\/p>\n
                      \n
                    1. Let p<\/em> be a prime integer dividing n<\/em> integer so the integers divisible by p<\/em> are:
                      \np, 2p, 3p, 4p, . . . , (n\/p)(p)<\/em> where there are n\/p<\/em> number of integers.<\/li>\n
                    2. Then, the number of integers not divisible by p<\/em> are: n – n\/p = n * (1 – 1\/p)<\/em><\/li>\n
                    3. Let q<\/em> be another prime number dividing n<\/em>.
                      \nIf we wish to find the number of integers divisible by neither p<\/em> or q<\/em>,
                      \nthen deduct the n\/q<\/em> multiples of q<\/em> such that q, 2q, 3q, . . . , (n\/q)(q)<\/em><\/li>\n
                    4. In case some elements of p<\/em> and q<\/em> are common, the n\/pq<\/em> multiples of pq<\/em> are:
                      \npq, 2pq, 3pq, . . . , (n\/pq)(pq)<\/em> so n\/q – n\/pq = (n\/q)(1- 1\/p)<\/em><\/li>\n
                    5. Therefore the total of integers not divisible by p<\/em> or q<\/em> is:
                      \nn(1 – 1\/p) – (n\/q)(1 – 1\/p) = n(1 – 1\/p)(1 – 1\/q)<\/em><\/li>\n<\/ol>\n
                      General formula for Euler’s Totient Function \u00f8<\/em><\/span>(n<\/em>)<\/span>:
                      \n<\/span>
                      \n\u00f8<\/em>(n<\/em>) = n * (1 – 1\/p1) * (1 – 1\/p2) * . . .\u00a0 * (1 – 1\/pm)<\/em>, where p1, p2, . . . , pm<\/em> are prime factors of n<\/em> and m<\/em> is the total number of prime numbers.<\/p>\n
                      Example:<\/p>\n
                      Lets n<\/em> = 60, p1<\/em> = 2, p2<\/em> = 4,\u00a0 p3<\/em> = 5 and \u00f8<\/em>(n<\/em>)\u00a0 = n * (1 – 1\/p1) * (1 – 1\/p2) * <\/em>(1 – 1\/p3) then<\/em>
                      \n<\/em><\/p>\n
                      \u00f8<\/em>( <\/em>60) = 60 * (1 – 1\/2) * (1 – 1\/3) * (1 – 1\/5)
                      \n\u00f8<\/em>(60) = (60 – 60\/2) * (1 – 1\/3) * (1 – 1\/5)
                      \n\u00f8<\/em>(60) = (60 – 30) * (1 – 1\/3) * (1 – 1\/5)
                      \n\u00f8<\/em>(60) = (30) * (1 – 1\/3) * (1 – 1\/5)
                      \n\u00f8<\/em>(60) = (30 – 30\/3) * (1 – 1\/5)
                      \n\u00f8<\/em>(60) = (30 – 10) * (1 – 1\/5)
                      \n\u00f8<\/em>(60) = (20) * (1 – 1\/5)
                      \n\u00f8<\/em>(60) = (20 – 20\/5)
                      \n\u00f8<\/em>(60) = (20 – 4)
                      \n\u00f8<\/em>(60) = 16<\/p>\n
                      All integers relative prime to 16 are:
                      \n1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59<\/p>\n
                      Euler’s Totient Function \u00f8<\/em><\/span>(n<\/em>)<\/span> using two Prime Numbers:<\/span><\/p>\n
                      Let have two prime number p<\/em> and q<\/em> such that p \u2260 q<\/em> so \u00f8(pq) = \u00f8(p)*\u00f8(q) = (p-1)*(q-1) <\/em>in which<\/p>\n
                        \n
                      1. The set {1, 2, …, pq<\/em> -1} of integers is less than pq<\/em><\/li>\n
                      2. The integers in the set {1, 2, …, pq<\/em> – 1} are not relatively prime to pq<\/em>:
                        \n{p<\/em>, 2p<\/em>, …, (q<\/em> – 1)p<\/em>} and {q<\/em>, 2q<\/em>, …, (p<\/em> – 1)q<\/em>}<\/li>\n
                      3. \u00f8(pq) = (pq – 1) \u2013 [(q-1) + (p-1)]
                        \n\u00f8(pq) = pq \u2013 p \u2013 q +1
                        \n\u00f8(pq) = (p-1) * (q-1)
                        \n\u00f8(pq) = \u00f8(p)*\u00f8(q)
                        \n<\/em><\/li>\n<\/ol>\n
                        For example:<\/p>\n
                        \u00f8(n)<\/em> = <\/em>\u00f8(pq) <\/em>= (p-1) * (q-1)<\/em> <\/em>
                        \n\u00f8(21) = <\/em>\u00f8(3 * 7) <\/em>
                        \n<\/em>\u00f8(21) <\/em>= <\/em>(3 – 1) * (7 – 1)
                        \n<\/em>\u00f8(21) <\/em>= 2 * 6
                        \n<\/em>\u00f8(21) <\/em>= 12<\/em><\/p>\n
                        (<http:\/\/home.earthlink.net\/~usondermann\/eulertot.html<\/a>>)<\/p>\n
                        Euler’s Theorem<\/strong><\/p>\n
                        Euler’s Theorem (also known as Fermat-Euler theorem) establish that for every positive integer a<\/em> relatively prime to n<\/em> then \"\"<\/a><\/p>\n
                        For example:<\/p>\n
                          \n
                        1. Lets a = 3 and n = 10 then 
                          \n<\/em>\u00f8(n)<\/em> = <\/em>\u00f8(pq) <\/em>= (p-1) * (q-1)<\/em>
                          \n\u00f8(10)<\/em> = \u00f8(2*5) = (2 – 1) * (5 -1) = (1) * (4<\/em>) = 4
                          \na<\/em>^\u00f8(n) mod n = 1<\/em>
                          \n<\/em>3<\/em>^\u00f8(10) mod 10 = 1
                          \n<\/em>3<\/em>^4 mod 10 = 1<\/em>
                          \n81<\/em> mod 10 = 1<\/em><\/li>\n
                        2. Lets a = 2 and n = 11 then 
                          \n<\/em>\u00f8(n)<\/em> = <\/em>\u00f8(p – 1) <\/em>
                          \n\u00f8(11)<\/em> = \u00f8(11 – 1) = 10<\/em>
                          \na<\/em>^\u00f8(n) mod n = 1<\/em>
                          \n2<\/em>^\u00f8(11) mod 11 = 1
                          \n<\/em>2^10 mod 11 = 1<\/em>
                          \n1024 mod 11 = 1<\/em><\/li>\n<\/ol>\n
                          Primality Testing<\/strong><\/p>\n
                            \n
                          1. Very large prime numbers selected at random are necessary for most of cryptographic algorithms.<\/li>\n
                          2. Na\u00efve Algorithm: The objective of this algorithm is to divide a number a<\/em> by all the numbers in turn that are less than the square root of a<\/em>. This kind of algorithm works for small numbers, but it inefficient for large numbers.<\/li>\n<\/ol>\n
                            Miller Rabin Algorithm<\/strong><\/p>\n
                            Miller Rabin algorithm (also known as Miller-Rabin Primality Test) is an algorithm that return a true or false value depending a given value n. <\/em>Normally, If it outputs true, then n<\/em> is “probably prime”, else then n<\/em> is definitely composite.<\/p>\n
                            Approach 1:<\/span><\/p>\n
                            [Split Off Power of]: Lets n<\/em> > 3 and n be odd, k<\/em> > 0, and\u00a0 q<\/em> odd so \"\"<\/a><\/p>\n
                              \n
                            1. [Random Base] Choose a random integer a<\/em> with 1 < a<\/em> < n.<\/em><\/li>\n
                            2. [Odd Power] Set b = a^n (mod m) so if b = \u00b11 (mod n) then output true and terminate.<\/li>\n
                            3. [Even Powers] For any r with 1 <= r <= k – 1, if b^2^r = -1 (mod n) then output true and terminate else output false<\/li>\n<\/ol>\n
                              (< http:\/\/modular.math.washington.edu\/edu\/2007\/spring\/ent\/ent-html\/node26.html<\/a>>)
                              \n<\/a><\/span><\/p>\n
                              Approach 2:<\/span><\/p>\n
                                \n
                              1. Lets n<\/em> > 3 and n be odd, k<\/em> > 0, and\u00a0 q<\/em> odd so \"\"<\/a>.
                                \nDivide (n – 1)<\/em> by 2 until the result is an odd number.<\/li>\n
                              2. Let a be an integer 1 < a < n where n > 2 so <\/a>\"\"<\/a>
                                \nCheck which of the following two conditions is true:
                                \n(a) (                                \"\"<\/a> ) == true ?
                                \n(b) There exist 1 <= j <= k such that                                 \"\"<\/a> == true ?<\/li>\n
                              3. If any of the previous conditions (a and b) are true, then n may not be a prime number.<\/li>\n<\/ol>\n
                                Example:<\/p>\n
                                  \n
                                1. Lets n = 2047 such that 2047 = 23 * 89.<\/li>\n
                                2. If \"\"<\/a> so n – 1 = 2^1 * 1023 then<\/li>\n
                                3. 2^1023 mod 2047 = 1<\/li>\n
                                4. However, 2047 is not a prime<\/li>\n<\/ol>\n
                                  Approach 3:<\/span> (Similar to approach 1)<\/p>\n
                                    \n
                                  1. Check if n integer value is prime or not<\/li>\n
                                  2. If n is prime then find integers k > 0, q being odd, such that \"\"<\/a> is true.<\/li>\n
                                  3. if \"\"<\/a> is true then output is true (n maybe prime) else<\/li>\n
                                  4. Check for every value of j going from 1 to k if \"\"<\/a> is true.
                                    \nIf true then output true (n maybe prime) else<\/li>\n
                                  5. return false (n is not prime)<\/li>\n<\/ol>\n
                                    Probabilistic Consideration<\/span><\/p>\n
                                    For an odd no prime number n<\/em> and a randomly chosen integer a<\/em> where 1 < a<\/em> < n<\/em> -1,
                                    \nwe can expect a probability of failure in detecting\u00a0 that n is not a prime number of less than one quarter of the probabiblities.<\/p>\n
                                    If we repeat the Millan Rabin algorithm with different values of a<\/em>, there is a chance that we find a “maybe” prime number n<\/em> after trying a t<\/em> number of tests:<\/p>\n
                                    Probabilities of finding a “maybe” prime number n<\/em> after t<\/em> test are:
                                    \nPr(n<\/em> maybe a prime number after t<\/em> tests) = (1\/4)^t<\/em><\/p>\n
                                    For example:
                                    \nLets assume we wish perform t<\/em> = 10 tests using different values of a<\/em>, we have less than 10^-6 probabilities to find an n<\/em> that maybe a prime number.<\/p>\n
                                    Extra Examples
                                    \n<\/strong><\/p>\n
                                    Lets have a = b mod p such that we wish to know a, b = 5^6 and p is 23 so a = 5^6 mod 23<\/p>\n
                                    How can we solve this? Using Modulus Arithmetic. One of the properties say that C^(ab) mod p = (C^a mod p)^b mod p<\/p>\n
                                    So,<\/p>\n
                                    5^6 mod 23 => 5^(2*3) mod 23 => (5^2 mod 23)^3 mod 23 => (25 mod 23)^3 mod 23<\/p>\n
                                    The remaider of 25 mod 23 is 2 (23 = 0, 24 = 1, 25 = 2) or you could divide 25 by 23: 23 * 1 = 23 => 25 – 23\u00a0 = 2 remainer<\/p>\n
                                    (25 mod 23)^3 mod 23 => (2)^3 mod 23 => 8 mod 23 = 8 (is less than 23 so is inside the modulus)<\/p>\n\n