Cops and Robbers: Redacted Primality (Räuberfaden)

9

Dies ist der Faden der Räuber. Der Thread der Polizei ist hier .

Ihre Herausforderung besteht darin, eine ungerissene Einsendung aus dem Thread der Polizei zu nehmen und zu versuchen, das ursprüngliche unredaktierte Programm zu finden. Bitte kommentieren Sie die Einreichung des Polizisten, wenn Sie seinen Code geknackt haben.

MD XF
quelle

Antworten:

6

Brainfuck , Jo King

>>>>>+>,[>++++++[-<-------->]<+>,]<[-[█<█<]++++++++++<]>[-]>>██[>█>>█>]+[<]<<[<]>█<<+>>[>]█>[>]█+[<]<<[<]>-█>]>>[->]<[-[[<]<]++++++++++<]>[-]>[<█]>]>[>]<[[█]<]<<<<<[<]<<██>>[>]<█[->+<]<█>>[>]<[-[[<]<]++++++++++<]>███>[<<]>[[[>]>████[<]<[-[[<]<]++++++++++<]>[-]>[█<]>]>[>]<[[-]>+[>]<-<[<]<]+<<<<<[<]>[[>]+[[>]>]>[>]>[-<+>]<[<]<[>+[<]>>-<<<<<[[<]<]>>███████>[[█]>]<]<[[<]<]<[█]>]>>>[[>]<->>]]>[[>]>]<<[[[█]<]<]<<<[█]<<█>>>[>]█[-[[<]<]++++++++++<]>>[[>]+[------->++<]>.+.+++++.[---->+<]>+++.>>]>[>]+[------->++<]>++.++.---------.++++.--------.
>>>>>+>,[>++++++[-<-------->]<+>,]<[-[[<]<]++++++++++<]>[-]>>[[[>]>>[>]+[<]<<[<]>[<<+>>[>]>>[>]<+[<]<<[<]>-]>]>>[->]<[-[[<]<]++++++++++<]>[-]>[<<]>]>[>]<[[-]<]<<<<<[<]<<[>>>[>]<[[->+<]<]>>[>]<[-[[<]<]++++++++++<]>[-]>[<<]>[[[>]>[>]+[<]<[-[[<]<]++++++++++<]>[-]>[<<]>]>[>]<[[-]>+[>]<-<[<]<]+<<<<<[<]>[[>]+[[>]>]>[>]>[-<+>]<[<]<[>+[<]>>-<<<<<[[<]<]>>[[-]+>]>[[>]>]<]<[[<]<]<[<]>]>>>[[>]<->>]]>[[>]>]<<[[[-]<]<]<<<[<]<<]>>>[>]<[-[[<]<]++++++++++<]>>[[>]+[------->++<]>.+.+++++.[---->+<]>+++.>>]>[>]+[------->++<]>++.++.---------.++++.--------.

Probieren Sie es online aus!

Dies implementiert das Sieb von Eratosthenes.

Der Anfang gibt >>>>>+>,[>++++++[-<-------->]<+>,]jede Ziffer als Zeichencode ein und subtrahiert 47, um sie in den Bereich von 1 bis 10 zu bringen. Dies ermöglicht einen Zellenwert von 0, um den Abstand zwischen Zahlen anzuzeigen. Am +>Anfang dieses Abschnitts wird die Zahl auf mindestens zwei Ziffern festgelegt, was in Kürze wichtig sein wird.

Als nächstes und eines der ersten Dinge, die ich herausgefunden habe, ist der Abschnitt <[-[[<]<]++++++++++<]>[-]>. Dies erscheint mehrmals im Code, jedes mit unterschiedlichen Redaktionsmustern, aber es war nicht schwer zu erraten, dass alle diese Instanzen wahrscheinlich der gleiche Code waren. Dieser Code erfordert drei Nullen links von der Dezimalzahl auf dem Band, und seine Wirkung besteht darin, die Zahl zu dekrementieren. Die letzte Iteration der Schleife setzt den Wert 10 zwei Zellen links von der Zahl, aber die [-]bereinigt ihn.

