Modulare multiplikative Inverse

22

Ihre Aufgabe ist es, zwei ganzzahlige Zahlen anzugeben aund bdie modulare multiplikative Inverse eines Modulo b zu berechnen, falls es existiert.

Das modulare Inverse von amodulo bist eine csolche Zahl ac ≡ 1 (mod b). Diese Zahl ist bfür jedes Paar von aund eindeutig modulo b. Es existiert nur, wenn der größte gemeinsame Teiler von aund bist 1.

Die Wikipedia-Seite für modulare multiplikative Inverse kann konsultiert werden, wenn Sie weitere Informationen zum Thema benötigen.

Ein- und Ausgang

Die Eingabe erfolgt entweder als zwei Ganzzahlen oder als Liste mit zwei Ganzzahlen. Ihr Programm sollte entweder eine einzelne Zahl, die modulare multiplikative Inverse, die sich im Intervall befindet 0 < c < b, oder einen Wert ausgeben, der angibt, dass es keine Inverse gibt. Der Wert kann ein beliebiger Wert sein, mit Ausnahme einer Zahl im Bereich (0,b), und es kann sich auch um eine Ausnahme handeln. Der Wert sollte jedoch für Fälle gleich sein, in denen es keine Inverse gibt.

0 < a < b kann angenommen werden

Regeln

  • Das Programm sollte irgendwann beendet sein und jeden Testfall in weniger als 60 Sekunden lösen
  • Es gelten Standardlücken

Testfälle

Testfälle unten sind im Format angegeben, a, b -> output

1, 2 -> 1
3, 6 -> Does not exist
7, 87 -> 25
25, 87 -> 7
2, 91 -> 46
13, 91 -> Does not exist
19, 1212393831 -> 701912218
31, 73714876143 -> 45180085378
3, 73714876143 -> Does not exist

Wertung

Dies ist Codegolf, daher gewinnt der kürzeste Code für jede Sprache.

Dies und das sind ähnliche Fragen, aber beide fragen nach bestimmten Situationen.

Halvard Hummel
quelle
6
Aus Fermats kleinem Theorem folgt, dass das multiplikative Inverse von a, falls es existiert, effizient als ^ (phi (b) -1) mod b berechnet werden kann, wobei phi die totiente Funktion von Euler ist: phi (p0 ^ k0 * p1 ^ k1 * ...) = (p0-1) * p0 ^ (k0-1) * (p1-1) * p1 ^ (k1-1) * ... Nicht zu sagen führt zu kürzerem Code :)
ngn
1
@Jenny_mathy Zusätzliche Eingaben sind generell nicht zulässig.
Mr. Xcoder
3
Ich zähle sechs Antworten, die brachial zu sein scheinen und wahrscheinlich nicht alle Testfälle in 60 Sekunden ausführen (einige geben zuerst einen Stapel- oder Speicherfehler aus).
Ørjan Johansen
1
@ngn: Sie haben Fermats Little Theorem (FLT) mit Eulers Verbesserung in Einklang gebracht. Fermat wusste nichts über die Euler-Phi-Funktion. Weiterhin gilt die Verbesserung von FLT und Euler nur, wenn gcd (a, b) = 1. Schließlich ist in der von Ihnen geschriebenen Form "a ^ (\ phi (b) -1) mod b" kongruent zu 1, nicht zu a ^ (- 1). Um eine ^ (- 1) zu erhalten, verwenden Sie eine ^ (\ phi (b) -2) mod b.
Eric Towers
1
@EricTowers Euler ist eine Konsequenz. Bezüglich "gcd (a, b) = 1" habe ich gesagt, "ob es [das Inverse] gibt". Sind Sie sicher über Phi (b) -2?
ngn

Antworten:

11

Mathematica, 14 Bytes

Obligatorische Mathematica eingebaut :

ModularInverse

Es ist eine Funktion, die zwei Argumente ( aund b) akzeptiert und die Umkehrung eines Mods b zurückgibt, falls es existiert. Wenn nicht, wird der Fehler zurückgegeben ModularInverse: a is not invertible modulo b..

