Inversi Tersembunyi (Utang Perampok)

16

Ini adalah teka teki , utas polisi dapat ditemukan di sini.

Tugas Anda adalah menemukan anagram program yang disediakan di utas polisi yang melakukan kebalikannya.

Setelah Anda memecahkan sebuah jawaban, solusinya sebagai jawaban di bawah ini dan beri tahu penjawab aslinya.

Anda akan dinilai berdasarkan jumlah program yang Anda ikuti terlebih dahulu.

Posting Rock Garf Hunter
sumber

Jawaban:

21

Python 3, 46 byte, Lynn

lambda x0223334566789:(x0223334566789*89)//178
GB
sumber
Bagaimana saya "memberi tahu penjawab asli"?
GB
Berikan komentar yang menghubungkan jawaban Anda dengan yang asli
Sefa
Anda harus meletakkan f=di awal kode Anda karena tidak diperlukan dan bukan bagian dari fungsi aslinya
0 '
Selesai, saya hanya menyalin-menempelnya terlalu cepat.
GB
16
Di sini saya benar-benar kasar memaksa solusi (dan bahkan dengan asumsi ada) dan Anda hanya menghindari seluruh masalah! +1
orlp
14

Python 2, 225 byte, orlp

p=90930641353124136621573325641513715557077985927835294018496194596645372722158;q=101979812089012306249375934082966806799688507587087308196267706260111970225882#--223444799
lambda n:pow(n,pow(65537,(p*q-2*(p+q))/4,p*q),~p*~q)

Kira saya beruntung setelah menebak pembagi prime acak sepanjang hari ...

(Batas tempat c4.8xlarge default adalah 4, tapi saya berhasil menabraknya menjadi 10 tahun lalu. Harus mengubah konfigurasi FAAS dari 16 slave menjadi 6 slave (+3 mpi, 1 master). 20m polyselect, 12h 50m saringan, 2h 25m linalg, 30m sqrt. Total biaya ~ $ 70. Setidaknya @orlp cukup baik untuk memilih ukuran yang dapat dipecahkan, tapi saya tidak melakukan ini lagi! Terima kasih kepada @IlmariKaronen untuk langkah terakhir, dan ya saya bercanda tentang menebak: P)

Sp3000
sumber
Aku .. apa ... Sekarang aku merasa tidak enak karena menghabiskan uang untukmu :( Aku sengaja memilih ukuran yang masih cukup kecil tapi terlalu mahal untuk menyerang. Aku tidak benar-benar berpikir ada orang yang mau mengeluarkan uang untuk ini.
orlp
1
@ Atlp Sangat berharga sebagai pengalaman satu kali bagi saya. Saya harap orang-orang mempelajari sesuatu tentang keamanan RSA 512-bit di alam bebas dari ini :)
Sp3000
Ini adalah dedikasi nyata untuk bermain golf, tidak hanya menghabiskan waktu tetapi juga uang! Menarik untuk dicatat bahwa penyerang berpotensi mematahkan RSA 512-bit secara gratis melalui uji coba layanan komputasi awan.
mil
@miles Saya harus menyebutkan bahwa AWS memiliki kredit untuk siswa jika ada yang mau mencoba, dan saya tidak akan terkejut jika layanan lain melakukan hal yang sama. Karenanya Anda mungkin tidak jauh dengan gagasan uji coba itu, setidaknya untuk pertama kalinya. (Jika ada yang ingin mencoba - pastikan Anda menghapus semua volume, AMI, dll begitu Anda selesai karena jika tidak Anda akan dikenakan biaya untuk penyimpanan)
Sp3000
11

Python 2, 83 byte, orlp

Asli:

#((()))****+,,---/2289;==oppppppqqqqqw~~
lambda n:pow(n,65537,10998167423251438693)

Retak:

p=3207399658;q=3428998126#--11
lambda n:pow(n,pow(65537,(p*q-2*(p+q))/4,p*q),~p*~q)

Cobalah online!

Retak RSA dilakukan oleh Wolfram Alpha . ;)

