Det jeg har hittil er følgende:
Dersom $n, m$ er relativt primiske, bruk Euclids utvidede algoritme. Akkurat denne delen er så rask som jeg kan få den, $O(\log m)$, og løser $(n, m) = (999999999999999, 1000000000000000)$ på bare noen millisekunder.
Problemet mitt er når $n, m$ ikke er relativt primiske. Der har jeg kun en løsning på $O(m)$, som for de fleste tilfeller er greit, men ikke greit nok. Har en mistanke om at det skal finnes en $O(\log m)$-algoritme for dette tilfellet også, men ikke som jeg kan se.
Her er det jeg har hittil.
Kode: Velg alt
def modInverse(n, m):
if n == 0: return -1
if isCoPrime(n, m): # O(log m) with Extended Euclid's Algorithm
m0 = m
y = 0
x = 1
if (m == 1): return 0
while n > 1:
quotient = n // m
temp = m
m = n % m
n = temp
temp = y
y = x - quotient * y
x = temp
if (x < 0): x = x + m0
return x
for i in range(0, m): # O(m)
value = n * i % m
if value == 1:
return i
return -1
def isCoPrime(n, m):
return gcd(n, m) == 1
def gcd(n, m):
while n != 0 and m != 0:
if n > m:
n %= m
else:
m %= n
return max(n, m)
