76 lines
1.8 KiB
Plaintext
76 lines
1.8 KiB
Plaintext
' version 10-07-2018
|
|
' compile with: fbc -s console
|
|
|
|
Type ext_euclid
|
|
Dim As Integer a, b
|
|
End Type
|
|
|
|
' "Table method" aka "The Magic Box"
|
|
Function magic_box(x As Integer, y As Integer) As ext_euclid
|
|
|
|
Dim As Integer a(1 To 128), b(1 To 128), d(1 To 128), k(1 To 128)
|
|
|
|
a(1) = 1 : b(1) = 0 : d(1) = x
|
|
a(2) = 0 : b(2) = 1 : d(2) = y : k(2) = x \ y
|
|
|
|
Dim As Integer i = 2
|
|
|
|
While Abs(d(i)) <> 1
|
|
i += 1
|
|
a(i) = a(i -2) - k(i -1) * a(i -1)
|
|
b(i) = b(i -2) - k(i -1) * b(i -1)
|
|
d(i) = d(i -2) Mod d(i -1)
|
|
k(i) = d(i -1) \ d(i)
|
|
'Print a(i),b(i),d(i),k(i)
|
|
If d(i -1) Mod d(i) = 0 Then Exit While
|
|
Wend
|
|
|
|
If d(i) = -1 Then ' -1 * (ab + by) = -1 * -1 ==> -ab -by = 1
|
|
a(i) = -a(i)
|
|
b(i) = -b(i)
|
|
End If
|
|
|
|
Function = Type( a(i), b(i) )
|
|
|
|
End Function
|
|
' ------=< MAIN >=------
|
|
|
|
Dim As Integer x, y, gcd
|
|
Dim As ext_euclid result
|
|
|
|
Do
|
|
Read x, y
|
|
If x = 0 AndAlso y = 0 Then Exit Do
|
|
result = magic_box(x, y)
|
|
With result
|
|
gcd = .a * x + .b * y
|
|
Print "a * "; Str(x); " + b * "; Str(y);
|
|
Print " = GCD("; Str(x); ", "; Str(y); ") ="; gcd
|
|
If gcd > 1 Then
|
|
Print "No solution, numbers are not coprime"
|
|
Else
|
|
Print "a = "; .a; ", b = ";.b
|
|
Print "The Modular inverse of "; x; " modulo "; y; " = ";
|
|
While .a < 0 : .a += IIf(y > 0, y, -y) : Wend
|
|
Print .a
|
|
'Print "The Modular inverse of "; y; " modulo "; x; " = ";
|
|
'While .b < 0 : .b += IIf(x > 0, x, -x) : Wend
|
|
'Print .b
|
|
End if
|
|
End With
|
|
Print
|
|
Loop
|
|
|
|
Data 42, 2017
|
|
Data 40, 1
|
|
Data 52, -217
|
|
Data -486, 217
|
|
Data 40, 2018
|
|
Data 0, 0
|
|
|
|
' empty keyboard buffer
|
|
While Inkey <> "" : Wend
|
|
Print : Print "hit any key to end program"
|
|
Sleep
|
|
End
|