Ilmari Karonen
sumber
Saya baru sadar bahwa ~p*~qlurus lebih pendek dari -~p*-~q, oops.
orlp
Bagaimana Anda membalik (p*q-2*(p+q))/4bagian itu? :)
orlp
Itu adalah bagian yang paling sulit, bukan? Pada dasarnya, pengetahuan tentang fungsi Carmichael dan fakta bahwa p/2dan q/2keduanya merupakan bilangan prima yang aneh, dan sekelompok percobaan dan kesalahan untuk menemukan sesuatu yang akan bekerja menggunakan karakter yang tersedia.
Ilmari Karonen
Saya sengaja memilih pdan q(yang asli, yang ada dalam kode adalah p-1dan q-1untuk tujuan bermain golf) sedemikian rupa sehingga (p-1)/2yang utama adalah yang kita miliki φ(φ(pq)) = ((p-1)/2-1)((q-1)/2-1). Ini memungkinkan kita untuk menghitung 65537mod invers modular φ(pq)(apa yang kita butuhkan untuk RSA) menggunakan identitas Euler, membuat jawabannya jauh lebih singkat karena kita tidak perlu mengimplementasikan logika invers modular atau hardcode konstanta besar lainnya. Terlepas dari -~q*-~p-> ~q*~p, Anda menemukan persis fungsi saya :)
orlp
1
Sebenarnya, untuk memilih nit kecil, saya percaya φ(φ(pq)) = 2((p-1)/2-1)((q-1)/2-1)untuk bilangan prima yang aman pdan q, karena φ(4) = 2. Tetapi λ(φ(pq)) = lcm(2, (p-1)/2-1, (q-1)/2-1)paling banyak ((p-1)/2-1)((q-1)/2-1)/2, dan kelipatannya, minus satu, akan berlaku untuk eksponen. :)
Ilmari Karonen
7

Python 3, 80 byte, Wolfram

from bisect import*
q=int(input())
print(bisect([(h+1)**2 for h in range(q)],q))

Ini sangat sulit untuk dipecahkan! Saya menggunakan perpustakaan dua bagian , yang termasuk dalam distribusi Python 3. The bisectfungsi mengambil daftar diurutkan dan elemen, dan mengembalikan indeks paling kanan di mana elemen dapat dimasukkan untuk menjaga ketertiban. Kami hanya memberikannya qdaftar panjang kotak mulai dari 1dan elemen q.

Zgarb
sumber
1
Saya akan menyarankan perubahan (h+1)ke -~h. Kemudian saya menyadari bahwa bukan itu inti dari tantangan ini: P
ETHproduksi
@ ETHproductions Itu toh tidak benar karena operator diutamakan.
Sp3000
@ Sp3000 Huh, saya tidak tahu yang **memiliki prioritas lebih tinggi daripada ~di Python. Saya kira itu lebih baik daripada di JS, di mana -~2**2melempar kesalahan sintaksis ("ekspresi unary yang tidak dapat dipersonalisasi tidak dapat muncul di sisi kiri '**'").
ETHproduk
@ ETHproductions Mereka benar-benar melakukan itu untuk menghindari ambiguitas, yang, seperti yang akan saya tambahkan, sangat tidak khas pada kebanyakan desain JS.
Buah Esolanging
@ Challenger5 Sebenarnya, saya harus tidak setuju dengan Anda di sana: dalam beberapa tahun terakhir TC39 telah sangat berhati-hati untuk memastikan setiap fitur baru yang ditambahkan sama sekali bebas dari ambiguitas mungkin (yang termasuk **operator, ditambahkan dalam ES2017)
ETHproductions
6

Javascript, 21 byte, Arnauld

Asli

b=>Math.pow(b,torc=3)

Retak

o=>Math.cbrt(o,pbw=3)

Mengembalikan akar pangkat tiga.

Emigna
sumber
Ini dia! ;)
Arnauld
@Arnauld: Saya merasa sedikit aneh bahwa JS memungkinkan Anda untuk memanggil fungsi dengan lebih banyak argumen daripada yang didefinisikan untuknya. Saya bertanya-tanya apa pemikiran di balik itu.
Emigna
6
Anda benar, JS memungkinkan desain. Argumen tambahan tidak sepenuhnya hilang, karena disimpan dalam objek argumen yang dapat diakses secara manual oleh fungsi.
Arnauld
5

7, 9 byte, ais523

00000000: 0173 dc25 7e13 dcb6 1f                   .s.%~....

Karena kekerasan selalu menang, dan 9! hanya 362880

GB
sumber
4

Memproses.js, 59 byte, Kritixi Lithos

Asli:

float igetuwebaoli(int p){return p*(((17*-4*-3)))+0+0;}//,,

Retak:

int loabewuteg(float p,i){return (i+0**+0,(p/17/(-4*-3)));}

Yah, itu cukup mudah. Bagian tersulit adalah mencari tahu di mana harus menempel koma dan tanda bintang tambahan. Untungnya, tampaknya Pemrosesan memungkinkan parameter fungsi tambahan yang tidak digunakan serta ekspresi koma gaya-C.

Ilmari Karonen
sumber
1
Rupanya, penerjemah yang saya tautkan salah. Bahkan, sebagian besar (atau bahkan semua) penerjemah online mungkin akan salah karena Processing-java akan dikompilasi ke Processing.js. Saat ini, saya pikir tindakan terbaik adalah bagi saya dan Anda untuk mengubah jawaban kami menjadi "Processing.js" alih-alih Memproses karena jawaban Anda akan valid (Memproses-java memberikan banyak kesalahan). Saya akan memposting jawaban terpisah dengan kode yang sama dengan Processing-java, tetapi untuk ini penerjemah sarang akan menginstalnya dari processing.org. Pokoknya dilakukan dengan baik!
Kritixi Lithos
4

