[GO] [Internal_math version (2)] Dekodieren der AtCoder Library ~ Implementierung in Python ~

0. Einleitung

AtCoder Offizielle Algorithmus-Sammlung AtCoder Library (** ACL **), veröffentlicht am 7. September 2020 es war erledigt. Ich dachte, es wäre eine gute Gelegenheit, da die meisten in ACL enthaltenen Algorithmen für mich neu waren. Deshalb habe ich alles getan, vom Studium der Algorithmen bis zur Implementierung in Python.

In diesem Artikel werden wir uns ** internal_math ** ansehen.

internal_math ist eine Auswahl mathematischer Algorithmen, die in ACLs verwendet werden und die folgenden Inhalte enthalten.

Davon in diesem Artikel

• is_prime
• primitive_root

Griffe. Ich werde nicht auf constexpr (konstanter Ausdruck) selbst eingehen.

In diesem Artikel nicht behandelt

• safe_mod
• pow_mod
• inv_gcd
• barrett

Wird im folgenden Artikel behandelt. Bitte sehen Sie das, wenn Sie möchten. [[Internal_math version ①] Dekodieren der AtCoder Library ~ Implementierung in Python ~] qiita_internal_math_1

Zielgruppe Leser

• Wenn Sie sich den ACL-Code ansehen, aber ** nicht wissen, was Sie tun **.
• Diejenigen, die C ++ nicht verstehen und es in Python lesen möchten.

Nicht zielgerichtete Leser

• Diejenigen, die Python-optimierten Code für ACL möchten. → Da es so implementiert wurde, dass es so weit wie möglich mit ACL identisch ist, wird die Ausführungsgeschwindigkeit in Python überhaupt nicht berücksichtigt. Es scheint eine Bewegung zu geben, die es direkt von Cython aus zur Verfügung stellt, daher kann es gut sein, dem zu folgen.

Referenziert

Dies ist eine Wikipedia-Seite, die sich auf is_prime bezieht.

• [Japanische Version von Wikipedia - Satz von Fratat] wiki_fermat
• [Japanische Version von Wikipedia --Probabilistische Primzahl] wiki_prp

Dies ist ein Artikel über starke Pseudo-Primzahlen.

• GERHARD JAESCHKE (1993) "ON STRONG PSEUDOPRIMES TO SEVERAL BASES"

Spiegel-Dies ist ein Artikel von @ srtk86 über die Methode zur Beurteilung der Rabin-Primzahl. Es ist leicht zu verstehen.

• [Verschiedene Haupturteile - Fermat-Testspiegel Rabin-Haupturteilsmethode] qiita_miller_rabin

Beschreibt die primitiven Wurzeln.

• [Mitwirkende an Wikibooks, "Elementary Integer Theory / Primitive Roots and Exponents", Wikibooks, Free Textbooks] wikibooks_primitive_root

1. is_prime

Überlegen Sie, ob die positive ganze Zahl $ n $ eine Primzahl ist.

1.1. Definitive Methode zur Beurteilung der Primzahl

Die Definition einer Primzahl ist "eine natürliche Zahl größer als 1, wobei der positive Teiler nur 1 und sich selbst ist". Teilen Sie also $ n $ durch die natürliche Zahl von 2 bis $ n -1 $, und wenn sie nicht teilbar ist, $ n $ Kann als Primzahl bezeichnet werden. Dies ist die sogenannte ** Trial Split ** -Methode. In Python sieht es folgendermaßen aus:

def deterministicPT(n):
    if n <= 1: return False
    if n == 2: return True
    for i in range(2, n):
        if n % i == 0: return False
    return True

Wenn Sie dies verwenden, um die Primzahl zu bestimmen, ist dies wie folgt.

for n in range(1, 10):
    if deterministicPT(n):
        print(f'{n}Ist eine Primzahl')
    else:
        print(f'{n}Ist keine Primzahl')

#1 ist keine Primzahl
#2 ist eine Primzahl
#3 ist eine Primzahl
#4 ist keine Primzahl
#5 ist eine Primzahl
#6 ist keine Primzahl
#7 ist eine Primzahl
#8 ist keine Primzahl
#9 ist keine Primzahl

Diese Methode entspricht der Definition, sodass Sie sicher sein können, dass $ n $ eine Primzahl ist. Eine solche Methode wird als ** definitive Primzahlbeurteilungsmethode ** bezeichnet. Mit anderen Worten besteht die endgültige Primzahlbeurteilungsmethode darin, einen Test mit den folgenden Eigenschaften durchzuführen.

• Wenn es eine Primzahl ist, wird sie definitiv bestehen **
• Wenn es keine Primzahl ist, wird es definitiv scheitern **

1.2 Probabilistische Methode zur Beurteilung von Primzahlen

Im Gegensatz zu der endgültigen Primzahlbeurteilungsmethode, die entweder "Primzahl" oder "Nicht-Primzahl" bestimmt, ist der Algorithmus, der entweder "Primzahl" oder "Nicht-Primzahl" bestimmt, eine ** probabilistische Primzahlbeurteilungsmethode * *Wird genannt. Der für die probabilistische Primzahlbeurteilungsmethode verwendete Test hat die folgenden Eigenschaften.

