3 Replies - 1975 Views - Last Post: 22 December 2011 - 12:37 PM

#1 Karel-Lodewijk   User is offline

  • D.I.C Addict
  • member icon

Reputation: 454
  • View blog
  • Posts: 864
  • Joined: 17-March 11

Probablistic primality test (Miller-Rabin)

Posted 14 December 2011 - 05:05 AM

Description: This is an implementation of the Miller-Rabin probabilistic primality test (http://en.wikipedia.org/wiki/Miller-Rabin_primality_test). If the algorithm says a number is not prime, then it is definitely not prime. If the algorithm however says a number is prime, then it is prime with probability 1-(0.25^k). With K=20 as declared on top, this probability is 99.99999999990905%. Probablistic primality tests are used to find very large primes such as primes that are used in public key asymmetric cryptography. This is a straight translation of the pseudo code on wikipedia.
K = 20

def is_probably_prime?(n)
    #fast calculation of base^exponent % modulus
    def modular_pow(base, exponent, modulus)
        result = 1
        while exponent > 0 do
            if (exponent & 1) == 1 then
               result = (result * base) % modulus
            end
            exponent = exponent >> 1
            base = (base * base) % modulus
        end
        return result
    end

    if n < 5 then
        if n == 2 || n == 3 then
            return true
        else
            return false
        end
    end

    #writing n-1 as 2^s * d (d odd)
    s = 0
    d = n - 1
    while (d%2 == 0) do
        d=d/2
        s=s+1
    end

    K.times do
        a = Random.rand(n-4) + 2 #random number on (2,n-2)
        x = modular_pow(a,d,n)
        if (x==1 || x==n-1) then 
            next
        end
        for r in 1 .. s-1 do
            x = modular_pow(x,2,n)
            if x == 1 then
                return false
            end
            if x == n-1 then
                stop = true
                break;
            end
        end
        if (stop) then
            next;
        end
        return false
    end
    return true;
end


Is This A Good Question/Topic? 0
  • +

Replies To: Probablistic primality test (Miller-Rabin)

#2 Karel-Lodewijk   User is offline

  • D.I.C Addict
  • member icon

Reputation: 454
  • View blog
  • Posts: 864
  • Joined: 17-March 11

Re: Probablistic primality test (Miller-Rabin)

Posted 22 December 2011 - 12:10 PM

Note that there is also a probabilistic version of this algorithm. Instead of random bases a as in this snippet, use 2, 3, 5, 7, 11, 13, and 17. It is proven that for these bases the test works for all numbers n < 341,550,071,728,321, resulting in a very fast deterministic test in the [0 341,550,071,728,321) range.
Was This Post Helpful? 0
  • +
  • -

#3 Karel-Lodewijk   User is offline

  • D.I.C Addict
  • member icon

Reputation: 454
  • View blog
  • Posts: 864
  • Joined: 17-March 11

Re: Probablistic primality test (Miller-Rabin)

Posted 22 December 2011 - 12:11 PM

I meant to say deterministic version in the last comment of course.
Was This Post Helpful? 0
  • +
  • -

#4 Karel-Lodewijk   User is offline

  • D.I.C Addict
  • member icon

Reputation: 454
  • View blog
  • Posts: 864
  • Joined: 17-March 11

Re: Probablistic primality test (Miller-Rabin)

Posted 22 December 2011 - 12:37 PM

It can also be used as a true deterministic primality test if you check for all bases a in the range [2, min(n-1, (2*log(n))**2).floor]. This result does depend on the yet unproven generalized Riemann hypothesis, wikipedia has the details.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1