Wenn die Dezimalzahl 0 war, wird keine fremde 10 erstellt, und die durch Null gesetzte Zelle [-]ist die höchstwertige Ziffer. Der Bandkopf befindet sich dann an der zweithöchsten Stelle (weshalb mindestens zwei Stellen erforderlich sind). Auf die meisten Instanzen dieses Snippets folgt sofort [<<]>, wodurch der Kopf unter normalen Bedingungen auf eine Zelle ungleich Null und eine Nullzelle gelegt wird, wenn die ursprüngliche Dezimalzahl Null war. Es scheint, dass in diesem Programm die Dezimaldarstellung von n-1verwendet wird, um zu bezeichnen n, so dass das Dekrementieren auf 0gefangen wird, anstatt auf dekrementiert zu werden -1.

Der nächste Teil schreibt die Zahlen von n-1 (n) bis 0 (1) auf das Band:

>[                      until the number reaches zero:
  [                     for each digit:
    [>]>>[>]+[<]<<[<]>  create a placeholder for the next copy
    [                   while the original value of the digit is nonzero:
      <<+               add 1 to copy two cells left (to keep one copy)
      >>[>]>>[>]<+      go to new copy and increment that cell
      [<]<<[<]>-        go back to original digit and decrement
    ]                   (this is effectively the same as [<+>>+<-] but with the cells at variable locations)
  >]                    next digit
  >>[->]                cancel the placeholder 1s that were used for the new copy
  <[-[[<]<]++++++++++<]>[-]>[<<]> decrement
]
>[>]<[[-]<]      clean up the trash 10s on the tape while ending at a known location relative to the last number

Diese Zahlen befinden sich nun alle auf dem Band, wobei zwei Nullzellen sie trennen. <<<<<[<]<<bringt uns in die letzte Zelle der vorletzten Nummer auf dem Band, wo wir uns in jeder Iteration der Schleife befinden werden. Die Schleife wird beendet, wenn alle Nummern außer dem Original verarbeitet wurden.

Zu Beginn der Schleife verschieben wir die aktuelle Nummer (die letzte noch auf dem Band) um eine Zelle nach rechts, um Platz zum Dekrementieren zu haben, und fahren dann fort und dekrementieren:

