PROGRAM Test_de_Miller_Rabin;
USES crt, Math;
//VAR n, cont:integer;
VAR cont:integer;
VAR ans:boolean;
FUNCTION millerRabin(n, iter:integer):boolean;
VAR k, q, i, a, y, j:integer;
Begin
k := 0;
q := n - 1;
a := 0;
y := 0;
j := 1;
while((q mod 2) = 0)do
begin
q := q DIV 2;
k := k + 1;
end;
Randomize;
for i := 0 to iter do
begin
a := random(n - 2) + 2;
y := round((power(a, q))) mod n;
if((not(y = 1)) and (not(y = (n - 1))))then
begin
j := 1;
while((j <= k) and (not(y = (n - 1))))do
begin
y := round((power(y, 2))) mod n;
if(y = 1)then
begin
millerRabin := false;
Exit;
end;
j := j + 1;
end;
if(not(y = (n - 1)))then
begin
millerRabin := false;
Exit;
end;
end;
end;
millerRabin := true;
End;
BEGIN
clrscr; //Limpiar pantalla
(*write('Ingrese un numero impar: ');
Readln(n); //Leer tecla
while((n <= 2) or ((n mod 2) = 0))do
begin
write('Numero no valido, por favor ingrese un numero impar: ');
Readln(n); //Leer tecla
end;
ans := millerRabin(n, 100);
write(n);
if(ans = true)then
writeln(' tal vez es primo')
else
writeln(' no es primo');*)
for cont := 2 to 18 do
begin
if(not((cont mod 2) = 0))then
begin
ans := millerRabin(cont, 100);
write(cont);
if(ans = true)then
writeln(' tal vez es primo')
else
writeln(' no es primo');
end;
end;
writeln();
write('Oprima una tecla para salir');
readkey; //Leer tecla
END.
UFJPR1JBTSBUZXN0X2RlX01pbGxlcl9SYWJpbjsKClVTRVMgY3J0LCBNYXRoOwovL1ZBUiBuLCBjb250OmludGVnZXI7ClZBUiBjb250OmludGVnZXI7ClZBUiBhbnM6Ym9vbGVhbjsKCkZVTkNUSU9OIG1pbGxlclJhYmluKG4sIGl0ZXI6aW50ZWdlcik6Ym9vbGVhbjsKICAgIFZBUiBrLCBxLCBpLCBhLCB5LCBqOmludGVnZXI7CiAgICBCZWdpbgogICAgICAgIGsgOj0gMDsKICAgICAgICBxIDo9IG4gLSAxOwogICAgICAgIGEgOj0gMDsKICAgICAgICB5IDo9IDA7CiAgICAgICAgaiA6PSAxOwogICAgICAgIHdoaWxlKChxIG1vZCAyKSA9IDApZG8KICAgICAgICAgICAgYmVnaW4KICAgICAgICAgICAgICAgIHEgOj0gcSBESVYgMjsKICAgICAgICAgICAgICAgIGsgOj0gayArIDE7CiAgICAgICAgICAgIGVuZDsKCiAgICAgICAgUmFuZG9taXplOwogICAgICAgIGZvciBpIDo9IDAgdG8gaXRlciBkbwogICAgICAgICAgICBiZWdpbgogICAgICAgICAgICAgICAgYSA6PSByYW5kb20obiAtIDIpICsgMjsKICAgICAgICAgICAgICAgIHkgOj0gcm91bmQoKHBvd2VyKGEsIHEpKSkgbW9kIG47CiAgICAgICAgICAgICAgICBpZigobm90KHkgID0gMSkpIGFuZCAobm90KHkgPSAobiAtIDEpKSkpdGhlbgogICAgICAgICAgICAgICAgICAgIGJlZ2luCiAgICAgICAgICAgICAgICAgICAgICAgIGogOj0gMTsKICAgICAgICAgICAgICAgICAgICAgICAgd2hpbGUoKGogPD0gaykgYW5kIChub3QoeSA9IChuIC0gMSkpKSlkbwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYmVnaW4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB5IDo9IHJvdW5kKChwb3dlcih5LCAyKSkpIG1vZCBuOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmKHkgPSAxKXRoZW4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYmVnaW4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbGxlclJhYmluIDo9IGZhbHNlOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRXhpdDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZW5kOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGogOj0gaiArIDE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBlbmQ7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmKG5vdCh5ID0gKG4gLSAxKSkpdGhlbgogICAgICAgICAgICAgICAgICAgICAgICAgICAgYmVnaW4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtaWxsZXJSYWJpbiA6PSBmYWxzZTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBFeGl0OwogICAgICAgICAgICAgICAgICAgICAgICAgICAgZW5kOwogICAgICAgICAgICAgICAgICAgIGVuZDsKICAgICAgICAgICAgZW5kOwogICAgICAgIG1pbGxlclJhYmluIDo9IHRydWU7CiAgICBFbmQ7CgoJCkJFR0lOCgoJY2xyc2NyOyAvL0xpbXBpYXIgcGFudGFsbGEKCiAgICAoKndyaXRlKCdJbmdyZXNlIHVuIG51bWVybyBpbXBhcjogJyk7CglSZWFkbG4obik7IC8vTGVlciB0ZWNsYQogICAgd2hpbGUoKG4gPD0gMikgb3IgKChuIG1vZCAyKSA9IDApKWRvCiAgICAgICAgYmVnaW4KICAgICAgICAgICAgd3JpdGUoJ051bWVybyBubyB2YWxpZG8sIHBvciBmYXZvciBpbmdyZXNlIHVuIG51bWVybyBpbXBhcjogJyk7CiAgICAgICAgICAgIFJlYWRsbihuKTsgLy9MZWVyIHRlY2xhCiAgICAgICAgZW5kOwoKICAgIGFucyA6PSBtaWxsZXJSYWJpbihuLCAxMDApOwoKICAgIHdyaXRlKG4pOwogICAgaWYoYW5zID0gdHJ1ZSl0aGVuCiAgICAgICAgd3JpdGVsbignIHRhbCB2ZXogZXMgcHJpbW8nKQogICAgZWxzZQogICAgICAgIHdyaXRlbG4oJyBubyBlcyBwcmltbycpOyopCgogICAgZm9yIGNvbnQgOj0gMiB0byAxOCBkbwogICAgICAgIGJlZ2luCiAgICAgICAgICAgIGlmKG5vdCgoY29udCBtb2QgMikgPSAwKSl0aGVuCiAgICAgICAgICAgICAgICBiZWdpbgogICAgICAgICAgICAgICAgICAgIGFucyA6PSBtaWxsZXJSYWJpbihjb250LCAxMDApOwogICAgICAgICAgICAgICAgICAgIHdyaXRlKGNvbnQpOwogICAgICAgICAgICAgICAgICAgIGlmKGFucyA9IHRydWUpdGhlbgogICAgICAgICAgICAgICAgICAgICAgICB3cml0ZWxuKCcgdGFsIHZleiBlcyBwcmltbycpCiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICB3cml0ZWxuKCcgbm8gZXMgcHJpbW8nKTsKICAgICAgICAgICAgICAgIGVuZDsKICAgICAgICBlbmQ7CgogICAgd3JpdGVsbigpOwogICAgd3JpdGUoJ09wcmltYSB1bmEgdGVjbGEgcGFyYSBzYWxpcicpOwoJcmVhZGtleTsgLy9MZWVyIHRlY2xhCkVORC4K