Suchen Sie eine Zahl, die alle ganzen Zahlen mod q generiert

9

Betrachten Sie die Ganzzahlen modulo, bei qdenen qes sich um Primzahlen handelt. Ein Generator ist eine beliebige Ganzzahl 1 < x < q, x^1, x^2, ..., x^(q-1)die alle q-1Ganzzahlen zwischen 1und abdeckt q-1. Betrachten Sie zum Beispiel die ganzen Zahlen modulo 7 (als die wir schreiben Z_7). Dann 3, 3^2 mod 7 = 2, 3^3 = 27 mod 7 = 6, 3^4 = 81 mod 7 = 4, 3^5 = 243 mod 7 = 5, 3^6 = 729 mod 7 = 1deckt alle Werte 3, 2, 6, 4, 5, 1deckt alle Zahlen 1..6nach Bedarf.

Die Aufgabe besteht darin, Code zu schreiben, der eine Eingabe übernimmt nund einen Generator für ausgibt Z_n. Sie können natürlich keine eingebaute Bibliothek verwenden, die dies für Sie erledigt.

Die einzige Einschränkung für die Leistung Ihres Codes besteht darin, dass Sie ihn vollständig getestet haben müssen n = 4257452468389.

Beachten Sie, dass 2^n dies 2die Leistung von bedeutet n. Das ist ^Potenzierung.


quelle
Hmm ... 1 < x < qmacht die Herausforderung imo viel einfacher.
Erik der Outgolfer
@EriktheOutgolfer Ich bin nicht sicher, ob ich weiß, was du meinst? Dies sind nur alle unterschiedlichen Ganzzahlen, die nicht 0 oder 1 sind.
Ich meine, es ist einfacher als das, was viele wahrscheinlich denken ... oder vielleicht ein inaktiver Moment bei PPCG.
Erik der Outgolfer
3
Aber ich denke, dass es unnötig ist, Leute zu beauftragen, es bis zu einer großen Anzahl zu testen ... im Grunde würde tio nur Speicherfehler.
Erik der Outgolfer
@Lembik Gibt es einen Fall, in dem es für eine bestimmte Nummer keinen Generator gibt? Einige Testfälle wären gut.
Herr Xcoder

Antworten:

13

Pyth, 16 15 Bytes

f-1m.^T/tQdQPtQ

Testsuite

Wenn p die Eingabe ist, wissen wir, dass g ^ (p-1) = 1 mod p ist, also müssen wir nur überprüfen, dass g ^ a! = 1 mod p für jedes kleinere a ist. Aber a muss ein Faktor von p-1 sein, damit dies möglich ist, und jedes Vielfache eines a mit dieser Eigenschaft hat auch diese Eigenschaft, also müssen wir nur überprüfen, dass g ^ ((p-1) / q)! = 1 mod p für alle Primfaktoren q von p-1. Also überprüfen wir alle ganzen Zahlen g in aufsteigender Reihenfolge, bis wir eine finden, die funktioniert.

Erläuterung:

f-1m.^T/tQdQPtQ
f                  Return the first value T such that the following is truthy:
            PtQ    Take the prime factorization of the input - 1.
   m               Map those prime factors to
       /tQd        Take the input - 1 divided by the factor
    .^T    Q       Raise T to that exponent mod input,
                   performed as modular exponentiation, for performance.
 -1                Check that 1 is not found among the results.
isaacg
quelle
Ziemlich cool!
Führt Ihr Code die Faktorisierung durch?
@Lembik Es tut (der PtQTeil).
Erik der Outgolfer
5

Mathematica, 52 Bytes

Inspiriert von Isaacs Antwort .

1//.i_/;PowerMod[i,Divisors[#-1],#]~Count~1!=1:>i+1&
Alephalpha
quelle
-3
%MATLAB CODE
%Program to generate Z_n for an integer n
n = input('Enter a number to find modulo')
q = input ('Enter a prime number greater than the number you wished to find modulo')
if n>=q 
   fprintf('Error')
   exit(1)
end
for R=1:q-1
    fprintf(rem(n.^R, q))
    fprintf('\n')
end
John Brookfields
quelle
1
Dies löst nicht das richtige Problem. Ihr Code sollte beispielsweise eine Eingabe und eine Ausgabe enthalten.
1
Außerdem wird dieser Code überhaupt nicht gespielt. Golfed Code muss so kurz wie möglich sein, damit Sie den eingegebenen Text und Leerzeichen um Gleichheitszeichen und dergleichen entfernen können.
Genosse SparklePony
3
@ ComradeSparklePony Ich denke, das erste Problem, dass es nicht das richtige Problem löst, sollte zuerst angegangen werden :)