Miller–Rabin primality test: Difference between revisions
→{{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...
(→{{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:
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
INTEGER N,X,P !All presumed positive, and X < N.
INTEGER I !A stepper.
INTEGER*8 V,W !Broad scratchpads, otherwise N > 46340 may incur overflow in 32-bit.
V = 1 !=X**0
IF (P.GT.0) THEN !Something to do?
I = P !
IF (I.GT.0)
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.
PROGRAM POKEMR
| |||