Pembalikan multiplikasi modular

22

Tugas Anda adalah memberikan dua angka bilangan bulat, adan bmenghitung inversi multiplikatif modular dari modulo b, jika ada.

Kebalikan modular dari amodulo badalah angka csedemikian rupa sehingga ac ≡ 1 (mod b). Angka ini adalah modulo unik buntuk setiap pasangan adan b. Ini ada hanya jika pembagi umum terbesar dari adan badalah 1.

The halaman Wikipedia untuk invers perkalian modular dapat dikonsultasikan jika Anda memerlukan informasi lebih lanjut tentang topik.

Masukan dan keluaran

Input diberikan sebagai dua bilangan bulat atau daftar dua bilangan bulat. Program Anda harus menampilkan angka tunggal, invers multiplikatif modular yang ada dalam interval 0 < c < b, atau nilai yang menunjukkan tidak ada invers. Nilai dapat berupa apa saja, kecuali angka dalam kisaran (0,b), dan mungkin juga merupakan pengecualian. Namun nilai harus sama untuk kasus-kasus di mana tidak ada invers.

0 < a < b dapat diasumsikan

Aturan

  • Program harus selesai pada titik tertentu, dan akan menyelesaikan setiap kasus uji dalam waktu kurang dari 60 detik
  • Celah standar berlaku

Uji kasus

Test case di bawah ini diberikan dalam 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

Mencetak gol

Ini adalah kode golf, jadi kode terpendek untuk setiap bahasa menang.

Ini dan ini adalah pertanyaan yang serupa, tetapi keduanya menanyakan situasi tertentu.

Halvard Hummel
sumber
6
Dari Teorema Kecil Fermat, invers multiplikasi dari a, jika ada, dapat dihitung secara efisien sebagai ^ (phi (b) -1) mod b, di mana phi adalah fungsi total Euler: phi (p0 ^ k0 * p1 ^ k1 * ...) = (p0-1) * p0 ^ (k0-1) * (p1-1) * p1 ^ (k1-1) * ... Tidak mengatakan itu mengarah pada kode yang lebih pendek :)
ngn
1
@ Jenny_mathy Mengambil input tambahan umumnya tidak diizinkan.
Tn. Xcoder
3
Saya menghitung enam jawaban yang tampaknya memaksa, dan tidak mungkin menjalankan semua kasus uji dalam 60 detik (beberapa dari mereka memberikan tumpukan atau kesalahan memori terlebih dahulu).
Ørjan Johansen
1
@ ngn: Anda telah menggabungkan Teorema Kecil Fermat (FLT) dengan peningkatan Euler. Fermat tidak tahu tentang fungsi Euler phi. Selanjutnya, peningkatan FLT dan Euler hanya berlaku jika gcd (a, b) = 1. Akhirnya, dalam bentuk yang Anda tulis, "a ^ (\ phi (b) -1) mod b" adalah kongruen dengan 1, bukan ^ (- 1). Untuk mendapatkan ^ (- 1), gunakan mod ^ (\ phi (b) -2) b.
Eric Towers
1
@EricTowers Euler adalah konsekuensinya. Mengenai "gcd (a, b) = 1" - Saya memang mengatakan "jika [kebalikannya] ada". Apakah Anda yakin tentang phi (b) -2?
ngn

Jawaban:

11

Mathematica, 14 byte

Wajib Matematika dibangun :

ModularInverse

Ini adalah fungsi yang mengambil dua argumen ( adan b), dan mengembalikan kebalikan dari mod b jika ada. Jika tidak, itu mengembalikan kesalahan ModularInverse: a is not invertible modulo b..

Pengawas
sumber
7

JavaScript (ES6), 79 73 62 61 byte

Mengembalikan falsejika invers tidak ada.

Ia menggunakan algoritma Euclidean yang diperluas dan menyelesaikan semua kasus uji hampir secara instan.

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

Uji kasus

Arnauld
sumber
Mengapa tidak mungkin menuliskan nama fungsi f, seperti pada 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)selalu diuraikan sebagai panggilan fungsi, kecuali jika secara eksplisit didahului oleh functionkata kunci. Fungsi panah anonim, di sisi lain, dinyatakan sebagai (x,y)=>somethingdan f=(x,y)=>somethingmenetapkan fungsi ke fvariabel.
Arnauld
4

Jelly , 2 byte

æi

Cobalah online!

Ini menggunakan builtin untuk invers modular, dan mengembalikan 0 tanpa invers modular.

Jelly , 7 byte

R×%⁸’¬T

Cobalah online!

Keluaran set kosong (direpresentasikan sebagai string kosong) tanpa pembalikan modular. Kehabisan memori pada TIO untuk kasus uji terbesar, tetapi harus bekerja mengingat memori yang cukup.

