Visión general
En este desafío, se le darán dos números que son un pequeño desplazamiento mayor que un múltiplo de un número de tamaño mediano. Debe generar un número de tamaño mediano que sea casi un divisor de ambos números, excepto por un pequeño desplazamiento.
El tamaño de los números implicados se puede parametrizar por un parámetro de dificultad, l
. Su objetivo es resolver el problema lo más posible l
en menos de 1 minuto.
Preparar
En un problema dado, habrá un número secreto p
, que será un número de bit aleatorio l^2
( l*l
). Habrá dos multiplicadores, q1, q2
que serán l^3
números de bits aleatorios , y habrá dos desplazamientos r1, r2
, que serán l
números de bits aleatorios .
La entrada a su programa será x1, x2
, definida como:
x1 = p * q1 + r1
x2 = p * q2 + r2
Aquí hay un programa para generar casos de prueba, en 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)
La primera línea de salida es una posible solución, mientras que la segunda y tercera líneas son la entrada que se le dará a su programa.
Su programa
Teniendo en cuenta x1
, x2
y l
, usted debe encontrar un l^2
número de bits p'
de tal manera que x1 % p'
y x2 % p'
son ambos l
números de bits. p
siempre funcionará, aunque puede haber otras posibilidades. Aquí hay una función para verificar una solución:
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)
Ejemplo
Supongamos que l
es 3. El programa generador elige un número de 9 bits p
, que en este caso es 442
. El generador elige dos 3
números de bit para r1, r2
, que son 4, 7
. El generador elige dos 27
números de bit para q1, q2
, que son 117964803, 101808039
. Debido a estas opciones, x1, x2
son 52140442930, 44999153245
.
Su programa se daría 52140442930, 44999153245
como entrada, y debe generar un número de 9 bits (en el rango [256, 511]
) de modo que 52140442930
y el 44999153245
módulo ese número dé números de 3 bits (en el rango [4, 7]
). 442
es el único valor de este tipo en este caso, por lo que su programa tendría que salir 442
.
Más ejemplos
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
Puntuación
Como se mencionó anteriormente, el puntaje de su programa es el más alto l
que el programa completa en menos de 1 minuto. Más específicamente, su programa se ejecutará en 5 instancias aleatorias con eso l
, y debe generar una respuesta correcta en los 5, con un tiempo promedio inferior a 1 minuto. El puntaje de un programa será el más alto en el l
que tenga éxito. Tiebreaker será el tiempo promedio en eso l
.
Para darle una idea de a qué puntajes apuntar, escribí un solucionador de fuerza bruta muy simple. Obtuve un puntaje de 5. Escribí un solucionador mucho más elegante. Obtuvo una puntuación de 12 o 13, dependiendo de la suerte.
Detalles
Para una comparación perfecta entre las respuestas, programaré las presentaciones en mi computadora portátil para obtener puntajes canónicos. También ejecutaré las mismas instancias elegidas al azar en todas las presentaciones, para aliviar un poco la suerte. Mi computadora portátil tiene 4 CPU, CPU i5-4300U a 1.9 GHz, 7.5G de RAM.
Siéntase libre de publicar un puntaje provisional basado en su propio tiempo, solo deje en claro si es provisional o canónico.
¡Que gane el programa más rápido!
fuente
l^2
número de bit que estél
-bits lejos de ser un factor de ambos números funciona. Sin embargo, generalmente solo hay uno.Respuestas:
Óxido, L = 13
src/main.rs
Cargo.toml
Correr
fuente
Mathematica, L = 5
Aquí hay una solución rápida 5
Entrada
[x1, x2, L]
para que cualquiera pueda probar esto, aquí está el generador de claves
elija el valor L ejecutado, el código y obtendrá tres números.
coloca los dos últimos junto con L como entrada, y deberías obtener el primero
fuente
Mathematica, L = 12
entrada [x1, x2, L]
para que cualquiera pueda probar esto, aquí está el generador de claves
elige el valor L, ejecuta el código y obtendrás tres números.
coloca los dos últimos junto con L como entrada, y deberías obtener el primero
fuente
l = 12
, dio un resultado incorrecto. Específicamente, el divisor resultante fue un número de 146 bits, que es demasiado grande. Creo que solo necesitarás un pequeño cambio para arreglar esto.l^2
bits, pero también necesita verificar que tenga la mayoría de losl^2
bits.Python, L = 15, tiempo promedio 39.9s
Este código se basa en el hecho de que el producto de x1 - r para todos los valores posibles de r debe ser un múltiplo de p, y el producto de x2 - r también debe serlo. La mayor parte del tiempo se dedica a tomar el mcd de los dos productos, cada uno de los cuales tiene aproximadamente 60,000,000 bits. El mcd, que solo tiene alrededor de 250,000 bits, se compara con cada uno de los valores xr una vez más, para extraer los candidatos p '. Si son demasiado grandes, la división de prueba se usa para reducirlos al rango apropiado.
Esto se basa en la biblioteca gmpy2 para Python, que es un envoltorio delgado para la biblioteca GNU MP, que en particular tiene una rutina gcd realmente buena.
Este código es de un solo subproceso.
fuente