38 lines
779 B
Plaintext
38 lines
779 B
Plaintext
EnableExplicit
|
|
Declare main()
|
|
Declare.i mi(a.i, b.i)
|
|
|
|
If OpenConsole("MODULAR-INVERSE")
|
|
main() : Input() : End
|
|
EndIf
|
|
|
|
Macro ModularInverse(a, b)
|
|
PrintN(~"\tMODULAR-INVERSE(" + RSet(Str(a),5) + "," +
|
|
RSet(Str(b),5)+") = " +
|
|
RSet(Str(mi(a, b)),5))
|
|
EndMacro
|
|
|
|
Procedure main()
|
|
ModularInverse(42, 2017) ; = 1969
|
|
ModularInverse(40, 1) ; = 0
|
|
ModularInverse(52, -217) ; = 96
|
|
ModularInverse(-486, 217) ; = 121
|
|
ModularInverse(40, 2018) ; = -1
|
|
EndProcedure
|
|
|
|
Procedure.i mi(a.i, b.i)
|
|
Define x.i = 1,
|
|
y.i = Int(Abs(b)),
|
|
r.i = 0
|
|
If y = 1 : ProcedureReturn 0 : EndIf
|
|
While x < y
|
|
r = (a * x) % b
|
|
If r = 1 Or (y + r) = 1
|
|
Break
|
|
EndIf
|
|
x + 1
|
|
Wend
|
|
If x > y - 1 : x = -1 : EndIf
|
|
ProcedureReturn x
|
|
EndProcedure
|