Bagaimana itu bekerja

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.

Jika Anda ingin bekerja untuk kasing yang lebih besar, coba versi ini (yang relatif tidak dipisahkan), yang membutuhkan lebih banyak waktu daripada memori:

Jelly, 9 byte

×⁴%³’¬ø1#

Cobalah online!

Bagaimana itu bekerja

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

Python 2 , 34 byte

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

Cobalah online!

Fungsi rekursif yang memberikan Trueuntuk print f(1,2), yang saya percaya dapat diterima, dan kesalahan untuk input tidak valid.

Kami berusaha untuk menemukan x dalam Sebuahx1(modb) .

Sebuahx-1=kbk

Pengambilan modSebuah-1kb(modSebuah)-kb1(modSebuah)k

kf(-b%Sebuah,Sebuah)

SebuahSebuahb

kSebuahx-1=kbxkb+1Sebuah

Kritixi Lithos
sumber
3

Angka R + , 15 byte

numbers::modinv

pengembalian NAuntuk yang atanpa mod invers b.

R-Fiddle untuk mencobanya!

R , 33 byte (tidak bersaing)

Ini akan gagal pada ukuran yang sangat besar bkarena ia sebenarnya membuat vektor 32*bbit ukuran .

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

Cobalah online!

Pengembalian integer(0)(daftar kosong) untuk yang atanpa mod terbalik b.

Giuseppe
sumber
3

Mathematica, 18 byte

