Inverso multiplicativo modular

22

Sua tarefa é fornecer dois números inteiros ae bcalcular o inverso multiplicativo modular de um módulo b, se existir.

O inverso modular do amódulo bé um número ctal que ac ≡ 1 (mod b). Este número é um módulo únicob para qualquer par de ae b. Existe apenas se o maior divisor comum de ae bé 1.

A página da Wikipedia para inverso multiplicativo modular pode ser consultada se você precisar de mais informações sobre o tópico.

Entrada e saída

A entrada é fornecida como dois números inteiros ou como uma lista de dois números inteiros. Seu programa deve gerar um único número, o inverso multiplicativo modular que está no intervalo0 < c < b ou um valor indicando que não há inverso. O valor pode ser qualquer coisa, exceto um número no intervalo (0,b), e também pode ser uma exceção. O valor deve, no entanto, ser o mesmo para os casos em que não há inverso.

0 < a < b pode ser assumido

Regras

  • O programa deve terminar em algum momento e resolver cada caso de teste em menos de 60 segundos
  • Aplicam-se brechas padrão

Casos de teste

Os casos de teste abaixo são fornecidos no formato, 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

Pontuação

Este é o código de golfe, portanto o código mais curto para cada idioma vence.

Este e este são questões semelhantes, mas ambos pedir para situações específicas.

Halvard Hummel
fonte
6
Segue-se do Pequeno Teorema de Fermat que o inverso multiplicativo de a, se existir, pode ser computado eficientemente como a ^ (phi (b) -1) mod b, onde phi é a função totiente de Euler: phi (p0 ^ k0 * p1 ^ k1 * ...) = (p0-1) * p0 ^ (k0-1) * (p1-1) * p1 ^ (k1-1) * ... Não está dizendo que isso leva a um código mais curto :)
ngn
1
@ Jenny_mathy Receber informações adicionais geralmente não é permitido.
Mr. Xcoder
3
Conto seis respostas que parecem brutais, e é improvável que executem todos os casos de teste em 60 segundos (alguns deles causam erros de pilha ou memória primeiro).
Ørjan Johansen
1
@ngn: Você confundiu o pequeno teorema de Fermat (FLT) com a melhoria de Euler. Fermat não sabia sobre a função phi de Euler. Além disso, o aprimoramento de FLT e Euler somente se aplica se gcd (a, b) = 1. Finalmente, na forma em que você o escreveu, "a ^ (\ phi (b) -1) mod b" é congruente com 1, não com a ^ (- 1). Para obter um ^ (- 1), use um ^ (\ phi (b) -2) mod b.
Eric Towers
1
@EricTowers Euler é uma consequência. Em relação a "mcd (a, b) = 1" - eu disse "se [o inverso] existe". Você tem certeza sobre phi (b) -2?
NGN

Respostas:

11

Mathematica, 14 bytes

Mathematica obrigatório incorporado :

ModularInverse

É uma função que recebe dois argumentos ( ae b) e retorna o inverso de um mod b, se existir. Caso contrário, ele retornará o erro ModularInverse: a is not invertible modulo b..

Tutleman
fonte
7

JavaScript (ES6), 79 73 62 61 bytes

Devoluções false se o inverso não existir.

Ele usa o algoritmo euclidiano estendido e resolve todos os casos de teste quase instantaneamente.

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

Casos de teste

Arnauld
fonte
Por que não é possível escrever o nome da função f, como em 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)é sempre analisado como uma chamada de função, exceto se for explicitamente precedido pela functionpalavra - chave. Uma função de seta anônima, por outro lado, é declarada como (x,y)=>somethinge f=(x,y)=>somethingatribui a função à fvariável.
Arnauld
4

Geléia , 2 bytes

æi

Experimente online!

Isso usa um built-in para inverso modular e retorna 0 para nenhum inverso modular.

Geléia , 7 bytes

R×%⁸’¬T

Experimente online!

Produz um conjunto vazio (representado como sequência vazia) em nenhum inverso modular. Fica sem memória no TIO para os maiores casos de teste, mas deve funcionar com memória suficiente.

Como funciona

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.

