Gambaran
Dalam tantangan ini, Anda akan diberikan dua angka yang keduanya merupakan offset kecil yang lebih besar dari kelipatan angka berukuran sedang. Anda harus menampilkan nomor berukuran sedang yang hampir merupakan pembagi kedua angka, kecuali untuk offset kecil.
Ukuran angka yang terlibat akan diparameterisasi dengan parameter kesulitan l
,. Tujuan Anda adalah memecahkan masalah sebesar mungkin l
dalam waktu kurang dari 1 menit.
Mempersiapkan
Dalam masalah yang diberikan, akan ada nomor rahasia p
,, yang akan menjadi nomor bit acak l^2
( l*l
). Akan ada dua pengganda,, q1, q2
yang akan menjadi l^3
angka bit acak , dan akan ada dua offset r1, r2
,, yang akan menjadi l
angka bit acak .
Input untuk program Anda akan x1, x2
, didefinisikan sebagai:
x1 = p * q1 + r1
x2 = p * q2 + r2
Berikut adalah program untuk menghasilkan kasus uji, dengan Python:
from random import randrange
from sys import argv
l = int(argv[1])
def randbits(bits):
return randrange(2 ** (bits - 1), 2 ** bits)
p = randbits(l ** 2)
print(p)
for i in range(2):
q_i = randbits(l ** 3)
r_i = randbits(l)
print(q_i * p + r_i)
Baris pertama dari output adalah solusi yang memungkinkan, sedangkan baris kedua dan ketiga adalah input yang akan diberikan oleh program Anda.
Program Anda
Mengingat x1
, x2
dan l
, Anda harus menemukan l^2
sejumlah bit p'
sehingga x1 % p'
dan x2 % p'
keduanya l
nomor bit. p
akan selalu berfungsi, meskipun mungkin ada kemungkinan lain. Berikut fungsi untuk memverifikasi solusi:
def is_correct(x1, x2, l, p_prime):
p_prime_is_good = p_prime >> (l**2 - 1) and not p_prime >> l ** 2
x1_is_good = (x1 % p_prime) >> (l-1) and not (x1 % p_prime) >> l
x2_is_good = (x2 % p_prime) >> (l-1) and not (x2 % p_prime) >> l
return bool(p_prime_is_good and x1_is_good and x2_is_good)
Contoh
Misalkan l
adalah 3. Program generator memilih angka 9-bit p
, yang dalam hal ini adalah 442
. Generator memilih dua 3
angka bit r1, r2
, yaitu 4, 7
. Generator memilih dua 27
angka bit q1, q2
, yaitu 117964803, 101808039
. Karena pilihan-pilihan ini, x1, x2
adalah 52140442930, 44999153245
.
Program Anda akan diberikan 52140442930, 44999153245
sebagai input, dan harus menampilkan angka 9-bit (dalam kisaran [256, 511]
) sehingga 52140442930
dan 44999153245
modulo angka tersebut memberikan angka 3 bit (dalam kisaran [4, 7]
). 442
adalah satu-satunya nilai dalam kasus ini, jadi program Anda harus menampilkannya 442
.
Lebih banyak contoh
l = 2
x1 = 1894
x2 = 2060
p = 11
No other p'.
l = 3
x1 = 56007668599
x2 = 30611458895
p = 424
No other p'.
l = 6
x1 = 4365435975875889219149338064474396898067189178953471159903352227492495111071
x2 = 6466809655659049447127736275529851894657569985804963410176865782113074947167
p = 68101195620
I don't know whether there are other p'.
l = 12
x1 = 132503538560485423319724633262218262792296147003813662398252348727558616998821387759658729802732555377599590456096450977511271450086857949046098328487779612488702544062780731169071526325427862701033062986918854245283037892816922645703778218888876645148150396130125974518827547039720412359298502758101864465267219269598121846675000819173555118275197412936184329860639224312426860362491131729109976241526141192634523046343361089218776687819810873911761177080056675776644326080790638190845283447304699879671516831798277084926941086929776037986892223389603958335825223
x2 = 131643270083452525545713630444392174853686642378302602432151533578354175874660202842105881983788182087244225335788180044756143002547651778418104898394856368040582966040636443591550863800820890232349510212502022967044635049530630094703200089437589000344385691841539471759564428710508659169951391360884974854486267690231936418935298696990496810984630182864946252125857984234200409883080311780173125332191068011865349489020080749633049912518609380810021976861585063983190710264511339441915235691015858985314705640801109163008926275586193293353829677264797719957439635
p = 12920503469397123671484716106535636962543473
I don't know whether there are other p'.
l = 12
x1 = 202682323504122627687421150801262260096036559509855209647629958481910539332845439801686105377638207777951377858833355315514789392768449139095245989465034831121409966815913228535487871119596033570221780568122582453813989896850354963963579404589216380209702064994881800638095974725735826187029705991851861437712496046570494304535548139347915753682466465910703584162857986211423274841044480134909827293577782500978784365107166584993093904666548341384683749686200216537120741867400554787359905811760833689989323176213658734291045194879271258061845641982134589988950037
x2 = 181061672413088057213056735163589264228345385049856782741314216892873615377401934633944987733964053303318802550909800629914413353049208324641813340834741135897326747139541660984388998099026320957569795775586586220775707569049815466134899066365036389427046307790466751981020951925232623622327618223732816807936229082125018442471614910956092251885124883253591153056364654734271407552319665257904066307163047533658914884519547950787163679609742158608089946055315496165960274610016198230291033540306847172592039765417365770579502834927831791804602945514484791644440788
p = 21705376375228755718179424140760701489963164
Mencetak gol
Seperti disebutkan di atas, skor program Anda adalah yang tertinggi l
yang diselesaikan oleh program dalam waktu kurang dari 1 menit. Lebih khusus lagi, program Anda akan dijalankan pada 5 kejadian acak dengan itu l
, dan itu harus menghasilkan jawaban yang benar pada semua 5, dengan waktu rata-rata di bawah 1 menit. Skor suatu program akan menjadi yang tertinggi l
yang berhasil. Tiebreaker akan menjadi waktu rata-rata untuk itu l
.
Untuk memberi Anda gambaran tentang skor apa yang ingin Anda tuju, saya menulis sebuah solusi brute-force yang sangat sederhana. Itu mendapat skor 5. Saya menulis pemecah jauh lebih mewah. Itu mendapat skor 12 atau 13, tergantung keberuntungan.
Detail
Untuk komparabilitas sempurna di seluruh jawaban, saya akan mengatur waktu pengiriman pada laptop saya untuk memberikan skor kanonik. Saya juga akan menjalankan contoh yang dipilih secara acak yang sama pada semua pengiriman, untuk mengurangi keberuntungan. Laptop saya memiliki 4 CPU, CPU i5-4300U @ 1.9 GHz, RAM 7.5G.
Jangan ragu untuk memposting skor sementara berdasarkan waktu Anda sendiri, cukup jelaskan apakah itu sementara atau kanonik.
Semoga program tercepat menang!
sumber
l^2
nomor bit yangl
-bits jauh dari menjadi faktor kedua angka berfungsi. Namun biasanya hanya ada satu.Jawaban:
Rust, L = 13
src/main.rs
Cargo.toml
Untuk berlari
sumber
Mathematica, L = 5
di sini adalah 5 solusi cepat
Input
[x1, x2, L]
agar siapa pun dapat menguji ini, ini adalah generator kunci
pilih menjalankan nilai L, kode dan Anda akan mendapatkan tiga angka.
tempatkan dua yang terakhir bersama dengan L sebagai input, dan Anda harus mendapatkan yang pertama
sumber
Mathematica, L = 12
masukan [x1, x2, L]
agar siapa pun dapat menguji ini, ini adalah generator kunci
pilih nilai L, jalankan kodenya dan Anda akan mendapatkan tiga angka.
tempatkan dua yang terakhir bersama dengan L sebagai input, dan Anda harus mendapatkan yang pertama
sumber
l = 12
, itu memberikan hasil yang salah. Secara khusus, pembagi yang dihasilkan adalah angka 146-bit, yang terlalu besar. Saya pikir Anda hanya perlu sedikit perubahan untuk memperbaikinya.l^2
bit, tetapi Anda juga perlu memeriksa bahwa ia memiliki paling banyakl^2
bit.Python, L = 15, waktu rata-rata 39.9s
Kode ini didasarkan pada fakta bahwa produk x1 - r untuk semua nilai yang mungkin dari r harus kelipatan p, dan produk dari x2 - r juga harus. Sebagian besar waktu dihabiskan untuk mengambil gcd dari dua produk, yang masing-masing memiliki sekitar 60.000.000 bit. Gcd, yang hanya memiliki sekitar 250.000 bit, kemudian dibandingkan dengan masing-masing nilai xr sekali lagi, untuk mengekstrak kandidat p '. Jika mereka agak terlalu besar, pembagian percobaan digunakan untuk menguranginya ke kisaran yang sesuai.
Ini didasarkan pada pustaka gmpy2 untuk Python, yang merupakan pembungkus tipis untuk pustaka GNU MP, yang secara khusus memiliki rutin gcd yang sangat bagus.
Kode ini adalah utas tunggal.
sumber