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