• Wenn es eine Primzahl ist, muss sie bestehen **
• Wenn es sich nicht um eine Primzahl handelt, kann sie entweder bestanden oder nicht bestanden werden **
• ** Eingebaute natürliche Zahl $ a $ **

Und die natürliche Zahl, die einen solchen Test besteht, heißt "** probabilistische Primzahl der Basis $ a $ **".

Schauen wir uns ein konkretes Beispiel an. Betrachten Sie den folgenden Test für die natürliche Zahl $ n $, die Sie bestimmen möchten.

• Fehlschlagen, wenn $ n = 1 $
• Bestehen Sie, wenn $ 2 \ leq n \ leq a $
• Wenn $ n> a $, übergeben, wenn nicht teilbar durch $ a $, fehlschlagen, wenn teilbar

Da dieser Test die obigen drei Eigenschaften erfüllt, kann er als probabilistische Methode zur Beurteilung der Primzahl verwendet werden. In Python implementiert, würde es so aussehen:

class ProbabilisticPT:
    def __init__(self, a=2):
        self._a = a
    
    def change_base(self, a):
        self._a = a
    
    def test(self, n):
        if n == 1: return False
        if n <= self._a: return True
        if n % self._a != 0:
            return True
        else:
            return False

Lassen Sie uns eine Primzahl beurteilen, wenn $ a = 2 $.

a = 2
ppt = ProbabilisticPT(a)
for n in range(10):
    if ppt.test(n):
        print(f'{n}Ist der Boden{a}Probabilistische Primzahl von')
    else:
        print(f'{n}Ist keine Primzahl')

#1 ist keine Primzahl
#2 ist eine probabilistische Primzahl von Basis 2
#3 ist eine probabilistische Primzahl von Basis 2
#4 ist keine Primzahl
#5 ist eine probabilistische Primzahl von Basis 2
#6 ist keine Primzahl
#7 ist eine probabilistische Primzahl von Basis 2
#8 ist keine Primzahl
#9 ist eine probabilistische Primzahl von Basis 2

Sie können dem Urteil "Es ist keine Primzahl" im probabilistischen Primzahlurteil vertrauen. Dies liegt daran, dass eine der Eigenschaften des Tests "Wenn es sich um eine Primzahl handelt, wird sie definitiv bestanden" lautet: "Wenn es fehlschlägt, ist es nicht immer eine Primzahl". Daher wurde entschieden, dass 4, 6 und 8 keine Primzahlen sind. Wenn es sich jedoch um eine "probabilistische Primzahl" handelt, müssen Sie vorsichtig sein, da Sie nicht viele Informationen daraus erhalten können.

Der Vorteil der probabilistischen Primzahlbeurteilung liegt wahrscheinlich in ihrer Berechnungsgeschwindigkeit. In diesem Beispiel kann beurteilt werden, ob es sich um eine "probabilistische Primzahl" oder eine "Nicht-Primzahl" mit nur einer Division handelt. Das erhaltene Ergebnis ist jedoch "mögliche Primzahl", und ich weiß nicht, ob es sich wirklich um eine Primzahl handelt. Tatsächlich wird die zusammengesetzte Zahl 9 auch als probabilistische Primzahl beurteilt.

1.3. Zur Verbesserung der Genauigkeit

Bei der probabilistischen Primzahlbeurteilungsmethode werden Tests an mehreren Basen durchgeführt, um die Genauigkeit der Beurteilung zu verbessern. Wenn es an einer Basis als "keine Primzahl" beurteilt wird, wird bestätigt, dass die natürliche Zahl keine Primzahl ist, so dass eine Verbesserung der Beurteilungsgenauigkeit erwartet werden kann. Lassen Sie uns tatsächlich auf natürliche Zahlen unter 30 testen, wenn die Basis 2, 3, 5 ist.

ppt = ProbabilisticPT()
p = {}
for a in [2, 3, 5]:
    p[a] = set()
    ppt.change_base(a)  #Stellen Sie den Boden auf a
    for n in range(30):
        if ppt.test(n):
            p[a].add(n)
for k, v in p.items(): print(f'Unterseite{k}Probabilistische Primzahl von: {v}')

#Finden Sie den gemeinsamen Teil des Satzes stochastischer Primzahlen für jede Basis
print('Probabilistische Primzahlen an allen Basen:', p[2] & p[3] & p[5])



#Probabilistische Primzahl der Basis 2: {2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29}
#Probabilistische Primzahl der Basis 3: {2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29}
#Probabilistische Primzahl der Basis 5: {2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24, 26, 27, 28, 29}
#Probabilistische Primzahlen an allen Basen: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

