[GO] [Internal_math version (2)] Décodage de la bibliothèque AtCoder ~ Implémentation en Python ~
0. Introduction
AtCoder Official Algorithm Collection AtCoder Library (** ACL **) publié le 7 septembre 2020 c'était fait. J'ai pensé que c'était une bonne opportunité car la plupart des algorithmes inclus dans ACL étaient nouveaux pour moi, j'ai donc tout fait, de l'étude des algorithmes à leur implémentation en Python.
Dans cet article, nous examinerons ** internal_math **.
internal_math est un assortiment d'algorithmes mathématiques utilisés dans les ACL et a le contenu suivant.
| Nom | Aperçu |
|---|---|
| safe_mod | entier |
| barrett | Calcul du reste à grande vitesse. |
| pow_mod | |
| is_prime | Jugement principal à grande vitesse. |
| inv_gcd | entier |
| primitive_root | nombre premier |
Parmi ceux-ci, dans cet article
- is_prime
- primitive_root
Poignées. Je ne parlerai pas de constexpr (expression constante) lui-même.
Non couvert dans cet article
- safe_mod
- pow_mod
- inv_gcd
- barrett
Est traité dans l'article suivant. S'il vous plaît voir cela si vous le souhaitez. [[Version Internal_math ①] Décodage de la bibliothèque AtCoder ~ Implémentation en Python ~] qiita_internal_math_1
Lecteurs cibles
- Si vous regardez le code ACL mais ** ne savez pas ce que vous faites **.
- Ceux qui ne comprennent pas le C ++ et veulent le lire en Python.
Lecteurs non ciblés
- Ceux qui veulent du code optimisé Python pour ACL. → Puisqu'il a été implémenté de manière à être le plus possible identique à ACL, la vitesse d'exécution en Python n'est pas du tout prise en compte. Il semble y avoir un mouvement pour le rendre disponible directement à partir de Cython, il peut donc être bon de suivre cela.
Référencé
Ceci est une page wikipedia relative à is_prime.
- [Version japonaise de Wikipédia - Théorème de Fermat] wiki_fermat
- [Version japonaise de Wikipedia - Nombre premier probabiliste] wiki_prp
Il s'agit d'un article sur les pseudo-nombres premiers forts.
Mirror-Ceci est un article de @ srtk86 sur la méthode de jugement des nombres premiers de Rabin. C'est facile à comprendre.
- [Divers jugements premiers - Méthode de jugement rabin du miroir de test de Fermat] qiita_miller_rabin
Décrit les racines primitives.
- [Contributeurs à Wikibooks, "Théorie élémentaire des nombres entiers / Racines et exposants primitifs," Wikibooks, manuels gratuits] wikibooks_primitive_root
- is_prime
Envisagez de déterminer si l'entier positif $ n $ est un nombre premier.
1.1. Méthode de jugement des nombres premiers définitifs
La définition d'un nombre premier est "un entier naturel supérieur à 1 où le diviseur positif est seulement 1 et lui-même", donc divisez $ n $ par le nombre naturel de 2 à $ n -1 $, et s'il n'est pas divisible, $ n $ Peut être considéré comme un nombre premier. Il s'agit de la méthode dite du ** trial split **. Lorsqu'il est implémenté en Python, cela ressemble à ceci:
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
Si vous l'utilisez pour déterminer le nombre premier, ce sera comme suit.
for n in range(1, 10):
if deterministicPT(n):
print(f'{n}Est un nombre premier')
else:
print(f'{n}N'est pas un nombre premier')
#1 n'est pas un nombre premier
#2 est un nombre premier
#3 est un nombre premier
#4 n'est pas un nombre premier
#5 est un nombre premier
#6 n'est pas un nombre premier
#7 est un nombre premier
#8 n'est pas un nombre premier
#9 n'est pas un nombre premier
Cette méthode adhère à la définition, vous pouvez donc être sûr que $ n $ est un nombre premier. Une telle méthode est appelée ** méthode de jugement définitif des nombres premiers **. En d'autres termes, la méthode définitive de jugement des nombres premiers consiste à effectuer un test avec les propriétés suivantes.
- S'il s'agit d'un nombre premier, il passera certainement **
- Si ce n'est pas un nombre premier, il échouera définitivement **
1.2. Méthode probabiliste de jugement des nombres premiers
Contrairement à la méthode de jugement définitif des nombres premiers qui détermine «premier» ou «non premier», l'algorithme qui détermine «peut être premier» ou «pas premier» est la ** méthode de jugement probabiliste * *Est appelé. Le test utilisé pour la méthode probabiliste de jugement des nombres premiers a les propriétés suivantes.
- S'il s'agit d'un nombre premier, il doit passer **
- S'il ne s'agit pas d'un nombre premier, il peut être réussi ou échoué **
- ** Nombre naturel intégré $ a $ **
Et le nombre naturel qui passe un tel test est appelé "** nombre premier probabiliste de base $ a $ **".
Regardons un exemple concret. Considérez le test suivant pour le nombre naturel $ n $ que vous voulez déterminer.
- Échec si $ n = 1 $
- Passer si $ 2 \ leq n \ leq a $
- Si $ n> a $, passe si non divisible par $ a $, échoue si divisible
Puisque ce test satisfait les trois propriétés ci-dessus, il peut être utilisé comme méthode probabiliste de jugement des nombres premiers. Implémenté en Python, cela ressemblerait à ceci:
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
Faisons un jugement sur les nombres premiers quand $ a = 2 $.
a = 2
ppt = ProbabilisticPT(a)
for n in range(10):
if ppt.test(n):
print(f'{n}Est le fond{a}Premier probabiliste de')
else:
print(f'{n}N'est pas un nombre premier')
#1 n'est pas un nombre premier
#2 est un premier probabiliste de base 2
#3 est un premier probabiliste de base 2
#4 n'est pas un nombre premier
#5 est un nombre premier probabiliste de base 2
#6 n'est pas un nombre premier
#7 est un nombre premier probabiliste de base 2
#8 n'est pas un nombre premier
#9 est un nombre premier probabiliste de base 2
Vous pouvez faire confiance au jugement selon lequel "ce n'est pas un nombre premier" dans le jugement probabiliste des nombres premiers. C'est parce que l'une des propriétés du test, "S'il s'agit d'un nombre premier, il passera définitivement" est "S'il échoue, ce ne sera pas toujours un nombre premier". Par conséquent, il a été décidé que 4, 6 et 8 ne sont pas des nombres premiers. Cependant, s'il est jugé comme un "nombre premier probabiliste", vous devez être prudent car vous ne pouvez pas en tirer beaucoup d'informations.
Le mérite du jugement probabiliste des nombres premiers est probablement sa vitesse de calcul. Dans cet exemple, il est possible de juger s'il s'agit d'un "nombre premier probabiliste" ou d'un "nombre non premier" avec une seule division. Cependant, le résultat obtenu est "nombre premier possible", et je ne sais pas s'il s'agit vraiment d'un nombre premier. En fait, le nombre composé 9 est également jugé être un nombre premier probabiliste.
1.3. Pour améliorer la précision
La méthode de jugement probabiliste premier teste avec plusieurs bases pour améliorer la précision du jugement. S'il est jugé "pas un nombre premier" à une base, il est confirmé que le nombre naturel n'est pas un nombre premier, de sorte qu'une amélioration de la précision du jugement peut être attendue. Testons en fait les nombres naturels inférieurs à 30 lorsque la base est 2, 3, 5.
ppt = ProbabilisticPT()
p = {}
for a in [2, 3, 5]:
p[a] = set()
ppt.change_base(a) #Réglez le bas sur un
for n in range(30):
if ppt.test(n):
p[a].add(n)
for k, v in p.items(): print(f'bas{k}Premier probabiliste de: {v}')
#Trouvez la partie commune de l'ensemble des nombres premiers stochastiques pour chaque base
print('Premiers probabilistes à toutes les bases:', p[2] & p[3] & p[5])
#Nombre premier probabiliste de base 2: {2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29}
#Nombre premier probabiliste de base 3: {2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29}
#Nombre premier probabiliste de base 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}
#Premiers probabilistes à toutes les bases: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
9 qui a été jugé comme un nombre premier probabiliste lorsque la base était 2 a été confirmé comme étant un nombre composé par le test avec la base 3. De cette manière, l'idée de la méthode de jugement probabiliste des nombres premiers est d'améliorer la probabilité que les nombres premiers probabilistes de toutes les bases soient des nombres premiers en combinant plusieurs bases avec une précision suffisante. Dans le test utilisé cette fois, en combinant trois bases (2, 3, 5), il était possible de juger un entier naturel inférieur à 30 comme nombre premier avec une précision de 100%.
1.4. Essai de Fermat
Celui qui utilise le ** théorème de Fermat ** pour les tests est appelé ** test de Fermat **. Le théorème de Fermat est le suivant.
Quand $ p $ est un nombre premier et $ a $ est un entier qui n'est pas un multiple de $ p $ ($ a $ et $ p $ sont premiers l'un par rapport à l'autre)
a^{p-1} \equiv 1 \pmod{p}
Est établi.
En d'autres termes, qu'est-ce que le test de Fermat?
- Passe si $ a ^ {n-1} \ equiv 1 \ pmod {n} $ est satisfait pour $ a $, qui est un nombre naturel qui est mutuellement exclusif à $ n $.
- Échec si non satisfait
C'est. Le test de Fermat est beaucoup plus puissant que le test que j'ai utilisé précédemment, et sur les 11.408.012.595 composites impairs jusqu'à 25 $ \ fois 10 ^ 9 $, seuls 21853 peuvent passer le test de Fermat avec un fond de 2. .. (De "[Version japonaise du nombre premier probabiliste de Wikipedia] wiki_prp")
Cependant, le test de Fermat a aussi ses inconvénients. Un nombre synthétique appelé ** nombre de Carmichael ** réussit n'importe quel test de Fermat inférieur. Par conséquent, quel que soit le nombre de fonds combinés, la possibilité d'une erreur de jugement reste dans une taille qui ne peut être ignorée dans le test de Fermat.
1.5. Racine carrée de 1 dans le monde des mods
En vue d'améliorer le test de Fermat, considérons d'abord la racine carrée de 1 dans le monde du mod. La racine carrée de 1 dans le monde mod est $ x $ qui satisfait la congruence suivante pour deux ou plusieurs nombres naturels $ n $.
x^2 \equiv 1 \pmod{n}
Évidemment $ x = 1, n-1 $ satisfait cette équation, nous les appelons donc ** racines carrées évidentes ** et les autres ** racines carrées non évidentes **.
Considérez la racine carrée non triviale. Considérons donc le cas où $ x $ n'est ni $ 1 $ ni $ n-1 $. Par exemple, lorsque $ n = 15 $, $ x = 4, 11 $ est une racine carrée non triviale.
\begin{aligned}
(4)^2 &= 16 \equiv 1 \pmod{15}\\
(11)^2 &= 121 \equiv 1 \pmod{15}
\end{aligned}
Mais que faire si $ n $ est un nombre premier? En fait, à ce moment ** il n'y a pas de racine carrée non triviale **. Montrons cela dans l'absurdité. Il existe maintenant un module de racine carrée non trivial, le nombre premier $ p $, que nous appelons $ x $. Autrement dit, $ x $ n'est ni $ 1 $ ni $ p-1 $,
x^2 \equiv 1 \pmod{p}
Rencontrer. En ce 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}
Et puisque $ p $ est un nombre premier, au moins un de $ (x + 1) $ et $ (x -1) $ est divisible par $ p $. Mais $ x $ n'est ni $ 1 $ ni $ p-1 $
\begin{aligned}
(x + 1) \not \equiv 0 \pmod{p}\\
(x - 1) \not \equiv 0 \pmod{p}
\end{aligned}
Ce sera. Autrement dit, $ (x + 1) $ et $ (x -1) $ ne sont pas divisibles par $ p $. Par conséquent, il a été montré qu'il n'y a pas de racine carrée non triviale modulo le nombre premier $ p $ en raison de l'incohérence.
1.6. Petit théorème de Fermat pour les nombres premiers impairs
Si le nombre naturel que vous voulez juger est 2, il est évident qu'il s'agit d'un nombre premier, alors supposons qu'il a été traité à l'avance. A ce moment, le nombre premier est toujours impair, alors considérons le petit théorème de Fermat pour le nombre premier impair $ p $. Maintenant que $ p-1 $ est pair, utilisez les nombres naturels $ s $ et les impairs $ d $
p - 1 = 2^s \cdot d
Peut être exprimé comme. Par conséquent, le théorème de Fermat est
a^{2^s \cdot d} \equiv 1 \pmod{p}
Et c'est
(a^{2^{s-1} \cdot d})^2 \equiv 1 \pmod{p}
Vous pouvez également le voir. Comme indiqué dans la section précédente, il n'y a pas de racine carrée non triviale de $ 1 $ modulo le premier $ p $, donc
\begin{aligned}
a^{2^{s-1} \cdot d} &\equiv \;\;\:1 \pmod{p}\\
a^{2^{s-1} \cdot d} &\equiv -1 \pmod{p}
\end{aligned}
Ce sera non plus. Si c'était le premier, alors $ s -1> 0 $
(a^{2^{s-2} \cdot d})^2 \equiv 1 \pmod{p}
On voit que c'est aussi
\begin{aligned}
a^{2^{s-2} \cdot d} &\equiv \;\;\:1 \pmod{p}\\
a^{2^{s-2} \cdot d} &\equiv -1 \pmod{p}
\end{aligned}
Ce sera non plus. Si vous répétez cela, un jour
\begin{aligned}
a^{d} &\equiv \;\;\:1 \pmod{p}\\
a^{d} &\equiv -1 \pmod{p}
\end{aligned}
Ce sera. Le résumé jusqu'à ce point est le suivant.
Lorsque $ p $ est un nombre premier impair, utilisez les nombres naturels $ s $ et les nombres impairs $ d $
p - 1 = 2^s \cdot d
Peut être écrit, et ** doit satisfaire l'une des expressions congruentes suivantes modulo $ p $ **.
\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}
Cette formule de congruence vaut au maximum $ \ log_2 {p} $, donc vérifions tout **.
À partir de ce qui précède, le test du nombre naturel $ n $ que vous souhaitez juger est le suivant.
-
Échec si $ n = 1 $
-
Passez si $ n = 2 $
-
Échec si $ n \ geq 3 $ est pair
-
Si $ n \ geq 3 $ est impair, alors $ n -1 = 2 ^ s \ cdot d $, et $ n $ comme loi pour un nombre naturel $ a $ qui s'exclut mutuellement avec $ n $.
\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}
Réussir si vous en rencontrez au moins un, échouez si vous n'en rencontrez aucun
La méthode de détermination probabiliste de la prime utilisant ce test est appelée ** méthode de détermination de la prime de Mirror-Rabin **.
1.7. Comment mettre en œuvre le test
Organisez les jugements pour des $ n $ impairs de 3 ou plus. Puisque la méthode probabiliste de jugement des nombres premiers teste avec plusieurs bases et juge qu'il s'agit d'un nombre premier uniquement lorsque tous réussissent, il suffit de détecter le cas d'échec dans le processus de test. Disons maintenant $ n -1 = 2 ^ s \ cdot d $ et le bas du test est $ a $. A ce moment, $ a ^ {2 ^ rd} $ est calculé pour $ r $ tel que $ 0 \ leq r <s $. Premièrement, quand $ r = 0 $
a^d \equiv 1\; or\; -1 \pmod{n}
Si tel est le cas, le test pour les $ a $ inférieurs est terminé. Sinon, pour $ r = 1, 2, \ cdots, s-1 $
a^{2^rd} \not \equiv 1\; or\; -1 \pmod{n}
Calculez aussi longtemps que. De plus, la condition de terminaison $ r <s $ pour $ r $ correspond à $ 2 ^ rd <n -1 $. Si $ a ^ {2 ^ rd} \ equiv -1 \ pmod {n} $, le test de la base $ a $ est terminé. Mais que faire si cela devient $ a ^ {2 ^ rd} \ equiv 1 \ pmod {n} $? Pour le moment, il a déjà été confirmé que $ a ^ {2 ^ {r-1} d} $ n'est ni $ 1 $ ni $ -1 $, donc $ a ^ {2 ^ {r-1} d} $ est La racine carrée non triviale de $ 1 $. Par conséquent, $ n $ n'est pas un nombre premier et sera rejeté. De plus, si c'est $ a ^ {2 ^ rd} \ not \ equiv 1 ; ou ; -1 \ pmod {n} $ jusqu'à la fin, il sera rejeté. Ce qui précède est résumé dans la figure ci-dessous.
1.8. Comment choisir le fond
Dans la méthode de jugement des nombres premiers miroir-Rabin, le nombre de bases est généralement décidé par soi-même, et un nombre naturel $ a $ tel que $ a <n $ est sélectionné ** au hasard et utilisé comme base. Puisqu'il existe un compromis entre la vitesse de calcul et la précision du jugement, il est souhaitable d'avoir le moins de bases possible tout en garantissant la précision requise. Par conséquent, des combinaisons de fond qui peuvent améliorer efficacement la précision ont été étudiées. ACL utilise $ a = \ {2, 7, 61 } $ comme base. Selon [Jaeschke (1993)] min_2_7_61, le nombre minimum de composites qui réussissent tout ce test de fond est de 4759123141 $ ; (= 48781 \ cdot 97561> 2 ^ {32}) $. Par conséquent, dans la plage de $ n <2 ^ {32} $ (plage d'entiers non signés de 4 octets), il peut être jugé avec une précision de 100 $ % $.
1.9. Mise en œuvre
Implémentons-le. La partie qui utilise pow_mod dans ACL est remplacée par la fonction intégrée Python pow, qui est une fonction équivalente.
def is_prime(n):
#Partie évidente
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 est étrange
while (d % 2 == 0): d //= 2 #Trouvez le d impair
for a in (2, 7, 61):
t = d #Maintenez d car il est également utilisé à d'autres fonds
y = pow(a, t, n)
# a^d = 1, -S'il vaut 1, cette boucle n'entrera pas
# a^t = 1, -Répétez jusqu'à 1
while (t != n - 1 and y != 1 and y != n - 1):
y = y * y % n
t <<= 1
# a^d = 1, -1 passe(t%2 == 0)
# a^t = -1 passe(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 est l'un des nombres Carmichael)
#bas{2, 7, 61}Nombre minimum de composites qui réussissent le test
print(is_prime(4759123141)) # True
1.10. Comparaison de la vitesse de calcul
Comparons-le avec la méthode définitive de jugement des nombres premiers du montant de calcul du temps $ O (\ sqrt {n}) $. Le code utilisé pour la comparaison est ci-dessous.
import random
#miroir-Méthode de jugement des nombres premiers de Rabin (méthode de jugement des nombres premiers probabilistes)
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
#Méthode de jugement définitif des nombres premiers
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) #Nombre aléatoire fixe
loop = 10000 #Nombre de boucles 10^4 or 10^6
for _ in range(loop):
n = random_1()
#n = random_2()
#n = random_3()
pro_is_prime(n) #Probabiliste
#det_is_prime(n) #Définitive
if __name__ == "__main__":
main()
Méthode de mesure
J'ai utilisé le test de code d'AtCoder (Python 3.8.2). Des nombres aléatoires ont été générés à partir de 3 types de plage avec 10 types de valeurs de départ, et le temps d'exécution pour 10 000 jugements principaux a été étudié. Dans le cas d'un nombre pair, les deux sont traités en premier, donc seul un nombre impair est utilisé.
- random_1
- Plage aléatoire: $ [3, 2 ^ {16}] $ impair
- Nombre de boucles: 10 $ ^ 4, 10 ^ 6 $ (Parce que 10 $ ^ 4 $ peuvent être les principaux frais généraux tels que l'importation)
- random_2
- Plage de nombres aléatoires: $ [2 ^ {16}, 2 ^ {32}] $ impair
- Nombre de boucles: 10 $ ^ 4 $
- random_3
- Plage aléatoire: $ [3, 2 ^ {32}] $ impair
- Nombre de boucles: 10 $ ^ 4 $
Résultat de la mesure
Le résultat est illustré dans la figure ci-dessous. La valeur numérique est le temps pour 10 000 jugements premiers, et l'unité est la ms.
| miroir-Rabin | Méthode de jugement définitif des nombres premiers | |
|---|---|---|
| random_1(10^4) | 63 | 59 |
| random_1(10^6) | 34 | 30 |
| random_2 | 100 | 4060 |
| random_3 | 99 | 4113 |
Si le nombre que vous voulez juger est aussi petit que 10 $ ^ 5 $, la méthode de jugement définitif des nombres premiers semble être légèrement plus rapide. Cependant, à mesure que le nombre augmente, la supériorité de la méthode de détermination du nombre premier miroir-rabin devient remarquable.
- primitive_root Trouvez la plus petite des racines primitives modulo le premier $ m $.
2.1. Numéro
Examinons d'abord le terme important «nombre» pour expliquer les racines primitives. La définition est la suivante.
Pour les nombres naturels $ m $ et $ m $ de 2 ou plus et les entiers $ a $ qui s'excluent mutuellement
a^{n} \equiv 1 \pmod{m}
Le plus petit nombre naturel $ n $ est appelé la fraction ** de $ a $ modulo ** $ m $.
Regardons un exemple concret. Lorsque $ m = 5, 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}
Ainsi, la fraction de 3 $ modulo $ 5 $ est de 4 $. Aussi, quand $ m = 12, a = 5 $,
\begin{aligned}
5^1 &= 2 & \not \equiv 1 \pmod{12}\\
5^2 &= 25 & \equiv 1 \pmod{12}
\end{aligned}
Ainsi, la fraction de 5 $ modulo $ 12 $ est de 2 $.
La nature du grade
La fraction $ e $, qui est un entier $ a $ qui est mutuellement exclusif à $ m $, modulo $ m $, a les propriétés suivantes pour l'entier positif $ n $.
a^n \equiv 1 \pmod{m} \Leftrightarrow e\;Est\;n\;Approximativement
(Preuve)
\begin{aligned}
a^n &=a^{ke}\\
&= (a^e)^k\\
&\equiv 1
\end{aligned}
Et établi.
\begin{aligned}
a^r &\equiv (a^{e})^qa^r\\
&\equiv a^{qe+r}\\
&\equiv 1
\end{aligned}
Sera. Si $ 0 <r <e $, alors cela contredit le fait que $ e $ est un chiffre (le chiffre est un ** entier ** minimum qui satisfait $ a ^ e \ equiv 1 \ pmod {m} $). Donc $ r = 0 $, c'est-à-dire que $ e $ est une fraction de $ n $.
(Fin de la certification)
Surtout quand $ m $ est un nombre premier, l'ordre est une fraction de $ m -1 $ selon le théorème de Fermat.
2.2. Racine primitive
Prenons le cas où $ m $ est un nombre premier. D'après le théorème de Fermat, l'ordre de $ m $ et l'entier mutuellement premier $ a $, modulo $ m $, est toujours inférieur ou égal à $ m -1 $. Par conséquent, nous accordons une attention particulière à $ a $ dont l'ordre est exactement $ m -1 $, et l'appelons une racine primitive ** modulo $ m $ **.
Par exemple, lorsque $ 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}
Ainsi, la fraction de 3 $ modulo $ 7 $ est de 6 $. Donc $ 3 $ est un modulo racine primitif $ 7 $. Il n'y a pas toujours une racine primitive. A partir du premier exemple montré à la place des chiffres, nous pouvons voir que $ 3 $ est une racine primitive modulo $ 5 $. Par contre, quand $ 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}
Donc $ 2 $ est aussi un modulo racine primitif $ 5 $.
Notez qu'une racine primitive existe toujours lorsque $ m $ est un nombre premier. Veuillez vérifier la preuve avec "Théorème racine primitif".
Nature de la racine primitive
La racine primitive $ g $ modulo le premier $ m $ a les propriétés suivantes:
Un ensemble de puissances de $ g $ modulo $ m $
\{g\pmod{m}, g^2\pmod{m}, \cdots , g^{m - 1}\pmod{m}\}
Et l'entier divisé par $ m $, moins $ 0 $
\{1, 2, \cdots , m - 1\}
Rencontre.
Cela peut être paraphrasé comme suit: À propos du nombre naturel $ k $ de $ 1 \ leq k \ leq m-1 $
g^k \not \equiv 0 - $ g ^ k $ sont tous différents.
Le premier est clair du fait que $ g $ et $ m $ sont mutuellement exclusifs. Par conséquent, je vais prouver le deuxième.
(Preuve) Supposons maintenant qu'il existe un nombre naturel $ k, l $ tel que $ k <l \ leq m --1 $, et que ce soit $ g ^ k \ equiv g ^ l \ pmod {m} $. En ce 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}
Ce sera. Puisque $ l --k <m --1 $, l'ordre de la racine primitive $ g $ est incompatible avec $ m-1 $. Donc pour $ 1 \ leq k \ leq m-1 $, $ g ^ k $ est tout différent. (Fin de la certification)
2.3. Comment vérifier s'il s'agit d'une racine primitive 1
Pour déterminer si un nombre naturel $ g $ de 2 ou plus est une racine primitive modulo $ m $, $ g, g ^ 2, \ cdots, modulo $ m $ à partir de la définition de la racine primitive Assurez-vous que g ^ {m --2} $ n'est pas entièrement congruente avec $ 1 $. Par conséquent, l'implémentation de l'algorithme pour trouver la plus petite racine primitive est la suivante.
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)) #Très chronophage
Cette méthode vérifie toutes les puissances de $ g $ jusqu'à $ m - 2 $, donc cela prend beaucoup de temps à mesure que $ m $ grandit.
2.4. Comment vérifier s'il s'agit d'une racine primitive 2
En fait, il est plus facile de confirmer s'il s'agit d'une racine primitive en utilisant les propriétés de la racine primitive. Les propriétés utilisées sont:
En utilisant le premier $ p_i $ et le naturel $ e_i $, $ m-1 $ est pour un premier $ m $ supérieur ou égal à $ 3 $.
m-1 = \prod_{i = 1}^n{p_i^{e_i}}
Lorsqu'il est factorisé en facteurs premiers, ce qui suit vaut pour les nombres naturels $ g $ supérieurs à 2 $ $.
g\;Mais\;m\;Racines primitives
\Leftrightarrow 1 \leq i \leq n\;Contre\; g^{\frac{m-1}{p_i}}\not\equiv 1 \pmod{m}
(Preuve)
g n'est pas une racine primitive\Rightarrow g^{\frac{m-1}{p_i}}\equiv 1 \pmod{m}Il existe je
Alors je vais montrer ça. Or $ g $ n'est pas une racine primitive, donc l'ordre $ e $ est inférieur à $ m-1 $. Comme le montre la nature des chiffres, $ e $ est une fraction de $ m-1 $, utilisez donc $ p_i $, qui est le même que le facteur premier de $ m-1 $.
e = \prod_{j = 1}^n{p_j^{e_j^{\prime}}}\;\;\;(e_j^{\prime} \leq e_j)
En particulier, il existe au moins un $ j $ tel que $ e_j ^ {\ prime} <e_j $. Soit un de ces $ j $ $ i $. En ce 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}
Ici, $ e_i --e_i ^ {\ prime} --1 \ geq 0 $ et $ e_j --e_j ^ {\ prime} \ geq 0 $
\frac{m-1}{p_i} = (Entier naturel) \times e
Sera. Donc si $ g $ n'est pas une racine primitive
g^{\frac{m-1}{p_i}} \equiv \left(g^e\right)^{Entier naturel} \equiv 1 \pmod{m}
Il existe $ i $.
(Fin de la certification)
De ce qui précède
- Trouvez le facteur premier de $ m-1 $.
- Pour chaque facteur premier $ p_i $, vérifiez s'il devient $ g ^ {\ frac {m-1} {p_i}} \ not \ equiv 1 \ pmod {m} $.
Vous pouvez déterminer si $ g $ est une racine primitive en suivant la procédure.
2.5. Mise en œuvre
Implémentons-le. Comme is_prime, pow_mod est remplacé par la fonction intégrée pow.
# @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-Extraction de facteur premier de 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)
#Trouvez le plus petit g qui n'est pas congru avec 1 dans tous les facteurs premiers
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
Les premiers $ m $ à déterminer semblent être les mods utilisés en convolution.
3. Conclusion
Cette fois, nous avons examiné la méthode de jugement des nombres premiers et les racines primitives. J'ai trouvé l'idée de la méthode probabiliste de jugement des nombres premiers particulièrement intéressante.
Parmi les internal_math, ceux que je n'ai pas abordés cette fois sont écrits dans [internal_math edition ①] qiita_internal_math_1, veuillez donc vous y référer également.
Veuillez nous faire savoir si vous avez des erreurs, des bugs ou des conseils.
Recommended Posts