Tutleman
quelle
7

JavaScript (ES6), 79 73 62 61 Bytes

Gibt zurück, falsewenn das Inverse nicht existiert.

Es verwendet den erweiterten euklidischen Algorithmus und löst alle Testfälle fast augenblicklich.

f=(a,b,c=!(n=b),d=1)=>a?f(b%a,a,d,c-(b-b%a)/a*d):b<2&&(c+n)%n

Testfälle

Arnauld
quelle
Warum ist es nicht möglich, den Namen der Funktion f zu schreiben, wie in f (c, a, b = 0, d = 1, n = a) => c? F (a% c, c, d, b- ( aa% c) / c * d, n): a <2 && (b + n)% n?
RosLuP
@RosLup f(x,y)wird immer als Funktionsaufruf analysiert, außer wenn das functionSchlüsselwort explizit vorangestellt ist . Eine anonyme Pfeilfunktion hingegen wird als deklariert (x,y)=>somethingund f=(x,y)=>somethingweist der fVariablen die Funktion zu .
Arnauld
4

Gelee , 2 Bytes

æi

Probieren Sie es online!

Dies verwendet eine integrierte Funktion für die modulare Inversion und gibt 0 für keine modulare Inversion zurück.

Gelee , 7 Bytes

R×%⁸’¬T

Probieren Sie es online!

Gibt eine leere Menge (dargestellt als leere Zeichenfolge) ohne modulare Inverse aus. Läuft auf TIO nicht genügend Arbeitsspeicher für die größten Testfälle, sollte aber bei genügend Arbeitsspeicher funktionieren.

Wie es funktioniert

R×%⁸’¬T  
R        Generate range of b
 ×       Multiply each by a
  %⁸     Mod each by b
    ’    Decrement (Map 1 to 0 and all else to truthy)
     ¬   Logical NOT
      T  Get the index of the truthy element.

Wenn Sie für größere Testfälle arbeiten möchten, probieren Sie diese (relativ ungolfed) Version aus, die viel Zeit anstatt Speicher benötigt:

Gelee, 9 Bytes

×⁴%³’¬ø1#

Probieren Sie es online!

Wie es funktioniert

×⁴%³’¬ø1#
        #   Get the first
      ø1      one integer
            which meets:
×⁴            When multiplied by a
  %³          And modulo-d by b
    ’         Decrement
     ¬        Is falsy
fireflame241
quelle
4

Python 2 , 34 Bytes

f=lambda a,b:a==1or-~b*f(-b%a,a)/a

Probieren Sie es online!

Rekursive Funktion , die gibt Truefür print f(1,2), was ich glaube , akzeptabel zu sein, und Fehler für ungültige Eingaben.

Wir versuchen zu finden x in einx1(modb) .

Dies kann geschrieben werden als einx-1=kb , wo k eine ganze Zahl ist.

Nehmen modein davon ergibt-1kb(modein) . Bewegen des Minus ergibt-kb1(modein) , wo wir nachk .

Um zu sehen, wie es dem ursprünglichen Szenario ähnelt, lassen Sie uns rekursiv nach k auflösen, indem wir die Funktion mit f ( - b % a , a ) aufrufen.f(-b%ein,ein) (funktioniert, weil Python positive Werte für modulo mit einem negativen Argument ).

Das Programm wiederholt solange, bis ein zu 1 wird, was nur dann der Fall ist , wenn das Original ein und b miteinander koprimiert sind (dh eine multiplikative Inverse existiert), oder ein durch Division durch 0 verursachter Fehler auftritt.

Dieser Wert von k kann in der Gleichung einx-1=kb , um x als kb+1ein .

Kritixi Lithos
quelle
3

R + Zahlen , 15 Bytes

numbers::modinv

kehrt NAfür diejenigen aohne inverses mod zurück b.

R-Fiddle zum Ausprobieren!