PowerMod[#,-1,#2]&

memasukkan

[31, 73714876143]

J42161217
sumber
3

Python 2 , 51 49 54 53 51 49 byte

Terima kasih -1 byte ke officialaimm
-1 byte terima kasih kepada Shaggy

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

Cobalah online!

Mencetak 0saat tidak ada solusi.

tongkat
sumber
1
Output 0untuk a=1dan b=2; dari kasus uji, seharusnya keluar 1.
Shaggy
1
Seperti yang ditunjukkan Shaggy, gagal untuk2, 1
Tn. Xcoder
@Shaggy seharusnya bekerja sekarang
Rod
Ini gagal mengembalikan jawaban dalam 60 detik (pada TIO) untuk input 31,73714876143.
Ilmari Karonen
3

Japt , 9 8 byte

Mengambil input dalam urutan terbalik. Output -1tanpa kecocokan. Craps keluar saat bilangan bulat lebih besar semakin besar.

Ç*V%UÃb1

Menguji

  • Disimpan 1 byte berkat ETH yang menunjukkan ruang yang salah, dan sangat jelas.
Shaggy
sumber
Input tes 73714876143,31tampaknya menghasilkan kesalahan kehabisan memori pada Firefox (dan menabrak Chromium). Saya rasa ini bukan jawaban yang valid.
Ilmari Karonen
@IlmariKaronen: Saya dengan jelas menunjukkan fakta itu dalam solusi saya. Kami dapat mengasumsikan memori tak terbatas untuk keperluan kode golf sehingga masalah memori dan kerusakan tidak membatalkan solusi ini.
Shaggy
1
Sayangnya masalah memori juga membuat tidak mungkin untuk mengatakan apakah kode Anda benar-benar akan menyelesaikan kasus pengujian dalam 60 detik sebagaimana ditentukan oleh tantangan. Saya kira itu tidak akan terjadi, bahkan jika ada cukup memori yang tersedia untuk membuatnya tidak crash, tetapi tanpa komputer yang benar-benar dapat menjalankan program selama itu tidak ada cara untuk memastikannya.
Ilmari Karonen
2

Python 3 + gmpy , 23 byte

Saya tidak berpikir itu bisa lebih pendek dengan Python.

gmpy.invert
import gmpy

Cobalah online! (tidak akan berfungsi jika gmpy Anda belum diinstal)

Tuan Xcoder
sumber
2

Python 3 , 49 byte

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

Cobalah online!

Python 3 , 50 byte

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

Cobalah online!

Ini melempar IndexError: list index out of rangekalau-kalau tidak ada invers multiplikatif modular, karena diizinkan oleh aturan.

Tuan Xcoder
sumber
Ini gagal mengembalikan hasil untuk input 31,73714876143dalam 60 detik (pada TIO).
Ilmari Karonen
@IlmariKaronen Tampaknya selesai dalam 56 detik di komputer saya (Macbook Pro '15)
Mr. Xcoder
2

8 , 6 byte

Kode

invmod

Penjelasan

invmodadalah kata ke 8 yang menghitung nilai kebalikan dari a, modulo b. Ia mengembalikan nullpada overflow atau kesalahan lainnya.

Penggunaan dan uji kasus

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
Kekacauan Manor
sumber
2

Pari / GP , 22 byte

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

Melempar kesalahan saat tidak ada terbalik.

Cobalah online!

alephalpha
sumber
2

J , 28 byte

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

Cobalah online!

Penggunaan teorema Euler . Mengembalikan 0 jika kebalikannya tidak ada.

Penjelasan

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
mil
sumber
2

Pyth , 10 byte

3 byte disimpan berkat @Jakube .

xm%*szdQQ1

Coba di sini!

Kembali -1 tanpa pembalikan multiplikasi.

Rincian Kode

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 byte

KEhfq1%*QTKSK

Melempar pengecualian jika tidak ada inversi multiplikasi.

Coba di sini!

Pyth , 15 byte

Iq1iQKEfq1%*QTK

Ini menambahkan banyak byte untuk menangani kasus di mana tidak ada nomor tersebut. Program ini dapat dipersingkat secara signifikan jika kasus itu tidak perlu ditangani:

fq1%*QTK

Coba di sini!

Tuan Xcoder
sumber
2 byte disimpan denganKExm%*QdKK1
Jakube
Atau 3 byte jika Anda menukar urutan input:xm%*szdQQ1
Jakube
@ Jakube Terima kasih banyak, sunting!
Tn. Xcoder
Bagaimana cara kerjanya?
Kritixi Lithos
@ Cowsquack Saya telah menambahkan rincian kode yang benar-benar primitif tetapi saya tidak punya waktu untuk memasukkan penjelasan lengkap. Semoga cukup jelas untuk saat ini tetapi saya akan mencoba untuk menambahkan penjelasan yang lebih lengkap segera.
Tn. Xcoder
1

C (gcc) , 115 byte

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

Cobalah online!

Algoritma Euclidean yang diperluas, versi rekursif

C (gcc) , 119 byte

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

Cobalah online!

Algoritma Euclidean yang diperluas, versi iteratif

nwellnhof
sumber
1

C (gcc) , 48 110 104 byte

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

Cobalah online!

Ini harus bekerja dengan semua input (yang cocok dalam waktu lama) dalam 60 detik.

Edit. Saya sudah menyalahgunakan nvariabel jadi saya mungkin juga berasumsi bahwa gcc menempatkan tugas pertama di %rax.

plafon
sumber
1
Sayangnya, ini memberikan hasil yang salah bahkan untuk input yang cukup kecil karena integer overflow di dalam loop. Misalnya, f(3,1000001)mengembalikan 717, yang jelas-jelas tidak masuk akal (jawaban yang benar adalah 333334). Juga, bahkan jika bug ini diperbaiki dengan menggunakan tipe integer yang lebih luas, pendekatan brute-force ini pasti akan habis untuk beberapa kasus uji yang lebih besar yang diberikan dalam tantangan.
Ilmari Karonen
0

Aksioma, 45 byte

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

0 untuk kesalahan lain kembalikan z dengan x * z Mod y = 1

RosLuP
sumber
0

Python 2 , 52 byte

-3 byte terima kasih kepada Tn. Xcoder.

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

Cobalah online!

Output Falsetanpa solusi dan kesalahan keluar karena bsemakin besar.

TIO tertanam

Saya hanya menguji iframe di Stack Snippets dan mereka bekerja sangat fantastis.

benar-benar manusiawi
sumber
Saya tidak yakin ini berhasil, tidak i*a%bbisa 0?
Wheat Wizard
Gagal dengan kesalahan "kedalaman rekursi maksimum terlampaui" untuk input (31,73714876143).
Ilmari Karonen
0

JavaScript (ES6), 42 41 39 38 byte

Output falsetanpa kecocokan. Akan menimbulkan kesalahan overflow karena angka kedua terlalu besar.

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

Jelly , 27 byte

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

Cobalah online!

Menggunakan teorema Euler dengan eksponensial modular. Karena Jelly tidak memiliki builtin untuk melakukan eksponensial modular, itu harus diimplementasikan, dan butuh sebagian besar byte.

mil
sumber
0

Aksioma, 99 byte

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)

menggunakan fungsi h (); h (a, b) mengembalikan 0 jika kesalahan [tidak ada kebalikan] jika tidak mengembalikan z sedemikian sehingga * z mod b = 1 Ini akan baik-baik saja walaupun argumen negatif ...

ini akan menjadi fungsi egcd () umum yang mengembalikan daftar int (sehingga mereka juga bisa negatif)

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]

beginilah cara menggunakannya

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

saya menemukan basis algo di internet dari https://pastebin.com/A13ybryc

RosLuP
sumber