9, die als probabilistische Primzahl beurteilt wurde, wenn die Basis 2 war, wurde durch den Test mit der Basis 3 als zusammengesetzte Zahl bestätigt. Auf diese Weise besteht die Idee der probabilistischen Primzahlbeurteilungsmethode darin, die Wahrscheinlichkeit zu verbessern, dass die probabilistischen Primzahlen an allen Basen Primzahlen sind, indem mehrere Basen mit einer ausreichenden Genauigkeit kombiniert werden. In dem diesmal verwendeten Test war es durch Kombinieren von drei Basen (2, 3, 5) möglich, eine natürliche Zahl von weniger als 30 als Primzahl mit 100% iger Genauigkeit zu beurteilen.

1.4 Fermat-Test

Derjenige, der den Satz von ** Fermat ** zum Testen verwendet, heißt ** Fermat-Test **. Der Satz von Fermat lautet wie folgt.

Wenn $ p $ eine Primzahl ist und $ a $ eine ganze Zahl ist, die kein Vielfaches von $ p $ ist ($ a $ und $ p $ sind Primzahlen zueinander)

a^{p-1} \equiv 1 \pmod{p}

Ist festgelegt.

Mit anderen Worten, was ist der Fermat-Test?

• Bestehen Sie, wenn $ a ^ {n-1} \ equiv 1 \ pmod {n} $ für $ a $ erfüllt ist. Dies ist eine natürliche Zahl, die sich mit $ n $ gegenseitig ausschließt.
• Fehler, wenn nicht erfüllt

Das ist. Der Fermat-Test ist viel leistungsfähiger als der Test, den ich zuvor verwendet habe, und von den 11.408.012.595 ungeraden Verbundwerkstoffen bis zu 25 $ mal 10 ^ 9 $ können nur 21.853 den Fermat-Test mit einem Boden von 2 bestehen. .. (Aus "[japanische Version der Wikipedia-probabilistischen Primzahl] wiki_prp")

Der Fermat-Test hat jedoch auch seine Nachteile. Eine synthetische Zahl namens ** Carmichael-Zahl ** besteht jeden unteren Fermat-Test. Unabhängig davon, wie viele Böden kombiniert werden, bleibt die Möglichkeit einer Fehleinschätzung in einer Größe, die im Fermat-Test nicht ignoriert werden kann.

1.5 Quadratwurzel von 1 in der Mod-Welt

Betrachten Sie zur Vorbereitung auf die Verbesserung des Fermat-Tests zunächst die Quadratwurzel von 1 in der Mod-Welt. Die Quadratwurzel von 1 in der Mod-Welt ist $ x $, was die folgende Kongruenz für zwei oder mehr natürliche Zahlen $ n $ erfüllt.

x^2 \equiv 1 \pmod{n}

Offensichtlich erfüllt $ x = 1, n-1 $ diese Gleichung, daher nennen wir sie ** offensichtliche ** Quadratwurzeln und die anderen ** nicht offensichtlichen ** Quadratwurzeln.

Betrachten Sie die nicht triviale Quadratwurzel. Betrachten Sie also den Fall, in dem $ x $ weder $ 1 $ noch $ n-1 $ ist. Wenn beispielsweise $ n = 15 $, $ x = 4, 11 $ eine nicht triviale Quadratwurzel ist.

\begin{aligned}
(4)^2 &= 16 \equiv 1 \pmod{15}\\
(11)^2 &= 121 \equiv 1 \pmod{15}
\end{aligned}

Aber was ist, wenn $ n $ eine Primzahl ist? Tatsächlich gibt es zu diesem Zeitpunkt ** keine nicht triviale Quadratwurzel **. Lassen Sie uns dies in Absurdität zeigen. Jetzt gibt es ein nicht triviales Quadratwurzel-Modulo, die Primzahl $ p $, die wir $ x $ nennen. Das heißt, $ x $ ist weder $ 1 $ noch $ p-1 $.

x^2 \equiv 1 \pmod{p}

Treffen. In diesem Moment,

\begin{aligned}
x^2 &\equiv 1 \pmod{p}\\
x^2 - 1 &\equiv 0 \pmod{p}\\
(x + 1) (x - 1) &\equiv 0 \pmod{p}
\end{aligned}

Und da $ p $ eine Primzahl ist, ist mindestens eine von $ (x + 1) $ und $ (x -1) $ durch $ p $ teilbar. Aber $ x $ ist weder $ 1 $ noch $ p-1 $

\begin{aligned}
(x + 1) \not \equiv 0 \pmod{p}\\
(x - 1) \not \equiv 0 \pmod{p}
\end{aligned}

Es wird sein. Das heißt, sowohl $ (x + 1) $ als auch $ (x -1) $ sind nicht durch $ p $ teilbar. Daher wurde gezeigt, dass es aufgrund der Inkonsistenz kein nicht triviales Quadratwurzelmodul der Primzahl $ p $ gibt.

1.6 Fermats kleiner Satz für ungerade Primzahlen

Wenn die natürliche Zahl, die Sie beurteilen möchten, 2 ist, ist es offensichtlich, dass es sich um eine Primzahl handelt. Nehmen wir also an, dass sie im Voraus verarbeitet wurde. Zu diesem Zeitpunkt ist die Primzahl immer ungerade. Betrachten Sie also Fermats kleinen Satz für die ungerade Primzahl $ p $. Verwenden Sie nun, da $ p-1 $ gerade ist, die natürlichen Zahlen $ s $ und die ungeraden $ d $

