Überblick
In dieser Herausforderung erhalten Sie zwei Zahlen, die jeweils einen kleinen Versatz größer als ein Vielfaches einer mittelgroßen Zahl sind. Sie müssen eine mittelgroße Zahl ausgeben, die bis auf einen kleinen Versatz fast ein Teiler beider Zahlen ist.
Die Größe der beteiligten Zahlen wird durch einen Schwierigkeitsparameter parametrisiert l
. Ihr Ziel ist es, das Problem l
in weniger als 1 Minute so schnell wie möglich zu lösen .
Installieren
In einem gegebenen Problem wird es eine Geheimzahl geben p
, die eine zufällige l^2
( l*l
) Bitnummer ist. Es wird zwei Multiplikatoren geben, q1, q2
bei denen es sich um zufällige l^3
Bitnummern handelt, und es werden zwei Offsets geben, r1, r2
bei denen es sich um zufällige l
Bitnummern handelt.
Die Eingabe für Ihr Programm x1, x2
lautet wie folgt :
x1 = p * q1 + r1
x2 = p * q2 + r2
Hier ist ein Programm zum Generieren von Testfällen in 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)
Die erste Ausgabezeile ist eine mögliche Lösung, während die zweite und dritte Zeile die Eingabe sind, die Ihrem Programm gegeben wird.
Ihr Programm
Gegeben x1
, x2
und l
, müssen Sie eine l^2
Bitnummer finden, p'
so dass x1 % p'
und x2 % p'
beide l
Bitnummern sind. p
wird immer funktionieren, obwohl es andere Möglichkeiten geben kann. Hier ist eine Funktion zum Überprüfen einer Lösung:
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)
Beispiel
Angenommen, es l
ist 3. Das Generatorprogramm wählt eine 9-Bit-Zahl aus p
, in diesem Fall ist dies 442
. Der Generator wählt zwei 3
Bitnummern aus, für r1, r2
die 4, 7
. Der Generator wählt zwei 27
Bitnummern aus, für q1, q2
die 117964803, 101808039
. Wegen dieser Entscheidungen x1, x2
sind 52140442930, 44999153245
.
Ihr Programm würde 52140442930, 44999153245
als Eingabe angegeben und muss eine 9-Bit-Zahl (im Bereich [256, 511]
) ausgeben, sodass 52140442930
und 44999153245
modulo diese Zahl 3-Bit-Zahlen (im Bereich [4, 7]
) ergibt . 442
ist der einzige solche Wert in diesem Fall, so müsste Ihr Programm ausgeben 442
.
Mehr Beispiele
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
Wertung
Wie oben erwähnt, ist die Punktzahl Ihres Programms die höchste l
, die das Programm in weniger als 1 Minute abgeschlossen hat. Genauer gesagt, Ihr Programm wird mit 5 zufälligen Instanzen ausgeführt l
, und es muss eine korrekte Antwort auf alle 5 mit einer durchschnittlichen Zeit unter 1 Minute ausgeben. Die Punktzahl eines Programms ist die höchste l
, bei der es erfolgreich ist. Tiebreaker wird in dieser Zeit durchschnittlich sein l
.
Um Ihnen eine Vorstellung davon zu geben, welche Ergebnisse angestrebt werden sollen, habe ich einen sehr einfachen Brute-Force-Löser geschrieben. Es wurde mit 5 bewertet. Ich habe einen viel schickeren Löser geschrieben. Es hat eine Punktzahl von 12 oder 13, je nach Glück.
Einzelheiten
Um eine perfekte Vergleichbarkeit der Antworten zu gewährleisten, werde ich die Einsendungen auf meinem Laptop zeitlich festlegen, um kanonische Ergebnisse zu erhalten. Ich werde bei allen Einsendungen die gleichen zufällig ausgewählten Instanzen ausführen, um das Glück etwas zu lindern. Mein Laptop hat 4 CPUs, i5-4300U CPU bei 1,9 GHz, 7,5 G RAM.
Es steht Ihnen frei, eine vorläufige Punktzahl zu veröffentlichen, die auf Ihrem eigenen Timing basiert. Machen Sie einfach klar, ob es sich um eine vorläufige oder eine kanonische Punktzahl handelt.
Möge das schnellste Programm gewinnen!
quelle
l^2
Bit-Zahl, diel
kein Faktor für beide Zahlen ist, funktioniert. Normalerweise gibt es jedoch nur einen.Antworten:
Rost, L = 13
src/main.rs
Cargo.toml
Laufen
quelle
Mathematica, L = 5
Hier ist eine schnelle Lösung
Eingang
[x1, x2, L]
Damit das jeder testen kann, hier der Schlüsselgenerator
Wählen Sie den L-Wert, den Code und Sie erhalten drei Zahlen.
platziere die letzten beiden zusammen mit L als Eingabe, und du solltest die erste bekommen
quelle
Mathematica, L = 12
Eingang [x1, x2, L]
Damit das jeder testen kann, hier der Schlüsselgenerator
Wählen Sie den L-Wert, führen Sie den Code aus und Sie erhalten drei Zahlen.
platziere die letzten beiden zusammen mit L als Eingabe, und du solltest die erste bekommen
quelle
l = 12
, gab es ein falsches Ergebnis. Insbesondere war der resultierende Divisor eine 146-Bit-Zahl, die zu groß ist. Ich denke, Sie brauchen nur eine kleine Änderung, um dies zu beheben.l^2
Bits enthält, aber Sie müssen auch überprüfen, ob sie höchstensl^2
Bits enthält.Python, L = 15, durchschnittliche Zeit 39,9 s
Dieser Code basiert auf der Tatsache, dass das Produkt von x1 - r für alle möglichen Werte von r ein Vielfaches von p sein muss, und das Produkt von x2 - r muss es auch sein. Die meiste Zeit wird damit verbracht, den gcd der beiden Produkte zu nehmen, von denen jedes ungefähr 60.000.000 Bits hat. Die gcd, die nur ungefähr 250.000 Bits hat, wird dann noch einmal mit jedem der xr-Werte verglichen, um p'-Kandidaten zu extrahieren. Wenn sie etwas zu groß sind, werden sie mithilfe der Testdivision auf den entsprechenden Bereich reduziert.
Dies basiert auf der gmpy2-Bibliothek für Python, die ein dünner Wrapper für die GNU MP-Bibliothek ist, die insbesondere eine wirklich gute gcd-Routine hat.
Dieser Code ist Singlethread.
quelle