[>>>[>]<[[->+<]<]>>[>]<[-[[<]<]++++++++++<]>[-]>[<<]>

Wenn dieses Dekrement nicht unterlaufen ist, konvertieren wir die Zahl in unär:

[[[>]>[>]+[<]<[-[[<]<]++++++++++<]>[-]>[<<]>]

Beachten Sie, dass dieser Ausschnitt eine nicht geschlossene hat [. Infolgedessen wird der Rest dieser Schleife übersprungen, wenn die Zahl 0 war (was 1 darstellt). Nach der Konvertierung in unary räumen wir die verbleibenden 10s aus und ziehen die unary-Darstellung mit nach links:

>[>]<[[-]>+[>]<-<[<]<]+

Ich habe es bis jetzt nicht bemerkt, aber das +am Ende dieses Snippets ist durch eine einzelne 0 von der unären Darstellung getrennt. Es ist auch ein Teil der unären Darstellung: Die Sequenz 1011...11wird 0 mod k darstellen. Das Folgende <<<<<[<]>bringt uns an den Anfang der Zahl k+1und startet eine neue Schleife.

Die innere Schleife "markiert" hier jede Zahl auf dem Band mit einer 1 in der Zelle unmittelbar rechts und verwendet die unäre Darstellung als Uhr, um zu bestimmen, welche Zahlen Vielfache von sind k.

[
  [>]+             mark the current decimal number
  [[>]>]           move to end of decimal part of tape
  >[>]             move to 0 in middle of unary "clock"
  >[-<+>]          move the following 1 to the left if possible
  <[<]<            if a 1 was moved this will bring us back to a zero before the start of this "clock";
                   otherwise the looped move command doesn't move us at all and we are at the final 1
  [                if there was no gap (happens every kth iteration):
    >+[<]>>-       reset to original position
    <<<<<[[<]<]>>  go to number that was just marked
    [[-]+>]        replace digits with 0s (cell value 1)
    >[[>]>]<       go back to where we would be without this conditional
  ]
  <[[<]<]<[<]>     return to first unmarked number
]

Das [[-]+>]in diesem Abschnitt war der letzte Teil, den ich herausgefunden habe. Vorher nahm ich an, dass das Programm nur Testabteilungen durchführte, aber ich konnte nicht sehen, wo das Ergebnis verwendet wurde.

Diese Schleife beendet zwei Zellen links von der ganz linken Zahl, >>>[[>]<->>]]entfernt die auf dem Band platzierten Markierungen und bringt uns wieder zum Ende des Bandes. Danach >[[>]>]<<[[[-]<]<]wird entweder die unäre Uhr oder, wenn dieses gesamte Segment übersprungen wurde, die übrig gebliebenen 10s entfernt. Die Schleife wird mit auf ihren Startzustand gesetzt <<<[<]<<].

Danach wird nur noch gelesen, ob die eingegebene Nummer zu irgendeinem Zeitpunkt durch 1 ersetzt wurde:

>>>[>]<[-[[<]<]++++++++++<]>>                      do the check
[[>]+[------->++<]>.+.+++++.[---->+<]>+++.>>]      conditionally print "not "
>[>]+[------->++<]>++.++.---------.++++.--------.  unconditionally print "prime"

Glücklicherweise wurde die tatsächliche Ausgabe überhaupt nicht redigiert.

Nitrodon
quelle
"Die Nacht ist lang und findet nie den Tag." Ist es heute Nacht noch? : P
Stewie Griffin
@StewieGriffin Ich konnte es in dieser Nacht nicht tun, und dann fiel es mir einfach ein. Danke für die Erinnerung.
Nitrodon
Ich glaube nicht, dass ich meinen eigenen Code so gut hätte erklären können wie Sie hier. Sehr gute Arbeit.
Jo King
5

Wolfram-Sprache (Mathematica)

Knackt diese Antwort .

f[x_]:=(p=ToString@Boole@PrimeQ@x;StringMatchQ[p&@@Infinity,RegularExpression@"(\
\n{}\b+, )?1"])

Probieren Sie es online aus!

user202729
quelle
Kein Scrollen erforderlich, um den Code zu lesen :)
user202729
Nett! Ganz anders als die beabsichtigte Lösung, deshalb werde ich das noch nicht verraten.
Pavel
@Pavel Was ist damit ? Oder immer noch "grundsätzlich gleich"?
user202729
Hier ist ein Hinweis: Dieser große Blob enthält weder Boolenicht noch PrimeQ.
Pavel
5

Brain-Flak, MegaTom