p - 1 = 2^s \cdot d

Kann ausgedrückt werden als. Daher lautet der Satz von Fermat

a^{2^s \cdot d} \equiv 1 \pmod{p}

Und das ist

(a^{2^{s-1} \cdot d})^2 \equiv 1 \pmod{p}

Das können Sie auch sehen. Wie im vorherigen Abschnitt gezeigt, gibt es keine nicht triviale Quadratwurzel von $ 1 $ modulo der Primzahl $ p $

\begin{aligned}
a^{2^{s-1} \cdot d} &\equiv \;\;\:1 \pmod{p}\\
a^{2^{s-1} \cdot d} &\equiv -1 \pmod{p}
\end{aligned}

Es wird entweder sein. Wenn es das erste war, dann ist $ s -1> 0 $

(a^{2^{s-2} \cdot d})^2 \equiv 1 \pmod{p}

Es ist zu sehen, dass dies auch so ist

\begin{aligned}
a^{2^{s-2} \cdot d} &\equiv \;\;\:1 \pmod{p}\\
a^{2^{s-2} \cdot d} &\equiv -1 \pmod{p}
\end{aligned}

Es wird entweder sein. Wenn Sie dies eines Tages wiederholen

\begin{aligned}
a^{d} &\equiv \;\;\:1 \pmod{p}\\
a^{d} &\equiv -1 \pmod{p}
\end{aligned}

Es wird sein. Die Zusammenfassung bis zu diesem Punkt ist wie folgt.

Wenn $ p $ eine ungerade Primzahl ist, verwenden Sie die natürlichen Zahlen $ s $ und die ungeraden $ d $

p - 1 = 2^s \cdot d

Kann geschrieben werden und ** muss einen der folgenden kongruenten Ausdrücke modulo $ p $ ** erfüllen.

\begin{aligned}
a^{2^{s-1} \cdot d} &\equiv -1\\
a^{2^{s-2} \cdot d} &\equiv -1\\
\cdots\\
a^{2 \cdot d} &\equiv -1\\
a^{d} &\equiv -1\\
a^d &\equiv \;\;\:1
\end{aligned}

Diese Kongruenzformel enthält höchstens $ \ log_2 {p} $. Überprüfen wir also alle **.

Aus dem oben Gesagten ergibt sich der Test für die natürliche Zahl $ n $, die Sie beurteilen möchten, wie folgt.

• Fehlschlagen, wenn $ n = 1 $

• Bestehen, wenn $ n = 2 $

• Fehler, wenn $ n \ geq 3 $ gerade ist

• Wenn $ n \ geq 3 $ ungerade ist, dann ist $ n -1 = 2 ^ s \ cdot d $ und $ n $ als Gesetz für eine natürliche Zahl $ a $, die sich mit $ n $ gegenseitig ausschließt.

  \begin{aligned}
  a^{2^{s-1} \cdot d} &\equiv -1\\
  a^{2^{s-2} \cdot d} &\equiv -1\\
  \cdots\\
  a^{2 \cdot d} &\equiv -1\\
  a^{d} &\equiv -1\\
  a^d &\equiv \;\;\:1
  \end{aligned}
  

Bestehen Sie, wenn Sie mindestens einen von ihnen treffen, bestehen Sie, wenn Sie keinen von ihnen treffen

Die probabilistische Primbestimmungsmethode unter Verwendung dieses Tests wird als ** Mirror-Rabin-Primbestimmungsmethode ** bezeichnet.

1.7. So implementieren Sie den Test

Organisieren Sie die Urteile für ungerade $ n $ von 3 oder mehr. Da die probabilistische Primzahlbeurteilungsmethode mit mehreren Basen testet und beurteilt, dass es sich nur dann um eine Primzahl handelt, wenn alle bestanden sind, ist es nur erforderlich, den Fehlerfall im Testprozess zu erkennen. Nehmen wir nun $ n -1 = 2 ^ s \ cdot d $ an und der untere Teil des Tests ist $ a $. Zu diesem Zeitpunkt wird $ a ^ {2 ^ rd} $ für $ r $ so berechnet, dass $ 0 \ leq r <s $. Erstens, wenn $ r = 0 $

a^d \equiv 1\; or\; -1 \pmod{n}

Wenn ja, ist der Test für das untere $ a $ abgeschlossen. Wenn nicht, für $ r = 1, 2, \ cdots, s-1 $

a^{2^rd} \not \equiv 1\; or\; -1 \pmod{n}

Berechnen Sie so lange wie. Auch die Beendigungsbedingung $ r <s $ für $ r $ entspricht $ 2 ^ rd <n -1 $. Wenn $ a ^ {2 ^ rd} \ equiv -1 \ pmod {n} $, ist der Test für die Basis $ a $ abgeschlossen. Aber was ist, wenn es zu $ a ^ {2 ^ rd} \ equiv 1 \ pmod {n} $ wird? Zu diesem Zeitpunkt wurde bereits bestätigt, dass $ a ^ {2 ^ {r-1} d} $ weder $ 1 $ noch $ -1 $ ist, also $ a ^ {2 ^ {r-1} d} $ Die nicht triviale Quadratwurzel von $ 1 $. Daher ist $ n $ keine Primzahl und wird abgelehnt. Wenn es bis zum Ende $ a ^ {2 ^ rd} \ not \ equiv 1 ; oder ; -1 \ pmod {n} $ ist, wird es abgelehnt. Das Obige ist in der folgenden Abbildung zusammengefasst.

