Inverse multiplicatif modulaire

22

Votre tâche consiste à donner deux nombres entiers aet à bcalculer l'inverse multiplicatif modulaire d'un modulo b, s'il existe.

L'inverse modulaire de amodulo best un nombre ctel que ac ≡ 1 (mod b). Ce numéro est un modulo unique bpour toute paire de aet b. Il n'existe que si le plus grand diviseur commun de aet best 1.

La page Wikipedia pour l'inverse multiplicatif modulaire peut être consultée si vous avez besoin de plus d'informations sur le sujet.

Entrée et sortie

L'entrée est donnée sous la forme de deux entiers ou d'une liste de deux entiers. Votre programme doit produire soit un nombre unique, l'inverse multiplicatif modulaire qui se trouve dans l'intervalle 0 < c < b, soit une valeur indiquant qu'il n'y a pas d'inverse. La valeur peut être n'importe quoi, sauf un nombre dans la plage (0,b), et peut également être une exception. La valeur doit cependant être la même pour les cas où il n'y a pas d'inverse.

0 < a < b peut être supposé

Règles

  • Le programme devrait se terminer à un moment donné et devrait résoudre chaque cas de test en moins de 60 secondes
  • Des échappatoires standard s'appliquent

Cas de test

Les cas de test ci-dessous sont donnés dans le format, 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

Notation

C'est le golf de code, donc le code le plus court pour chaque langue gagne.

Ceci et ceci sont des questions similaires, mais les deux demandent des situations spécifiques.

Halvard Hummel
la source
6
Il résulte du Petit Théorème de Fermat que l'inverse multiplicatif de a, s'il existe, peut être calculé efficacement comme un ^ (phi (b) -1) mod b, où phi est la fonction totiente d'Euler: phi (p0 ^ k0 * p1 ^ k1 * ...) = (p0-1) * p0 ^ (k0-1) * (p1-1) * p1 ^ (k1-1) * ... Ne pas dire que cela conduit à un code plus court :)
ngn
1
@Jenny_mathy Prendre des entrées supplémentaires est généralement interdit.
M. Xcoder
3
Je compte six réponses qui semblent être un forçage brutal et peu susceptibles d'exécuter tous les cas de test en 60 secondes (certains donnent d'abord une erreur de pile ou de mémoire).
Ørjan Johansen
1
@ngn: Vous avez confondu le petit théorème de Fermat (FLT) avec l'amélioration d'Euler. Fermat ne connaissait pas la fonction phi d'Euler. De plus, l'amélioration de FLT et d'Euler ne s'applique que si gcd (a, b) = 1. Enfin, sous la forme que vous l'avez écrite, "a ^ (\ phi (b) -1) mod b" est congru à 1, pas a ^ (- 1). Pour obtenir un ^ (- 1), utilisez un mod b (^ (\ phi (b) -2).
Eric Towers
1
@EricTowers Euler est une conséquence. Concernant "gcd (a, b) = 1" - j'ai dit "s'il existe [l'inverse]". Êtes-vous sûr de phi (b) -2?
ngn

Réponses:

11

Mathematica, 14 octets

Mathematica obligatoire intégré :

ModularInverse

C'est une fonction qui prend deux arguments ( aet b), et retourne l'inverse d'un mod b s'il existe. Sinon, il renvoie l'erreur ModularInverse: a is not invertible modulo b..

Tutleman
la source
7

JavaScript (ES6), 79 73 62 61 octets

Renvoie falsesi l'inverse n'existe pas.

Il utilise l'algorithme euclidien étendu et résout tous les cas de test presque instantanément.

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

Cas de test

Arnauld
la source
Pourquoi n'est-il pas possible d'écrire le nom de la fonction f, comme dans 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)est toujours analysé comme un appel de fonction, sauf s'il est explicitement précédé du functionmot - clé. Une fonction de flèche anonyme, en revanche, est déclarée comme (x,y)=>somethinget f=(x,y)=>somethingaffecte la fonction à la fvariable.
Arnauld
4

Gelée , 2 octets

æi

Essayez-le en ligne!

Cela utilise une fonction intégrée pour l'inverse modulaire et renvoie 0 pour aucune inverse modulaire.

Gelée , 7 octets

R×%⁸’¬T

Essayez-le en ligne!

Produit un ensemble vide (représenté comme une chaîne vide) sur aucun inverse modulaire. Manque de mémoire sur TIO pour les plus grands cas de test, mais devrait fonctionner avec suffisamment de mémoire.

Comment ça marche

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.

