Demo entry 4451880

Miller-Rabin

   

Submitted by anonymous on Apr 12, 2016 at 11:35
Language: Matlab. Code size: 616 Bytes.

function is_prime = miller_rabin(m)
% Find s and t
t = m-1;
s = 0;
while ~bitget(t,1)
    t = t/2;
    s = s+1;
end

b = randi([1,m-1]);

% compute y = b^t mod m by square and multiply algorithm
y = square_and_multiply(t,b,m);

if mod(1,m) == y; is_prime = 1; return; end

for i = 0:s-1
    if mod(-1,m) == y; is_prime = 1; return; end
    y = mod(y^2,m);
end
is_prime = 0;
end

function y = square_and_multiply(t,b,m)
% compute the square and multiply algorithm
t_bin = dec2bin(t);
y = 1;
for i = 1:length(t_bin)
    y = mod(y^2,m);
    if t_bin(i) == '1'; y = mod(y*b,m); end
end
end

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).