1.8 Wie man den Boden wählt

Bei der Spiegel-Rabin-Primzahl-Beurteilungsmethode wird die Anzahl der Basen im Allgemeinen selbst bestimmt und eine natürliche Zahl $ a $, so dass $ a <n $ zufällig ausgewählt ** und als Basis verwendet wird. Da es einen Kompromiss zwischen Berechnungsgeschwindigkeit und Beurteilungsgenauigkeit gibt, ist es wünschenswert, so wenig Grundlagen wie möglich zu haben und gleichzeitig die erforderliche Genauigkeit sicherzustellen. Daher wurden Bodenkombinationen untersucht, die die Genauigkeit effizient verbessern können. ACL verwendet $ a = \ {2, 7, 61 } $ als Basis. Nach [Jaeschke (1993)] min_2_7_61 beträgt die Mindestanzahl von Verbundwerkstoffen, die diesen gesamten Bodentest bestehen, $ 4759123141 ; (= 48781 \ cdot 97561> 2 ^ {32}) $. Daher kann im Bereich von $ n <2 ^ {32} $ (Bereich der vorzeichenlosen 4-Byte-Ganzzahl) mit der Genauigkeit von $ 100 % $ beurteilt werden.

1.9. Implementierung

Lassen Sie es uns implementieren. Der Teil, der pow_mod in ACL verwendet, wird durch die in Python integrierte Funktion pow ersetzt, die eine äquivalente Funktion darstellt.

def is_prime(n):
    #Offensichtlicher Teil
    if (n <= 1): return False
    if (n == 2 or n == 7 or n == 61): return True
    if (n % 2 == 0): return False

    d = n - 1  #n ist ungerade
    while (d % 2 == 0): d //= 2  #Finde die ungerade d

    for a in (2, 7, 61):
        t = d  #Halten Sie d gedrückt, da es auch an anderen Böden verwendet wird
        y = pow(a, t, n)

        # a^d = 1, -Wenn es 1 ist, wird diese Schleife nicht eingegeben
        # a^t = 1, -Wiederholen bis 1
        while (t != n - 1 and y != 1 and y != n - 1):
            y = y * y % n
            t <<= 1
        
        # a^d = 1, -1 Durchgänge(t%2 == 0)
        # a^t = -1 Durchgänge(y != n - 1)
        if (y != n - 1 and t % 2 == 0):
            return False
    return True



print(is_prime(17))  # True
print(is_prime(1000000007))  # True
print(is_prime(121))  # False
print(is_prime(561))  # False (561 ist eine der Carmichael-Zahlen)

#Unterseite{2, 7, 61}Mindestanzahl von Verbundwerkstoffen, die den Test bestehen
print(is_prime(4759123141))  # True

1.10 Vergleich der Berechnungsgeschwindigkeit

Vergleichen wir es mit der endgültigen Primzahl-Beurteilungsmethode des Zeitberechnungsbetrags $ O (\ sqrt {n}) $. Der für den Vergleich verwendete Code ist unten.

import random

#Spiegel-Rabin-Primzahl-Beurteilungsmethode (probabilistische Primzahl-Beurteilungsmethode)
def pro_is_prime(n):
    if (n <= 1): return False
    if (n == 2 or n == 7 or n == 61): return True
    if (n % 2 == 0): return False
    d = n - 1
    while (d % 2 == 0): d //= 2
    for a in (2, 7, 61):
        t = d
        y = pow(a, t, n)
        while (t != n - 1 and y != 1 and y != n - 1):
            y = y * y % n
            t <<= 1
        if (y != n - 1 and t % 2 == 0):
            return False
    return True

#Definitive Methode zur Beurteilung der Primzahl
def det_is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False
    for i in range(3, int(n ** 0.5) + 1):
        if n % i == 0: return False
    return True


def random_1():
    l1, r1 = [3, 1 << 16]
    return random.randrange(l1, r1, 2)

def random_2():
    l2, r2 = [(1 << 16) + 1, 1 << 32]
    return random.randrange(l2, r2, 2)

def random_3():
    l3, r3 = [3, 1 << 32]
    return random.randrange(l3, r3, 2)


def main():
    """
    seed_list = [111, 222, 333, 444, 555, \
                 666, 777, 888, 999, 101010]
    """
    random.seed(111)  #Feste Zufallszahl
    loop = 10000  #Anzahl der Schleifen 10^4 or 10^6

    for _ in range(loop):
        n = random_1()
        #n = random_2()
        #n = random_3()

        pro_is_prime(n)  #Probabilistisch
        #det_is_prime(n)  #Definitiv
    

if __name__ == "__main__":
    main()