Si vous souhaitez travailler pour des cas de test plus importants, essayez cette version (relativement non gérée), qui nécessite beaucoup de temps plutôt que de mémoire:

Gelée, 9 octets

×⁴%³’¬ø1#

Essayez-le en ligne!

Comment ça marche

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

Python 2 , 34 octets

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

Essayez-le en ligne!

Fonction récursive qui donne Truepourprint f(1,2) , que je pense être acceptable, et des erreurs pour les entrées invalides.

Nous essayons de trouver x dans ax1(modb) .

Cela peut être écrit comme ax1=kbk est un entier.

Prise moda de ceci donne1kb(moda) . Déplacer le moins donnekb1(moda) , où nous devons résoudre pourk .

Voyant comment il ressemble au scénario initial, permettez-nous de recurse pour résoudre pour k en appelant la fonction avec f(b%a,a) (fonctionne parce que Python donne des valeurs positives pour modulo avec un argument négatif).

Le programme se répète jusqu'à ce a devienne 1, ce qui ne se produit que si l'original a et b sont premiers entre eux (c'est-à-dire qu'il existe un inverse multiplicatif), ou se termine par une erreur causée par la division par 0.

Cette valeur de k peut être substituée dans l'équation ax1=kb pour donner x comme kb+1a .

Kritixi Lithos
la source
3

Numéros R + , 15 octets

numbers::modinv

renvoie NApour ceux asans inverses mod b.

R-Fiddle pour l'essayer!

R , 33 octets (non concurrent)

Cela échouera sur de très gros volumes bcar il crée en fait un vecteur de 32*bbits de taille .

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

Essayez-le en ligne!

Renvoie integer(0)(une liste vide) pour ceux asans inverses mod b.

Giuseppe
la source
3

Mathematica, 18 octets