(({████){██[████)█>(({}))<>}<>{}███{}((██({}))█████{}]██)({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{})██[██()██(()█[()]██{}██}{}<>{})
(({})<>){([[]]{})<>(({}))<>}<>{}{}{{}(([]({}))[({}[{}])])({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{})}([][()])((){[()](<{}>)}{}<>{})

Probieren Sie es online aus!

Dieses Programm führt Versuchsunterteilungen von n-2 bis 1 durch und gibt dann nur dann 1 aus, wenn dies mit dem Faktor 1 endet.

Nitrodon
quelle
4

8086 DOS COM von Joshua

xxd Darstellung aufgrund von Codierungen und Null-Bytes und anderen beängstigenden Dingen:

00000000: 31c0 b90a 0031 dbbe 8100 ac3c 0d74 3c3c  1....1.....<.t<<
00000010: 2075 f7ac 3c0d 7410 2c30 7c2f 3c09 7f2b   u..<.t.,0|/<..+
00000020: 93f7 e193 01c3 ebeb 83fb 027c 19c6 0653  ...........|...S
00000030: 0159 b902 0039 d974 1289 d831 d2f7 f109  .Y...9.t...1....
00000040: d274 0341 ebef c606 5301 4eb4 09ba 5301  .t.A....S.N...S.
00000050: cd21 c341 0d0a 24                        .!.A..$

Zuerst den Cop manuell zerlegen, dann mit yasm zusammenbauen. Einige Bytes wurden durch den verwendeten Konverter Joshua beschädigt, aber ich habe sie nur wie redigierte Bytes behandelt. Ich bin mir zu 99,72% sicher über ihren tatsächlichen Inhalt. Es sollte jedoch nicht lange dauern, bis das Problem behoben ist, wenn ich falsch liege. Genießen:

; A COM file is just a 16-bit flat binary
; loaded at 0x100 in some segment by DOS

org 0x100
bits 16

; Unsurprisingly, we start by converting
; the commandline string to a number. During
; the conversion, SI is a pointer to the
; string, CX is the base, and BX holds the
; partial result
parse_input:
; We'll read the input character by character
; into AL, but we need the resulting digit as
; a 16-bit number. Therefore, initialise AX to
; zero.
    xor ax, ax
    mov cx, 10
    xor bx, bx
; When a DOS program is loaded, it's preceded
; in memory by the Program Segment Prefix,
; which holds the commandline arguments at
; offset 0x81, terminated by a carriage return
    mov si, 0x81

.skip_prog_name:
; Load a character and move the pointer
    lodsb
; If we find the terminator here, the program
; was not given any arguments.
    cmp al, 13
    je finish

    cmp al, ' '
    jne .skip_prog_name

.input_loop:
    lodsb
    cmp al, 13
    je got_input

; If the ASCII value of the character is less
; than the one of '0', error out. Adjust the
; value in AL so that it holds the digit
; itself. This exploits the fact that the
; comparison instruction is just a subtraction
; that throws away the actual result.
    sub al, '0'
    jl finish

; If we have a value larger than 9, this
; character wasn't a digit.
    cmp al, 9
    jg finish

; Multiply the intermediate result by 10 and
; add the new digit to it.

    xchg ax, bx
    mul cx
    xchg ax, bx
    add bx, ax
    jmp .input_loop

got_input:
; The loop below would go haywire when given a
; zero or a one, so make them a special case.
    cmp bx, 2
    jl composite

; Patch the output string to say that it's
; prime
    mov byte[outstr], 'Y'

; BX = number being checked
; CX = loop counter, potential divisor of BX
    mov cx, 2

.loop:
; If CX = BX, we looked everywhere and couldn't
; find a divisor, therefore the number is prime
    cmp cx, bx
    je finish

; DIV takes DX:AX as a 32-bit number for the
; dividend. We don't want nor need the extra
; precision, so we set DX to 0.
    mov ax, bx
    xor dx, dx
    div cx

; DX now contains the remainder. To check if
; it's 0, we perform some noop operation, that
; happens to set the flags appropriately. AND
; and OR are commonly used for this purpose.
; Because of what's presumably a bug in the
; encoder used by Joshua, I do not yet know
; which for certain. However, I can make an
; educated guess. All other instances of the
; bug happened with a codepoint below 32.
; Moreover, no other bytes from that range
; occur in the code. Because an AND would be
; encoded as an exclamation mark, while OR -
; - as a tab, I am highly confident that Joshua
; used an OR.
    or dx, dx
    jz composite

; Increment the counter and loop again!
    inc cx
    jmp .loop

composite:
    mov byte[outstr], 'N'

finish:
    mov ah, 9
    mov dx, outstr
    int 0x21
    ret

outstr:
    db 'A', 13, 10, '$'
NieDzejkob
quelle
Der einzige Unterschied zwischen mir war bx < 2, dass er eher fertig als zusammengesetzt war. Zu Ihrer Information, die Beschädigung war darauf zurückzuführen, dass ursprünglich X als Maskenzeichen verwendet wurde und beim Umschalten auf █ nicht alles richtig repariert wurde.
Joshua
@Joshua Ich habe dort zuerst auch Finish verwendet, aber dann habe ich mich daran erinnert, dass die richtige Behandlung von 1 erforderlich ist. Über die Korruption - das ist eines der Szenarien, die ich mir vorgestellt habe
NieDzejkob
3

Gelee

Knackt diese Antwort.

25██26█966836897364918299█0█1█65849159233270█02█837903312854349029387313█ị██v
250126,9668368973649182994001,658491592332700020837903312854349029387313ṖịØJv

Probieren Sie es online aus!


Erläuterung:

Mit Blick auf und v, ich glaube , eine Liste von Zahlen zu bauen, ndex es in eine Liste und auswerten.

Die "triviale" Art, die Primalität in Jelly zu überprüfen, ist ÆP, also (wenn es die Einreichung knacken kann):

  • Die zu indizierende Liste muss Æund enthalten P.
  • Die Liste der Indizes müssen kongruent modulo sein 256mit [14, 81].

Also ... die Liste am Anfang des Programms stimmt mit [14, 81, 49]Mod 256 ( TIO ) überein und zeigt das letzte Element an.

user202729
quelle
3

sh + coreutils

Knackt diese Antwort .

eecs c "██████WyAkKHNoIC1jICJg█WNobyBabUZqZEc5eWZIUnlJQ2█2SnlBblhHNG5m██JoYVd3Z0t6SjhkMk1nTFhjSyB8YmFzZTY0IC1kYCIpIC1lcSAxIF0K█b█se6███d`"
exec sh -c "`echo WyAkKHNoIC1jICJgZWNobyBabUZqZEc5eWZIUnlJQ2M2SnlBblhHNG5mSFJoYVd3Z0t6SjhkMk1nTFhjSyB8YmFzZTY0IC1kYCIpIC1lcSAxIF0K|base64 -d`"

Nein Probieren Sie es online aus! diesmal wegen einiger Probleme . Sie können jedoch jdoodle verwenden .

Rückgabe per Exit-Code. 0(Erfolg) für Prime, 1(Fehler) für Composite.

Der tatsächlich ausgeführte Befehl ist

factor|tr ':' '\n'|tail +2|wc -w

Wie man knackt

  1. Schauen Sie sich den Code an und erkennen Sie Base64.
  2. Erfahren Sie, wie Sie base64Befehle verwenden.
  3. Wisse, dass dies +ein gültiges base64-Zeichen ist.
  4. Versuche zu dekodieren .
  5. Wenden Sie den Wrapper sh -c "`echo ...|base64 -d`"wieder auf das ursprüngliche Programm an .
  6. Generieren Sie verschachtelte base64 aus Befehlen .
user202729
quelle
Richtige Methode. "Einige Probleme" sind nicht alle Maschinen bekannt tail +n. Als ich Ihren Riss an der Maschine bei der Arbeit ausprobierte, beschwerte sie sich darüber. Sie haben den richtigen Code entlarvt, also ... :(
Joshua
3

Oktave , 86 Bytes, Stewie Griffin .

@(x)eval([(str2num(cell2mat([cellstr(reshape('0█1███1█0█0█00',████))])')'█')','(x)'])
@(x)eval([(str2num(cell2mat([cellstr(reshape('04141113040800',2,[]))])')+'e')','(x)'])

Probieren Sie es online aus!

Das hat Spaß gemacht! Ich hatte ein paar gute Tage damit zu kämpfen.

Der erste Hinweis bestand darin eval([...,'(x)']), eine Konstruktion zu erkennen, die einen Aufruf der isprimeFunktion als Verkettung des Arrays erstellt intsund dieses charimplizit in konvertiert char, sodass das Array ...entweder isprimeoder ein Array mit den ASCII-Werten von isprime, [105, 115, 112, 114, 105, 109, 101].

Der Rest war nur das Durchsuchen der Dokumentation, um herauszufinden, dass reshapeeine unbekannte Dimension verwendet werden kann [], obwohl ich wahrscheinlich reshape(...,2, 7)mit der gleichen Byteanzahl hätte arbeiten können.

Die Verwendung von +'e'(101) anstelle von +'d'(100) war eine nette Geste, die mich noch einige Minuten lang beschäftigte, bis ich bemerkte, dass die letzten Ziffern (unverhüllt) 00eher als waren 01, und damit war es einfach.

Giuseppe
quelle
2

JavaScript

x=>{if(x<4)return(!0);for(y=x>>>Math.log10(p=████;--y-1;(p=x/y%1)████if(██&&(███))break████return(███)}
x=>{if(x<4)return(!0);for(y=x>>>Math.log10(p=2-1);--y-1;(p=x/y%1)){;;if(!p&&(1<2))break;;;}return(!!p)}

Probieren Sie es online aus!

Ich bezweifle irgendwie, dass Sie genau das im Sinn hatten, aber es funktioniert.

MegaTom
quelle
2

> <> , Esolanging Obst

:1@v>~~:?1n;█$-1<█?=2:}*{█@:$@:

zu

:1@v>~~:?1n;
$-1</?=2:}*{%@:$@:

Probieren Sie es online aus!

Der kluge Umgang mit dem Redigieren einer Newline verwirrte mich ein wenig. Scheint aber nicht für 1 oder 2 zu funktionieren.

Scherzen
quelle
Nett. Jede ^, v, /, oder \ für den zweiten Rohling hätte dort gearbeitet. Ich wünschte jetzt, ich hätte das *anstelle des abgedeckt /.
Esolanging Fruit
2

Java (OpenJDK 8) , Magic Octopus Urn

class X{public static void main(String[]args){System.out.println(new String(████████[Integer.parseInt(args[0])]).matches("█████████████")?███);}}
class X{public static void main(String[]args){System.out.println(new String(new char[Integer.parseInt(args[0])]).matches(".?|(..+?)\\1+")?0:1);}}

Probieren Sie es online aus!

Der Code stammt aus RosettaCode und wird auf SO erklärt .

ovs
quelle
Hatte keine Ahnung, dass es so beliebt war hah! Hatte das schon lange in meiner Gesäßtasche. Ich habe es ehrlich aus einer Utility-Datei gestohlen, die ich seitdem hatte wie ... Herrgott ... 2014?
Magic Octopus Urn
2

Python 3 , 44 Bytes, osuka_

p=lambda x,i=2:i>=x or(x%i and p(x,i+1))or 0

Probieren Sie es online aus!

Funktioniert nicht, wenn x <2 ist. Das or 0kann durch >0{2 spaces}oder sogar 4 Leerzeichen ersetzt werden

Für das x <2-Problem muss da i>=xvorne stehen (sonst gibt es eine Endlosschleife), und die i>=xRückgabe ist sofort wahr, wenn x <2, also denke ich, dass das damit keine Lösung ist.

Shieru Asakoto
quelle
Wie sich herausstellt, funktioniert mein Code auch nicht mit x <2. Hoppla. (Ich habe es wahrscheinlich gerade mit Range (2, ...) getestet, weil ich dumm bin)
osuka_
2

M, Dylnan

ÆPø“;;“»VOḣ2S⁵++3Ọ;”Pv

Dies war wahrscheinlich nicht die beabsichtigte Lösung.

Probieren Sie es online aus!

Wie es funktioniert

ÆP ist der eingebaute Primalitätstest.

øWesen eine neue, niladische Kette. Da der vorherige Rückgabewert (das Ergebnis von ÆP) außerhalb des Gültigkeitsbereichs liegt, wird er implizit gedruckt.

“;;“»wertet die Liste der Zeichenfolgen aus ["< Aalst" ""]und Vversucht, sie auszuwerten . sversucht, sein Argument in Blöcke der Länge 0 aufzuteilen , wodurch der M-Interpreter abstürzt und die weitere Ausgabe unterdrückt wird.

Dennis
quelle
Nicht beabsichtigte Lösung, aber schön. Wird den Beitrag bald auf geknackt aktualisieren. Wenn ich das Wort "Zoo" sagen würde, würde das Sie zu einer anderen möglichen Lösung führen?
Dylnan
Hm, das klingt nach komplexer Unendlichkeit.
Dennis
1

Python 3 , user71546

import random
def f(z):
 if z<4:return z>>1
 d,s,n,e,c=~-z,0,z,0,50
 while not d&1:d//=2;s+=1
 while n>0:n//=2;e+=1
 random.seed()
 while c>0:
  a=0
  while a<2or a>z-1:
   a,b=0,e
   while b>0:a=a*2+random.randint(0,1);b-=1
  x,r=pow(a,d,z),~-s
  if ~-x and x!=~-z:
   while r>0:
    x,r=pow(x,2,z),~-r
    if not ~-x:return 0
    elif x==~-z:break
   else:return 0
  c-=1
 else:return 1

Probieren Sie es online aus!

Nitrodon
quelle