Messmethode

Ich habe den Code-Test von AtCoder (Python 3.8.2) verwendet. Zufallszahlen wurden aus 3 Arten von Bereichen mit 10 Arten von Startwerten erzeugt, und die Ausführungszeit pro 10.000 Haupturteile wurde untersucht. Bei einer geraden Zahl werden beide zuerst verarbeitet, sodass nur eine ungerade Zahl verwendet wird.

• random_1
• Zufälliger Bereich: $ [3, 2 ^ {16}] $ ungerade
• Anzahl der Schleifen: $ 10 ^ 4, 10 ^ 6 $ (da $ 10 ^ 4 $ der Hauptaufwand sein kann, z. B. Import)
• random_2
• Bereich von Zufallszahlen: $ [2 ^ {16}, 2 ^ {32}] $ ungerade
• Anzahl der Schleifen: $ 10 ^ 4 $
• random_3
• Zufälliger Bereich: $ [3, 2 ^ {32}] $ ungerade
• Anzahl der Schleifen: $ 10 ^ 4 $

Messergebnis

Das Ergebnis ist in der folgenden Abbildung dargestellt. Der numerische Wert ist die Zeit pro 10.000 Haupturteile und die Einheit ist ms.

Wenn die Zahl, die Sie beurteilen möchten, nur $ 10 ^ 5 $ beträgt, scheint die endgültige Methode zur Beurteilung der Primzahl etwas schneller zu sein. Mit zunehmender Anzahl wird jedoch die Überlegenheit des Spiegel-Rabin-Primzahl-Bestimmungsverfahrens bemerkenswert.

2. primitive_root Finden Sie die kleinste der primitiven Wurzeln modulo die Primzahl $ m $.

2.1. Nummer

Schauen wir uns zunächst den wichtigen Begriff "Zahl" an, um die primitiven Wurzeln zu erklären. Die Definition ist dies.

Für natürliche Zahlen $ m $ und $ m $ von 2 oder mehr und ganze Zahlen $ a $, die sich gegenseitig ausschließen

a^{n} \equiv 1 \pmod{m}

Die kleinste natürliche Zahl $ n $ heißt der Bruch ** von $ a $ modulo ** $ m $.

Schauen wir uns ein konkretes Beispiel an. Wenn $ m = 5 ist, ist a = 3 $

\begin{aligned}
3^1  &= 3 & \not \equiv 1 \pmod{5}\\
3^2  &= 9 & \not \equiv 1 \pmod{5}\\
3^3  &= 27 & \not \equiv 1 \pmod{5}\\
3^4  &= 81 & \equiv 1 \pmod{5}
\end{aligned}

Der Bruchteil von $ 3 $ modulo $ 5 $ ist also $ 4 $. Auch wenn $ m = 12, a = 5 $,

\begin{aligned}
5^1  &= 2 & \not \equiv 1 \pmod{12}\\
5^2  &= 25 & \equiv 1 \pmod{12}
\end{aligned}

Der Bruchteil von $ 5 $ modulo $ 12 $ beträgt also $ 2 $.

Die Art des Ranges

Der Bruch $ e $, bei dem es sich um eine Ganzzahl $ a $ handelt, die sich für $ m $ gegenseitig ausschließt, modulo $ m $, hat die folgenden Eigenschaften für die positive Ganzzahl $ n $.

a^n \equiv 1 \pmod{m} \Leftrightarrow e\;Ist\;n\;CA

(Beweis) \Leftarrow: Da $ e $ ein Bruchteil von $ n $ ist, verwenden wir die natürliche Zahl $ k $ und multiplizieren mit $ n = ke $. Verwenden Sie daher $ m $ als Gesetz

\begin{aligned}
a^n &=a^{ke}\\
&= (a^e)^k\\
&\equiv 1
\end{aligned}

Und etabliert. \Rightarrow: $ n $ wird ausgedrückt als $ n = qe + r ; (0 \ leq r <e) $ unter Verwendung nicht negativer Ganzzahlen $ q und r $. Zu diesem Zeitpunkt wird $ m $ als Gesetz verwendet

\begin{aligned}
a^r &\equiv (a^{e})^qa^r\\
&\equiv a^{qe+r}\\
&\equiv 1
\end{aligned}

Wird sein. Wenn $ 0 <r <e $ ist, widerspricht dies, dass $ e $ eine Ziffer ist (die Ziffer ist eine ** minimale ** Ganzzahl, die $ a ^ e \ equiv 1 \ pmod {m} $ erfüllt). Also ist $ r = 0 $, das heißt, $ e $ ist ein Bruchteil von $ n $.

(Ende der Zertifizierung)

Insbesondere wenn $ m $ eine Primzahl ist, ist die Reihenfolge nach dem Satz von Fermat ein Bruchteil von $ m -1 $.

2.2 Primitive Wurzel

Betrachten Sie den Fall, in dem $ m $ eine Primzahl ist. Nach dem Satz von Fermat ist die Ordnung von $ m $ und die gegenseitig Primzahl $ a $, modulo $ m $, immer kleiner oder gleich $ m -1 $. Daher sind wir auf $ a $ spezialisiert, das eine Ziffer von genau $ m -1 $ hat, und nennen es eine primitive Wurzel ** modulo $ m $ **.