Se você deseja trabalhar para casos de teste maiores, tente esta versão (relativamente não-destruída), que requer muito tempo e não memória:

Geléia, 9 bytes

×⁴%³’¬ø1#

Experimente online!

Como funciona

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

Python 2 , 34 bytes

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

Experimente online!

Função recursiva que dá Truepara print f(1,2), que eu acredito para ser aceitável, e erros de entradas inválidas.

Estamos tentando encontrar x em ax1(modb) .

Isso pode ser escrito como umax-1=kb ondek é um número inteiro.

Levando moda isto dá1kb(moda) . Mover o sinal de menos dákb1(moda) , onde temos que resolverk .

Vendo como ele se assemelha ao cenário inicial, permita-nos recuar para resolver k chamando a função com f(b%a,a) (funciona porque o Python fornece valores positivos para o módulo com argumento negativo).

O programa se repete até que a se torne 1, o que só acontece se o original a e b são coprime entre si (ou seja, existe um inverso multiplicativo) ou termina em um erro causado pela divisão por 0.

Este valor de k pode ser substituído na equação ax1=kb para dar x como kb+1a .

Kritixi Lithos
fonte
3

Números R + , 15 bytes

numbers::modinv

retorna NApara aqueles asem inversos mod b.

R-Fiddle para experimentá-lo!

R , 33 bytes (não concorrente)

Isso falhará em muito grande, bpois na verdade cria um vetor de 32*bbits de tamanho .

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

Experimente online!

Retorna integer(0)(uma lista vazia) para aqueles asem inversões mod b.

Giuseppe
fonte
3

Mathematica, 18 bytes

