Inversiones ocultas (Hilo de ladrones)

16

Este es un rompecabezas de , el hilo de la policía se puede encontrar aquí.

Su tarea será encontrar un anagrama de los programas proporcionados en el hilo de la policía que realiza su inverso izquierdo.

Una vez que descifre una respuesta, publique la solución como respuesta a continuación y notifique al respondedor original.

Te calificarán en la cantidad de programas que seas el primero en descifrar.

Post Rock Garf Hunter
fuente

Respuestas:

21

Python 3, 46 bytes, Lynn

lambda x0223334566789:(x0223334566789*89)//178
GB
fuente
¿Cómo "notifico al respondedor original"?
GB
Dejó un comentario que vincula su respuesta en el original
Sefa
Debería soltarlo f=al comienzo de su código ya que no es necesario y no forma parte de la función original
0
Hecho, acabo de copiarlo y pegarlo demasiado rápido.
GB
16
Aquí estoy, en realidad, forzando una solución bruta (¡e incluso suponiendo que exista una) y usted simplemente evita todo el problema! +1
orlp
14

Python 2, 225 bytes, orlp

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

Supongo que tuve suerte después de adivinar divisores primos aleatorios todo el día ...

(El límite de punto de c4.8xlarge predeterminado es 4, pero pude subirlo a 10 el año pasado. Aunque tuve que ajustar la configuración de FAAS de 16 esclavos a 6 (+3 mpi, 1 maestro). 20m polyselect, 12h 50m tamizado, 2h 25m linalg, 30m sqrt. Costo total ~ $ 70. Al menos @orlp fue lo suficientemente agradable como para elegir un tamaño solucionable, ¡pero no lo volveré a hacer! Gracias a @IlmariKaronen por el último paso, y sí, estoy bromeando sobre el adivinando: P)

Sp3000
fuente
Yo ... qué ... Ahora me siento mal por costarle dinero :( Elegí intencionalmente un tamaño que todavía sería razonablemente pequeño pero demasiado alto para atacar. En realidad, no pensé que alguien gastaría dinero en esto.
orlp
1
@orlp Vale la pena como una experiencia única para mí. Espero que la gente aprenda algo sobre la seguridad RSA de 512 bits en la naturaleza de esto :)
Sp3000
Esta es una verdadera dedicación al golf, ¡gastando no solo tiempo sino dinero! Es interesante observar que un atacante podría romper RSA de 512 bits de forma gratuita a través de pruebas de servicio de cómputo en la nube.
millas
@miles Debo mencionar que AWS tiene crédito para los estudiantes si alguien quiere intentarlo, y no me sorprendería que otros servicios hicieran lo mismo. Por lo tanto, probablemente no estés lejos con esa idea de ensayos, al menos por primera vez. (Si alguien quiere intentarlo, asegúrese de eliminar todos los volúmenes, AMI, etc. una vez que haya terminado porque de lo contrario se le cobrará por el almacenamiento)
Sp3000
11

Python 2, 83 bytes, orlp

Original:

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

Grieta:

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

Pruébalo en línea!

Craqueo de RSA realizado por Wolfram Alpha . ;)

Ilmari Karonen
fuente
Me acabo de dar cuenta de que ~p*~qes más corto que -~p*-~q, vaya.
orlp
Sin embargo, ¿cómo hiciste la ingeniería inversa de la (p*q-2*(p+q))/4pieza? :)
orlp
Esa fue la parte más complicada, ¿no? Básicamente, el conocimiento de la función de Carmichael y el hecho de que p/2y q/2eran ambos primos impares, y un montón de prueba y error para encontrar algo que funcione utilizando los caracteres disponibles.
Ilmari Karonen
Elegí intencionalmente py q(los reales, el que está en el código son p-1y q-1para fines de golf) tal que (p-1)/2sea ​​primordial para que tengamos φ(φ(pq)) = ((p-1)/2-1)((q-1)/2-1). Esto nos permite calcular el inverso modular de 65537mod φ(pq)(lo que necesitamos para RSA) usando la identidad de Euler, haciendo la respuesta mucho más corta porque no necesitamos implementar lógica inversa modular o codificar otra constante grande. Aparte de -~q*-~p-> ~q*~p, encontraste exactamente mi función :)
orlp
1
En realidad, para elegir una liendre menor, creo que φ(φ(pq)) = 2((p-1)/2-1)((q-1)/2-1)para los primos seguros py q, porque φ(4) = 2. Pero λ(φ(pq)) = lcm(2, (p-1)/2-1, (q-1)/2-1)es a lo sumo ((p-1)/2-1)((q-1)/2-1)/2, y cualquier múltiplo de eso, menos uno, servirá para el exponente. :)
Ilmari Karonen
7

Python 3, 80 bytes, Wolfram

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

¡Esto fue realmente difícil de descifrar! Yo uso la biblioteca de bisectos , que se incluye en la distribución Python 3. La bisectfunción toma una lista ordenada y un elemento, y devuelve el índice más a la derecha donde el elemento podría insertarse para mantener el orden. Simplemente le damos la qlista de cuadrados a partir de 1y el elemento q.