Zum Beispiel, wenn $ m = 7 $, $ a = 3 $

\begin{aligned}
3^1  &= 3  &\not \equiv 1 \pmod{7}\\
3^2  &= 9  &\not \equiv 1 \pmod{7}\\
3^3  &= 27  &\not \equiv 1 \pmod{7}\\
3^4  &= 81  &\not \equiv 1 \pmod{7}\\
3^5  &= 243  &\not \equiv 1 \pmod{7}\\
3^6  &= 729  &\equiv 1 \pmod{7}\\
\end{aligned}

Der Bruchteil von $ 3 $ modulo $ 7 $ ist also $ 6 $. $ 3 $ ist also ein primitives Root-Modulo $ 7 $. Es gibt nicht immer eine primitive Wurzel. Aus dem ersten Beispiel, das anstelle von Ziffern gezeigt wird, können wir sehen, dass $ 3 $ ein primitives Wurzelmodulo $ 5 $ ist. Auf der anderen Seite, wenn $ a = 2 $

\begin{aligned}
2^1  &= 2 & \not \equiv 1 \pmod{5}\\
2^2  &= 4 & \not \equiv 1 \pmod{5}\\
2^3  &= 8 & \not \equiv 1 \pmod{5}\\
2^4  &= 16 & \equiv 1 \pmod{5}
\end{aligned}

$ 2 $ ist also auch ein primitives Root-Modulo $ 5 $.

Beachten Sie, dass eine primitive Wurzel immer dann existiert, wenn $ m $ eine Primzahl ist. Bitte überprüfen Sie den Beweis mit "Primitive Root Theorem".

Primitive Wurzelnatur

Primitive Wurzel $ g $ modulo Die Primzahl $ m $ hat die folgenden Eigenschaften:

Eine Reihe von Potenzen von $ g $ modulo $ m $

\{g\pmod{m}, g^2\pmod{m}, \cdots , g^{m - 1}\pmod{m}\}

Und die ganze Zahl geteilt durch $ m $ minus $ 0 $

\{1, 2, \cdots , m - 1\}

Spiel.

Dies kann wie folgt umschrieben werden: Über die natürliche Zahl $ k $ von $ 1 \ leq k \ leq m-1 $

• g^k \not \equiv 0
• $ g ^ k $ sind alle unterschiedlich.

Das erste ergibt sich aus der Tatsache, dass sich $ g $ und $ m $ gegenseitig ausschließen. Deshalb werde ich den zweiten beweisen.

(Beweis) Nehmen wir nun an, es gibt eine natürliche Zahl $ k, l $, so dass $ k <l \ leq m - 1 $, und es ist $ g ^ k \ equiv g ^ l \ pmod {m} $. In diesem Moment

\begin{aligned}
g^l - g^k &\equiv 0 \pmod{m}\\
g^k(g^{l-k} - 1) &\equiv 0 \pmod{m}\\
g^{l-k} - 1 &\equiv 0 \pmod{m}\\
g^{l-k} &\equiv 1 \pmod{m}
\end{aligned}

Es wird sein. Da $ l - k <m - 1 $ ist, stimmt die Reihenfolge der primitiven Wurzel $ g $ nicht mit $ m-1 $ überein. Für $ 1 \ leq k \ leq m-1 $ ist $ g ^ k $ also alles anders. (Ende der Zertifizierung)

2.3 So überprüfen Sie, ob es sich um eine primitive Wurzel handelt 1

Um zu bestimmen, ob eine natürliche Zahl $ g $ von 2 oder mehr eine primitive Wurzel ist, modulo $ m $, $ g, g ^ 2, \ cdots, modulo $ m $ aus der Definition der primitiven Wurzel Stellen Sie sicher, dass nicht alle g ^ {m --2} $ mit $ 1 $ übereinstimmen. Daher ist die Implementierung des Algorithmus zum Finden der kleinsten primitiven Wurzel wie folgt.

def naive_primitive_root(m):
    g = 2
    while True:
        for i in range(1, m - 1):
            if pow(g, i, m) == 1:
                g += 1
                break
        else:
            return g


print(naive_primitive_root(7))  # 3
print(naive_primitive_root(23))  # 5
#print(naive_primitive_root(1000000007))  #Sehr Zeit aufwendig

Diese Methode findet alle Potenzen von $ g $ bis zu $ m - 2 $, daher nimmt es viel Zeit in Anspruch, wenn $ m $ wächst.

2.4 So überprüfen Sie, ob es sich um eine primitive Wurzel handelt 2

Tatsächlich ist es einfacher, anhand der Eigenschaften der primitiven Wurzel zu bestätigen, ob es sich um eine primitive Wurzel handelt. Die verwendeten Eigenschaften sind:

Unter Verwendung der Primzahl $ p_i $ und der natürlichen $ e_i $ steht $ m-1 $ für eine Primzahl $ m $ größer oder gleich $ 3 $.

