matematikk.net

Oppgaven er som følger: Gitt heltall $n, m$, finn $x$ slik at $n \cdot x \equiv 1 \pmod m$. Dersom ingen invers eksisterer, returner $-1$.

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.
Noen som har gjort liknende før? Tallteoretisk programmering er ikke noe jeg har mye erfaring med som webutvikler, men siden det er intervju-aktuelle oppgaver tenkte jeg å bryne meg på det likevel.

Aleks855 wrote:Oppgaven er som følger: Gitt heltall $n, m$, finn $x$ slik at $n \cdot x \equiv 1 \pmod m$. Dersom ingen invers eksisterer, returner $-1$.

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.

Code: Select all

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)

Noen som har gjort liknende før? Tallteoretisk programmering er ikke noe jeg har mye erfaring med som webutvikler, men siden det er intervju-aktuelle oppgaver tenkte jeg å bryne meg på det likevel.

Du trenger nok ikke forandre veldig mye på programmet ditt om du bruker litt matematikk:

Anta at $p>1$ er et primtall og at $p|m,n$. Da kan vi skrive $m = pr$ og $n=ps$, hvor $r,s\in\mathbb{Z}$. Dersom det finnes en multiplikativ invers, altså det finnes $x\in\mathbb{Z}$ slik at $n \cdot x \equiv 1 \pmod m$, så må det finnes det finnes $x,y\in\mathbb{Z}$ slik at $nx + my = 1$. Men da får vi at $$1 = nx + my = prx + psy = p(rx + sy),$$ en selvmotsigelse, ettersom $rx + sy \in \mathbb{Z}$. Altså finnes det ingen multiplikativ invers i disse tilfellene, så når du kjører Euklis algoritme trenger du bare å breake og returnere $-1$ dersom det viser seg at $\text{hcf}(m,n) \neq 1$.

Ah! Perfekt utfall. Trenger bare å fjerne hele $O(m)$-delen.

Perfekt forklaring også. Takk!

Tenkte ikke over muligheten for at det ikke finnes en løsning dersom $n, m$ ikke er relativt primisk.