PowerMod[#,-1,#2]&

entrada

[31, 73714876143]

J42161217
fonte
3

Python 2 , 51 49 54 53 51 49 bytes

-1 byte graças a officialaimm
-1 byte graças a Shaggy

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

Experimente online!

Imprime 0quando não há solução.

Cajado
fonte
1
Saídas 0para a=1e b=2; dos casos de teste, ele deve ser gerado 1.
Shaggy
1
Como Shaggy apontou, falha para2, 1
Sr. Xcoder
@Shaggy deve funcionar agora
Rod
Isso não retorna uma resposta em 60 segundos (no TIO) para a entrada 31,73714876143.
Ilmari Karonen
3

Japonês , 9 8 bytes

Toma as entradas na ordem inversa. Saídas -1sem correspondência. Craps como o número inteiro maior fica maior.

Ç*V%UÃb1

Teste-o

  • Economizou 1 byte graças à ETH, indicando um espaço errante e muito óbvio.
Shaggy
fonte
A entrada de teste 73714876143,31parece produzir um erro de falta de memória no Firefox (e travar o Chromium). Não acho que seja uma resposta válida.
Ilmari Karonen
@IlmariKaronen: Eu indiquei claramente esse fato na minha solução. Podemos assumir memória infinita para os propósitos do código golf, para que os problemas e travamentos de memória não invalidem esta solução.
Shaggy
1
Infelizmente, os problemas de memória também tornam impossível saber se o seu código resolveria os casos de teste em 60 segundos, conforme estipulado pelo desafio. Eu suspeito que não, mesmo que houvesse memória suficiente disponível para não travar, mas sem um computador que possa executar o programa por tanto tempo, não há como ter certeza.
Ilmari Karonen
2

Python 3 + gmpy , 23 bytes

Eu não acho que pode ficar mais curto em Python.

gmpy.invert
import gmpy

Experimente online! (não funcionará se você não tiver o gmpy instalado)

Mr. Xcoder
fonte
2

Python 3 , 49 bytes

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

Experimente online!

Python 3 , 50 bytes

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

Experimente online!

Isso IndexError: list index out of rangeocorre caso não haja inverso multiplicativo modular, como é permitido pelas regras.

Mr. Xcoder
fonte
Isso não retorna um resultado para a entrada 31,73714876143em 60 segundos (no TIO).
Ilmari Karonen
@IlmariKaronen Parece terminar em 56 segundos na minha máquina (Macbook Pro '15)
Sr. Xcoder
2

8 , 6 bytes

Código

invmod

Explicação

invmodé uma oitava palavra que calcula o valor do inverso de a, módulo b. Retornanull em excesso ou em outros erros.

Casos de uso e teste

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
fonte
2

Pari / GP , 22 bytes

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

Lança um erro quando não há inverso.

Experimente online!

alefalpha
fonte
2

J , 28 bytes

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

Experimente online!

Usa o teorema de Euler . Retorna 0 se o inverso não existir.

Explicação

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
milhas
fonte
2

Pitão , 10 bytes

3 bytes salvos graças ao @Jakube .

xm%*szdQQ1

Experimente aqui!

Retorna -1para nenhum inverso multiplicativo.

Repartição do código

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.

Pitão , 15 13 bytes

KEhfq1%*QTKSK

Lança uma exceção caso não exista inversa multiplicativa.

Experimente aqui!

Pitão , 15 bytes

Iq1iQKEfq1%*QTK

Isso adiciona muitos bytes para lidar com o caso em que esse número não existe. O programa pode ser reduzido significativamente se esse caso não precisar ser tratado:

fq1%*QTK

Experimente aqui!

Mr. Xcoder
fonte
2 bytes salvos comKExm%*QdKK1
Jakube
Ou 3 bytes, se você trocar a ordem das entradas:xm%*szdQQ1
Jakube
@Jakube Muito obrigado, editando!
Mr. Xcoder
Como é que isso funciona?
Kritixi Lithos
@ Cowsquack Adicionei uma quebra de código completamente primitiva, mas rn não tenho tempo para incluir uma explicação completa. Espero que esteja claro o suficiente por enquanto, mas tentarei adicionar uma explicação mais completa em breve.
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;}

Experimente online!

Algoritmo euclidiano estendido, versão recursiva

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

Experimente online!

Algoritmo euclidiano estendido, versão iterativa

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

Experimente online!

Isso deve funcionar com todas as entradas (que cabem em um longo) em 60 segundos.

Editar. Já estou abusando da nvariável, portanto, posso assumir que o gcc coloca a primeira atribuição %rax.

teto
fonte
1
Infelizmente, isso gera resultados errados, mesmo para entradas relativamente pequenas devido ao excesso de números inteiros dentro do loop. Por exemplo, f(3,1000001)retorna 717, o que obviamente não faz sentido (a resposta correta é 333334). Além disso, mesmo que esse bug fosse corrigido usando um tipo inteiro mais amplo, essa abordagem de força bruta certamente atingiria o tempo limite para alguns dos casos de teste maiores apresentados no desafio.
Ilmari Karonen
0

Axioma, 45 bytes

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

0 para outro erro, retorne z com x * z Mod y = 1

RosLuP
fonte
0

Python 2 , 52 bytes

-3 bytes graças ao Sr. Xcoder.

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

Experimente online!

Saídas Falsesem solução e erros à medida que baumenta.

TIO incorporado

Estou apenas testando iframes no Stack Snippets e eles funcionam absolutamente fantásticos.

totalmente humano
fonte
Não tenho certeza se isso funciona, não pode i*a%bser 0?
Wheat Wizard
Falha com o erro "profundidade máxima de recursão excedida" para entrada (31,73714876143).
Ilmari Karonen
0

JavaScript (ES6), 42 41 39 38 bytes

Saídas falsesem correspondência. Irá gerar um erro de estouro quando o segundo número for muito grande.

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

Gelatina , 27 bytes

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

Experimente online!

Usa o teorema de Euler com exponenciação modular. Como o Jelly não possui um built-in para executar exponenciação modular, ele teve que ser implementado e levou a maior parte dos bytes.

milhas
fonte
0

Axioma, 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)

usa a função h (); h (a, b) retorna 0 se o erro [não existe inverso], caso contrário, ele retorna z de modo que a * z mod b = 1 Isso seria bom mesmo que os argumentos fossem negativos ...

essa seria a função egcd () geral que executa novamente uma lista de int (para que também possam ser negativas)

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]

é assim que usá-lo

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

eu acho o algo básico na internet em https://pastebin.com/A13ybryc

RosLuP
fonte