Zgarb
fuente
1
Iba a sugerir cambiar (h+1)a -~h. Entonces me di cuenta de que ese no es el objetivo de este desafío: P
ETHproductions
@ETHproductions Eso sería incorrecto de todos modos debido a la precedencia del operador.
Sp3000
@ Sp3000 Huh, no tenía idea de que **tiene mayor prioridad que ~en Python. Supongo que es mejor que en JS, donde -~2**2arroja un error de sintaxis ("la expresión unaria no sintetizada no puede aparecer en el lado izquierdo de '**'").
ETHproductions
@ETHproductions En realidad lo hicieron para evitar ambigüedades, lo cual, como podría agregar, es muy poco característico de la mayoría de los diseños de JS.
Esolanging fruta
@ Challenger5 En realidad, tendría que estar en desacuerdo con usted allí: en los últimos años TC39 ha sido extremadamente cuidadoso para asegurarse de que las nuevas funciones agregadas estén tan libres de ambigüedades como sea posible (que incluye el **operador, agregado en ES2017)
ETHproductions
6

Javascript, 21 bytes, Arnauld

Original

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

Grieta

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

Devuelve la raíz cúbica.

Emigna
fuente
Ahí tienes! ;)
Arnauld
@Arnauld: Me parece un poco extraño que JS le permita llamar a funciones con más argumentos de los que están definidos. Me pregunto cuál es el pensamiento detrás de eso.
Emigna
66
Tienes razón, JS lo permite por diseño. Sin embargo, los argumentos adicionales no se pierden por completo, ya que se almacenan en el objeto de argumentos al que puede acceder manualmente la función.
Arnauld
5

7, 9 bytes, ais523

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

¡Porque la fuerza bruta siempre gana, y 9! es solo 362880

GB
fuente
4

Processing.js, 59 bytes, Kritixi Lithos

Original:

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

Grieta:

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

Bueno, eso fue bastante fácil. La parte más difícil fue averiguar dónde colocar las comas y los asteriscos adicionales. Afortunadamente, parece que Processing permite parámetros de funciones adicionales no utilizados, así como expresiones de coma de estilo C.

Ilmari Karonen
fuente
1
Aparentemente, el intérprete que relacioné estaba equivocado. De hecho, la mayoría (o incluso todos) los intérpretes en línea probablemente estarán equivocados ya que Processing-java se precompila a Processing.js. En este momento, creo que el mejor curso de acción sería que usted y yo cambiemos nuestras respuestas a "Processing.js" en lugar de Processing porque entonces su respuesta sería válida (Processing-java da toneladas de errores). Publicaré una respuesta por separado con el mismo código que Processing-java, pero para esto el intérprete de nidos sería instalarlo desde processing.org. Bien hecho de todos modos!
Kritixi Lithos
4

JavaScript (ES6), 63 bytes, SLuck49

Original:

x=>eval(atob`eCp4KzEvLyAgfXBModLS4TvEn4wp1iys9YRRKC85KLIhNMC=`)

Grieta:

x=>eval(atob`CgpNYXRoLnBvdyh4LTEsMC41KSAvLw4589CEIKKMRefipyz=`)

El código base64 anterior se decodifica para:



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

donde el ... representa un montón de basura aleatoria que es ignorada por el intérprete JS, ya que está en un comentario.

Encontré esta solución por prueba y error. Al final, la única parte realmente difícil fueron las dos nuevas líneas al principio del código, necesarios para hacer la línea resto correctamente y para conseguir la Men Matha base 64 a codificar en algo que estaba disponible en el juego de caracteres originales. Primero probé espacios, pero " M"codifica en base64 "ICBN"y necesitaba el único disponible Bpara codificar ".po"más adelante en el código. "0+M", "1*M", "1?M"O cualquier otro prefijos no-op similares que podría pensar en no funcionó bien, pero los saltos de línea hicieron.

Sospecho que esto puede no ser exactamente la solución prevista, pero lo que sea, funciona. :)

Manifestación:

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
fuente
Un buen trabajo para encontrar algo que funcionara, esperaba poner los caracteres adicionales al comienzo haría esto un poco más difícil
SLuck49
Impresionante :) Tomé exactamente el mismo enfoque pero no pensé en probar nueva línea. Estaba tratando de perder una C en otro lugar pero no estaba llegando a ninguna parte.
Chris M
3

Brain-Flak, 26 bytes, asistente de trigo

Original (agrega 13)

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

Grieta (resta 13)

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

J, 8 bytes, millas

[:]-:[+:

Intercambio simple de +:for -:(doble por la mitad).

Conor O'Brien
fuente
También puede cambiar los verbos izquierdo y derecho: [:[+:]-:.
randomra
3

Python 2, 47 bytes, asistente de trigo

lambda x:sorted(a**2for a in range(x)).index(x)
nmjcman101
fuente
¡Buen trabajo! Encontraste la solución exacta que tenía en mente
Post Rock Garf Hunter
3

JavaScript (ES6), 46 bytes, SLuck49

Original (calcula ln (x + 1))

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

Grieta

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

Nunca habría resuelto esto si no me hubiera dado cuenta de que el inverso es un elemento Mathincorporado . (lg=19979699+55686).toString(9+25)es solo una forma complicada de regresar "expm1".

ETHproducciones
fuente
¡Bien hecho! Sí, estaba mirando las funciones de Matemáticas para decidir qué usar, vi expm1y dije "Espera, ¿eso es una cosa?"
SLuck49
2

J, 10 bytes, millas

1%:@*~>:[<

Tengo que escribir algo aquí porque la respuesta es demasiado corta.

GB
fuente
2

J, 29 bytes, Zgarb

Original

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

Grieta

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

Pruébalo en línea!

Otro equivalente de crack es

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

Explicación

[:(](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
millas
fuente
Sí, eso funciona! Es un poco diferente de mi solución, pero hay mucho margen de maniobra. Sin embargo, la lógica básica es la misma.
Zgarb