PowerMod[#,-1,#2]&

contribution

[31, 73714876143]

J42161217
la source
3

Python 2 , 51 49 54 53 51 49 octets

-1 octet grâce à officialaimm
-1 octet grâce à Shaggy

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

Essayez-le en ligne!

Imprime 0lorsqu'il n'y a pas de solution.

Barre
la source
1
Sorties 0pour a=1et b=2; à partir des cas de test, il devrait sortir 1.
Shaggy
1
Comme l'a souligné Shaggy, échoue pour2, 1
M. Xcoder
@Shaggy devrait fonctionner maintenant
Rod
Cela ne renvoie pas de réponse dans 60 secondes (sur TIO) pour l'entrée 31,73714876143.
Ilmari Karonen
3

Japt , 9 8 octets

Prend les entrées dans l'ordre inverse. Sorties -1pour aucune correspondance. Craps lorsque le plus grand entier devient plus grand.

Ç*V%UÃb1

Essaye-le

  • 1 octet sauvé grâce à ETH signalant un espace errant et très évident.
Hirsute
la source
L'entrée de test 73714876143,31semble produire une erreur de mémoire insuffisante sur Firefox (et planter Chromium). Je ne pense pas que ce soit une réponse valable.
Ilmari Karonen
@IlmariKaronen: J'ai clairement souligné ce fait dans ma solution. Nous pouvons supposer une mémoire infinie à des fins de code golf afin que les problèmes de mémoire et les plantages n'invalident pas cette solution.
Shaggy
1
Malheureusement, les problèmes de mémoire ne permettent pas non plus de dire si votre code résoudrait réellement les cas de test en 60 secondes, comme stipulé par le défi. Je soupçonne que ce ne serait pas le cas, même s'il y avait suffisamment de mémoire disponible pour le faire ne pas planter, mais sans un ordinateur qui peut réellement exécuter le programme aussi longtemps, il n'y a aucun moyen de le savoir avec certitude.
Ilmari Karonen
2

Python 3 + gmpy , 23 octets

Je ne pense pas que cela puisse devenir plus court en Python.

gmpy.invert
import gmpy

Essayez-le en ligne! (ne fonctionnera pas si vous n'avez pas installé gmpy)

M. Xcoder
la source
2

Python 3 , 49 octets

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

Essayez-le en ligne!

Python 3 , 50 octets

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

Essayez-le en ligne!

Cela jette IndexError: list index out of rangedans le cas où il n'y a pas d'inverse multiplicatif modulaire, comme cela est autorisé par les règles.

M. Xcoder
la source
Cela ne renvoie pas de résultat pour l'entrée 31,73714876143en 60 secondes (sur TIO).
Ilmari Karonen
@IlmariKaronen Semble terminer en 56 secondes sur ma machine (Macbook Pro '15)
M. Xcoder
2

8e , 6 octets

Code

invmod

Explication

invmodest un 8ème mot qui calcule la valeur de l'inverse de a, modulo b. Il revient nullen cas de débordement ou d'autres erreurs.

Cas d'utilisation et de test

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
Manoir du Chaos
la source
2

J , 28 octets

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

Essayez-le en ligne!

Utilise le théorème d'Euler . Renvoie 0 si l'inverse n'existe pas.

Explication

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
miles
la source
2

Pyth , 10 octets

3 octets enregistrés grâce à @Jakube .

xm%*szdQQ1

Essayez-le ici!

Résultats -1 pour aucun inverse multiplicatif.

Répartition du code

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 octets

KEhfq1%*QTKSK

Lève une exception dans le cas où aucun inverse multiplicatif n'existe.

Essayez-le ici!

Pyth , 15 octets

Iq1iQKEfq1%*QTK

Cela ajoute beaucoup d'octets pour gérer le cas où un tel nombre n'existe pas. Le programme peut être considérablement raccourci si ce cas n'a pas besoin d'être traité:

fq1%*QTK

Essayez-le ici!

M. Xcoder
la source
2 octets enregistrés avecKExm%*QdKK1
Jakube
Ou 3 octets si vous échangez l'ordre des entrées:xm%*szdQQ1
Jakube
@Jakube Merci beaucoup, édition!
M. Xcoder
Comment cela marche-t-il?
Kritixi Lithos
@Cowsquack J'ai ajouté une ventilation de code complètement primitive mais je n'ai pas le temps d'inclure une explication complète. J'espère que c'est assez clair pour le moment mais j'essaierai d'ajouter bientôt une explication plus complète.
M. Xcoder
1

C (gcc) , 115 octets

#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;}

Essayez-le en ligne!

Algorithme euclidien étendu, version récursive

C (gcc) , 119 octets

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;}

Essayez-le en ligne!

Algorithme euclidien étendu, version itérative

nwellnhof
la source
1

C (gcc) , 48 110 104 octets

#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;}

Essayez-le en ligne!

Cela devrait fonctionner avec toutes les entrées (qui tiennent dans une longue) dans les 60 secondes.

Modifier. J'abuse déjà de la nvariable, donc je pourrais aussi bien supposer que gcc place la première affectation %rax.

plafond
la source
1
Hélas, cela donne de mauvais résultats même pour des entrées assez petites en raison d'un débordement d'entier à l'intérieur de la boucle. Par exemple, f(3,1000001)renvoie 717, ce qui est évidemment un non-sens (la bonne réponse est 333334). De plus, même si ce bogue a été corrigé en utilisant un type entier plus large, cette approche par force brute expirerait certainement pour certains des cas de test les plus importants donnés dans le défi.
Ilmari Karonen
0

Axiome, 45 octets

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

0 pour erreur sinon retourner z avec x * z Mod y = 1

RosLuP
la source
0

Python 2 , 52 octets

-3 octets grâce à M. Xcoder.

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

Essayez-le en ligne!

Sorties Falsesur aucune solution et erreurs surb volume augmente.

TIO intégré

Je teste simplement les iframes dans les extraits de pile et ils fonctionnent absolument fantastique.

totalement humain
la source
Je ne suis pas certain cela fonctionne, ne peut pas i*a%bêtre 0?
Wheat Wizard
Échec avec l'erreur "profondeur de récursivité maximale dépassée" pour l'entrée (31,73714876143).
Ilmari Karonen
0

JavaScript (ES6), 42 41 39 38 octets

Sorties falsepour aucune correspondance. Lance une erreur de débordement lorsque le deuxième nombre devient trop grand.

x=>y=>(g=z=>x*z%y==1?z:z<y&&g(++z))(1)
Hirsute
la source
0

Gelée , 27 octets

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

Essayez-le en ligne!

Utilise le théorème d'Euler avec une exponentiation modulaire. Étant donné que Jelly n'a pas de fonction intégrée pour effectuer l'exponentiation modulaire, il a dû être implémenté et a pris la plupart des octets.

miles
la source
0

Axiome, 99 octets

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)

il utilise la fonction h (); h (a, b) retourne 0 si erreur [n'existe pas inverse] sinon il retourne le z tel que a * z mod b = 1 Ce serait ok même si les arguments sont négatifs ...

ce serait la fonction générale egcd () qui retournera une liste d'int (donc ils peuvent aussi être négatifs)

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]

voici comment l'utiliser

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

je trouve l'algo de base dans Internet à partir de https://pastebin.com/A13ybryc

RosLuP
la source