m-1 = \prod_{i = 1}^n{p_i^{e_i}}

Berücksichtigt man die Primfaktoren, gilt das Folgende für natürliche Zahlen $ g $ über $ 2 $.

g\;Aber\;m\;Primitive Wurzeln
\Leftrightarrow 1 \leq i \leq n\;Gegen\; g^{\frac{m-1}{p_i}}\not\equiv 1 \pmod{m}

(Beweis) \Rightarrow: Da $ p_i $ ein Primfaktor von $ m-1 $ ist, ist $ \ frac {m-1} {p_i} $ eine ganze Zahl und erfüllt $ 1 \ leq \ frac {m-1} {p_i} <p - 1 $. Wenn $ g $ eine primitive Wurzel ist, sollte $ g ^ {p-1} $ zum ersten Mal mit $ 1 $ kongruent sein, also für $ 1 \ leq i \ leq n ; ; g ^ {\ frac {m-1} Es wird {p_i}} \ not \ equiv 1 \ pmod {m} $.

\Leftarrow: Das Paar dieser Behauptung ist

g ist keine primitive Wurzel\Rightarrow g^{\frac{m-1}{p_i}}\equiv 1 \pmod{m}Es existiert i

Also werde ich das zeigen. Jetzt ist $ g $ keine primitive Wurzel, daher ist die Reihenfolge $ e $ kleiner als $ m-1 $. Wie in der Art der Ziffern gezeigt, ist $ e $ ein Bruchteil von $ m-1 $. Verwenden Sie also $ p_i $, was dem Primfaktor von $ m-1 $ entspricht.

e = \prod_{j = 1}^n{p_j^{e_j^{\prime}}}\;\;\;(e_j^{\prime} \leq e_j)

Insbesondere gibt es mindestens ein $ j $, so dass $ e_j ^ {\ prime} <e_j $. Sei eines dieser $ j $ $ i $. In diesem Moment

\begin{aligned}
\frac{m-1}{p_i} &= \frac{1}{p_i}\prod_{j}{p_j^{e_j}}\\
&= \frac{1}{p_i}\left(\prod_{j}{p_j^{e_j - e_j^{\prime}}}\right)\left(\prod_j{p_j^{e_j^{\prime}}}\right)\\
&= p_i^{e_i - e_i^{\prime} - 1}\left(\prod_{j \ne i}{p_j^{e_j - e_j^{\prime}}}\right)\left(\prod_j{p_j^{e_j^{\prime}}}\right)
\end{aligned}

Hier $ e_i --e_i ^ {\ prime} --1 \ geq 0 $ und $ e_j --e_j ^ {\ prime} \ geq 0 $

\frac{m-1}{p_i} = (Natürliche Zahl) \times e

Wird sein. Also, wenn $ g $ keine primitive Wurzel ist

g^{\frac{m-1}{p_i}} \equiv \left(g^e\right)^{Natürliche Zahl}　\equiv 1 \pmod{m}

Es gibt $ i $.

(Ende der Zertifizierung)

Von Oben

1. Finden Sie den Primfaktor von $ m-1 $.
2. Überprüfen Sie für jeden Primfaktor $ p_i $, ob er zu $ g ^ {\ frac {m-1} {p_i}} \ not \ equiv 1 \ pmod {m} $ wird.

Sie können bestimmen, ob $ g $ eine primitive Wurzel ist, indem Sie die Prozedur befolgen.

2.5. Implementierung

Lassen Sie es uns implementieren. Pow_mod wird wie is_prime durch die eingebaute Funktion pow ersetzt.

# @param m must be prime
def primitive_root(m):
    if m == 2: return 1
    if m == 167772161: return 3
    if m == 469762049: return 3
    if m == 754974721: return 11
    if m == 998244353: return 3

    # m-Primfaktor-Extraktion von 1
    divs = [2]
    x = (m - 1) // 2
    while x % 2 == 0: x //= 2
    i = 3
    while i * i <= x:
        if x % i == 0:
            divs.append(i)
            while x % i == 0: x //= i
        i += 2
    if x > 1: divs.append(x)

    #Finden Sie das kleinste g, das nicht mit 1 in allen Primfaktoren kongruent ist
    g = 2
    while True:
        if all(pow(g, (m - 1) // div, m) != 1 for div in divs): return g
        g += 1


print(primitive_root(7))  # 3
print(primitive_root(23))  # 5
print(primitive_root(1000000007))  # 5

Die ersten paar $ m $, die bestimmt werden müssen, scheinen die Mods zu sein, die bei der Faltung verwendet werden.

3. Fazit

Dieses Mal haben wir uns die Primzahl-Beurteilungsmethode und die primitiven Wurzeln angesehen. Besonders interessant fand ich die Idee der probabilistischen Primzahlbeurteilungsmethode.

Unter den internal_math sind diejenigen, die ich dieses Mal nicht angesprochen habe, in [internal_math edition ①] qiita_internal_math_1 geschrieben. Bitte beziehen Sie sich auch darauf.

Bitte lassen Sie uns wissen, wenn Sie Fehler, Bugs oder Ratschläge haben.