R , 33 Bytes (nicht konkurrierend)

Dies wird sehr groß scheitern, bda es tatsächlich einen Vektor von 32*bGrößenbits erzeugt.

function(a,b)which((1:b*a)%%b==1)

Probieren Sie es online!

Gibt integer(0)(eine leere Liste) für diejenigen aohne inversen Mod zurück b.

Giuseppe
quelle
3

Mathematica, 18 Bytes

PowerMod[#,-1,#2]&

Eingang

[31, 73714876143]

J42161217
quelle
3

Python 2 , 51 49 54 53 51 49 Bytes

-1 Byte dank officialaimm
-1 Byte dank Shaggy

a,b=input()
i=a<2
while(a*i%b-1)*b%a:i+=1
print+i

Probieren Sie es online!

Druckt, 0wenn es keine Lösung gibt.

Stange
quelle
1
Ausgänge 0für a=1und b=2; Aus den Testfällen sollte es ausgeben 1.
Shaggy
Als rekursives Algo
Mr. Xcoder
1
Wie Shaggy wies darauf hin, nicht für2, 1
Herr Xcoder
@ Shaggy sollte jetzt funktionieren
Rod
Dadurch wird innerhalb von 60 Sekunden (bei TIO) keine Antwort für die Eingabe zurückgegeben 31,73714876143.
Ilmari Karonen
3

Japt , 9 8 Bytes

Nimmt die Eingaben in umgekehrter Reihenfolge vor. Ausgänge -1für keine Übereinstimmung. Schaltet aus, wenn die größere Ganzzahl größer wird.

Ç*V%UÃb1

Probier es aus

  • Dank ETH-Hinweis auf einen fehlerhaften und sehr offensichtlichen Platz 1 Byte gespart.
Zottelig
quelle
Die Testeingabe 73714876143,31scheint in Firefox einen Fehler wegen unzureichendem Arbeitsspeicher zu verursachen (und Chromium zum Absturz zu bringen). Ich denke nicht, dass dies eine gültige Antwort ist.
Ilmari Karonen
@IlmariKaronen: Ich habe in meiner Lösung deutlich darauf hingewiesen. Wir können für Codegolf von unendlich viel Speicher ausgehen, sodass Speicherprobleme und Abstürze diese Lösung nicht ungültig machen.
Shaggy
1
Leider kann aufgrund der Speicherprobleme auch nicht festgestellt werden, ob Ihr Code die Testfälle in 60 Sekunden tatsächlich lösen würde, wie es die Anforderung vorsieht. Ich vermute, dass dies nicht der Fall ist, selbst wenn ausreichend Speicher verfügbar ist, um einen Absturz zu vermeiden. Ohne einen Computer, auf dem das Programm tatsächlich so lange ausgeführt werden kann, ist dies jedoch nicht sicher zu erkennen.
Ilmari Karonen
2

Python 3 , 49 Bytes

lambda a,b:[c for c in range(b)if-~c*a%b==1][0]+1

Probieren Sie es online!

Python 3 , 50 Bytes

lambda a,b:[c for c in range(1,b+1)if c*a%b==1][0]

Probieren Sie es online!

Dies wird ausgelöst, IndexError: list index out of rangefalls es keine modulare multiplikative Inverse gibt, wie dies nach den Regeln zulässig ist.

Mr. Xcoder
quelle
Dadurch wird nach 31,7371487614360 Sekunden (bei TIO) kein Ergebnis für die Eingabe zurückgegeben .
Ilmari Karonen
@IlmariKaronen Scheint in 56 Sekunden auf meinem Computer (Macbook Pro '15)
fertig zu sein
2

8th , 6 Bytes

Code

invmod

Erläuterung

invmodist ein 8. Wort, das den Wert der Umkehrung von aModulo berechnet b. Es kehrt zurücknull bei Überlauf oder anderen Fehlern zurück.

Anwendungs- und Testfälle

ok> 1 2 invmod .
1
ok> 3 6 invmod .
null
ok> 7 87 invmod .
25
ok> 25 87 invmod .
7
ok> 2 91 invmod .
46
ok> 13 91 invmod .
null
ok> 19 1212393831 invmod .
701912218
ok> 31 73714876143 invmod .
45180085378
ok> 3 73714876143 invmod .
null
Chaos Manor
quelle
2

Pari / GP , 22 Bytes

a->b->lift(1/Mod(a,b))

Löst einen Fehler aus, wenn keine Inverse vorhanden ist.

Probieren Sie es online!

Alephalpha
quelle
2

J , 28 Bytes

4 :'(1=x+.y)*x y&|@^<:5 p:y'

Probieren Sie es online!

Verwendet den Satz von Euler . Gibt 0 zurück, wenn die Inverse nicht existiert.

Erläuterung

4 :'(1=x+.y)*x y&|@^<:5 p:y'  Input: a (LHS), b (RHS)
4 :'                       '  Define an explicit dyad - this is to use the special
                              form `m&|@^` to perform modular exponentiation
                          y   Get b
                      5 p:    Euler totient
                    <:        Decrement
             x                Get a
                   ^          Exponentiate
               y&|@             Modulo b
       x+.y                   GCD of a and b
     1=                       Equals 1
            *                 Multiply
Meilen
quelle
2

Pyth , 10 Bytes

3 Bytes gespart dank @Jakube .

xm%*szdQQ1

Probieren Sie es hier aus!

Gibt -1ohne multiplikative Inverse zurück.

Code-Aufschlüsselung

xm%*szdQQ1      Let Q be the first input.
 m      Q       This maps over [0 ... Q) with a variable d.
   *szd         Now d is multiplied by the evaluated second input.
  %    Q        Now the remained modulo Q is retrieved.
x        1      Then, the first index of 1 is retrieved from that mapping.

Pyth , 15 13 Bytes

KEhfq1%*QTKSK

Löst eine Ausnahme aus, falls keine multiplikative Inverse existiert.

Probieren Sie es hier aus!

Pyth , 15 Bytes

Iq1iQKEfq1%*QTK

Dies fügt viele Bytes hinzu, um den Fall zu behandeln, dass keine solche Anzahl existiert. Das Programm kann erheblich verkürzt werden, wenn dieser Fall nicht behandelt werden muss:

fq1%*QTK

Probieren Sie es hier aus!

Mr. Xcoder
quelle
2 Bytes gespeichert mitKExm%*QdKK1
Jakube
Oder 3 Bytes, wenn Sie die Reihenfolge der Eingaben xm%*szdQQ1
vertauschen
@ Jakube Vielen Dank, Bearbeitung!
Mr. Xcoder
Wie funktioniert das?
Kritixi Lithos
@Cowsquack Ich habe eine komplett primitive Code-Aufschlüsselung hinzugefügt, aber ich habe keine Zeit, eine vollständige Erklärung hinzuzufügen. Hoffentlich ist es für den Moment klar genug, aber ich werde versuchen, bald eine vollständigere Erklärung hinzuzufügen.
Mr. Xcoder
1

C (gcc) , 115 Bytes

#define L long long
L g(L a,L b,L c,L d){return a?g(b%a,a,d-b/a*c,c):b-1?0:d;}L f(L a,L b){return(g(a,b,1,0)+b)%b;}

Probieren Sie es online!

Erweiterter euklidischer Algorithmus, rekursive Version

C (gcc) , 119 Bytes

long long f(a,b,c,d,t,n)long long a,b,c,d,t,n;{for(c=1,d=0,n=b;a;a=t)t=d-b/a*c,d=c,c=t,t=b%a,b=a;return b-1?0:(d+n)%n;}

Probieren Sie es online!

Erweiterter euklidischer Algorithmus, iterative Version

nwellnhof
quelle
1

C (GCC) , 48 110 104 Bytes

#define f(a,b)g(a,b,!b,1,b)
long g(a,b,c,d,n)long a,b,c,d,n;{a=a?g(b%a,a,d,c-(b-b%a)/a*d):!--b*(c+n)%n;}

Probieren Sie es online!

Dies sollte innerhalb von 60 Sekunden bei allen Eingaben (die in eine lange passen) funktionieren.

Bearbeiten. Ich missbrauche die nVariable bereits, daher kann ich auch davon ausgehen, dass gcc die erste Zuweisung vornimmt %rax.

Ceilingcat
quelle
1
Leider führt dies zu falschen Ergebnissen, selbst bei relativ kleinen Eingaben aufgrund eines Ganzzahlüberlaufs innerhalb der Schleife. Beispielsweise wird f(3,1000001)717 zurückgegeben, was offensichtlich Unsinn ist (die richtige Antwort lautet 333334). Selbst wenn dieser Fehler durch Verwendung eines breiteren Integer-Typs behoben würde, würde dieser Brute-Force-Ansatz für einige der größeren Testfälle, die in der Herausforderung angegeben wurden, mit Sicherheit eine Zeitüberschreitung bedeuten.
Ilmari Karonen
0

Axiom, 45 Bytes

f(x:PI,y:PI):NNI==(gcd(x,y)=1=>invmod(x,y);0)

0 für Fehler sonst z mit x * z Mod y = 1 zurück

RosLuP
quelle
0

Python 2 , 52 Bytes

-3 Bytes dank Herrn Xcoder.

f=lambda a,b,i=1:i*a%b==1and i or i<b and f(a,b,i+1)

Probieren Sie es online!

Ausgaben Falseohne Lösung und Fehler werden bgrößer.

Embedded TIO

Ich teste gerade iframes in Stack Snippets und sie funktionieren absolut fantastisch.

total menschlich
quelle
Ich bin diese Werke nicht sicher, kann nicht i*a%bsein 0?
Weizen-Assistent
Fehler mit dem Fehler "Maximale Rekursionstiefe überschritten" für die Eingabe (31,73714876143).
Ilmari Karonen
0

JavaScript (ES6), 42 41 39 38 Byte

Ausgänge falsefür keine Übereinstimmung. Wirft einen Überlauffehler, wenn die zweite Zahl zu groß wird.

x=>y=>(g=z=>x*z%y==1?z:z<y&&g(++z))(1)
Zottelig
quelle
0

Gelee , 27 Bytes

²%³
⁴Ç⁹Сx⁸
ÆṪ’BṚçL$P%³×gỊ¥

Probieren Sie es online!

Verwendet den Satz von Euler mit modularer Exponentiation. Da Jelly nicht über eine integrierte Funktion zur Durchführung modularer Exponentiation verfügt, musste diese implementiert werden, und es wurden die meisten Bytes benötigt.

Meilen
quelle
0

Axiom, 99 Bytes

w(a,b,x,u)==(a=0=>(b*b=1=>b*x;0);w(b rem a,a,u,x-u*(b quo a)));h(a,b)==(b=0=>0;(b+w(a,b,0,1))rem b)

es benutzt die Funktion h (); h (a, b) gibt 0 zurück, wenn der Fehler [nicht existent invers] ist, andernfalls wird das z zurückgegeben, so dass a * z mod b = 1 Dies wäre auch dann in Ordnung, wenn die Argumente negativ sind ...

Dies wäre die allgemeine egcd () - Funktion, die eine Liste von int zurückgibt (sie können also auch negativ sein).

egcd(aa:INT,bb:INT):List INT==
   x:=u:=-1   -- because the type is INT
   (a,b,x,u):=(aa,bb,0,1)
   repeat
      a=0=>break
      (q,r):=(b quo a, b rem a)
      (b,a,x,u):=(a,r,u,x-u*q)
   [b,x, (b-x*aa)quo bb]

So benutzt man es

(7) -> h(31,73714876143)
   (7)  45180085378
                                                    Type: PositiveInteger

Ich finde die Basis Algo im Internet von https://pastebin.com/A13ybryc

RosLuP
quelle