JavaScript (ES6), 63 byte, SLuck49

Asli:

x=>eval(atob`eCp4KzEvLyAgfXBModLS4TvEn4wp1iys9YRRKC85KLIhNMC=`)

Retak:

x=>eval(atob`CgpNYXRoLnBvdyh4LTEsMC41KSAvLw4589CEIKKMRefipyz=`)

Kode base64 di atas menerjemahkan ke:



Math.pow(x-1,0.5) //...

Dimana ... singkatan dari sekelompok sampah acak yang diabaikan oleh penerjemah JS, karena itu dalam komentar.

Saya menemukan solusi ini dengan coba-coba. Pada akhirnya, bagian hanya benar-benar rumit adalah dua baris di awal kode, diperlukan untuk membuat garis sisanya dengan benar dan untuk mendapatkan Mdi Mathke base64-encode menjadi sesuatu yang tersedia di set karakter asli. Saya pertama kali mencoba spasi, tetapi " M"base64-encode ke "ICBN"dan saya membutuhkan satu-satunya yang tersedia Buntuk mengkodekan ".po"nanti dalam kode. "0+M", "1*M", "1?M"Atau awalan no-op serupa lainnya yang dapat saya pikirkan tidak berhasil, tapi baris lakukan.

Saya menduga ini mungkin bukan solusi yang dimaksudkan, tetapi apa pun - itu berhasil. :)

Demo:

var f = x=>eval(atob`eCp4KzEvLyAgfXBModLS4TvEn4wp1iys9YRRKC85KLIhNMC=`)
var g = x=>eval(atob`CgpNYXRoLnBvdyh4LTEsMC41KSAvLw4589CEIKKMRefipyz=`)
for (var i = -0; i <= 10; i++) console.log(i, '->', f(i), '->', g(f(i)))

Ilmari Karonen
sumber
Kerja
Mengesankan :) Saya mengambil pendekatan yang persis sama tetapi tidak berpikir untuk mencoba baris baru. Saya mencoba untuk kehilangan C di tempat lain tetapi tidak berhasil.
Chris M
3

Brain-Flak, 26 byte, Wheat Wizard

Asli (tambah 13)

((((()()())){}[()]){}{}{})

Retak (kurangi 13)

([(((()())()){}){}{}](){})
0 '
sumber
3

J, 8 byte, mil

[:]-:[+:

Penukaran sederhana +:untuk -:(dobel untuk separuh).

Conor O'Brien
sumber
Juga Anda dapat menukar kata kerja kiri dan kanan: [:[+:]-:.
randomra
3

Python 2, 47 byte, Wheat Wizard

lambda x:sorted(a**2for a in range(x)).index(x)
nmjcman101
sumber
Kerja bagus! Anda menemukan solusi tepat yang ada dalam pikiran saya
Post Rock Garf Hunter
3

JavaScript (ES6), 46 byte, SLuck49

Asli (menghitung ln (x + 1))

x=>Math.log(x+(+String(t=985921996597669)[5]))

Retak

x=>Math[(lg=19979699+55686).toString(9+25)](x)

Saya tidak akan pernah retak ini jika saya tidak menyadari bahwa kebalikannya adalah Mathbuilt-in . (lg=19979699+55686).toString(9+25)hanyalah cara berbelit-belit untuk kembali "expm1".

Produksi ETH
sumber
Bagus sekali! Ya saya sedang melihat fungsi pada Matematika untuk memutuskan apa yang akan digunakan, melihat expm1, dan berkata, "Tunggu, itu hal?"
SLuck49
2

J, 10 byte, mil

1%:@*~>:[<

Saya harus menulis sesuatu di sini karena jawabannya terlalu pendek.

GB
sumber
2

J, 29 byte, Zgarb

Asli

5#.[:,(3 5&#:(-$]-)7)#.inv"0]

Retak

[:(](07-5)"3 #.-:&#$,)5#.inv]

Cobalah online!

Setara retak lainnya adalah

[:((3 ]7-5)#.-:&#$,)5#.inv"0]

Penjelasan

[:(](07-5)"3 #.-:&#$,)5#.inv]  Input: integer n
                            ]  Get n
                      5        The constant 5
                       #.inv   Get the digits of n in base 5
[:(                  )         Operate on those digits D
                    ,            Flatten D (does nothing since it is already a list)
                  #              Get the length of D
               -:&               Halve it
                   $             Reshape D to half its length (only the base 2 digits)
    (07-5)"3                     The constant 2 with rank 3
             #.                  Convert the front-half of D to a decimal from base 2
   ]                             Return the right result
mil
sumber
Yap, itu berhasil! Ini sedikit berbeda dari solusi saya, tetapi ada banyak peluang. Logika dasarnya sama.
Zgarb