Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(→{{header|Fortran}}: When generating X**P via repeated squarings of W, square W only if more power is needed. The resulting code loses DO WHILE and has a GO TO...) |
|||
| Line 1,382: | Line 1,382: | ||
INTEGER FUNCTION MODEXP(N,X,P) !Calculate X**P mod N without overflowing... |
INTEGER FUNCTION MODEXP(N,X,P) !Calculate X**P mod N without overflowing... |
||
C Relies on a.b mod n = (a mod n)(b mod n) mod n |
C Relies on a.b mod n = (a mod n)(b mod n) mod n |
||
INTEGER N,X,P !All presumed positive. |
INTEGER N,X,P !All presumed positive, and X < N. |
||
INTEGER I !A stepper. |
INTEGER I !A stepper. |
||
INTEGER*8 V,W !Broad scratchpads, otherwise N > 46340 may incur overflow in 32-bit. |
INTEGER*8 V,W !Broad scratchpads, otherwise N > 46340 may incur overflow in 32-bit. |
||
V = 1 !=X**0 |
V = 1 !=X**0 |
||
IF (P.GT.0) THEN !Something to do? |
|||
W = X !=X**1, X**2, X**4, X**8, ... except, all are mod N. |
|||
I = P ! |
I = P !Yes. Get a copy I can mess with. |
||
W = X !=X**1, X**2, X**4, X**8, ... except, all are mod N. |
|||
1 IF (MOD(I,2).EQ.1) V = MOD(V*W,N) !Incorporate W if the low-end calls for it. |
|||
I = I/2 !Used. Shift the next one down. |
|||
I |
IF (I.GT.0) THEN !Still something to do? |
||
W = MOD(W**2,N) !Yes. Square W ready for the next bit up. |
|||
GO TO 1 !Consider it. |
|||
END IF !Don't square W if nothing remains. It might overflow. |
|||
END IF !Negative powers are ignored. |
|||
MODEXP = V !Done, in lb(P) iterations! |
|||
END FUNCTION MODEXP !"Bit" presence by arithmetic: works for non-binary arithmetic too. |
END FUNCTION MODEXP !"Bit" presence by arithmetic: works for non-binary arithmetic too. |
||
END MODULE MRTEST !Just some trial versions. |
|||
PROGRAM POKEMR |
PROGRAM POKEMR |
||