La dernière fois, j'ai implémenté un anneau entier après avoir créé une classe de base abstraite pour les monoïdes, les groupes et les anneaux. Cette fois, après avoir créé la classe de base abstraite du champ, nous implémenterons le champ de nombres rationnels, l'anneau de classe de reste et le corps fini.
Le corps est un ensemble qui remplit les conditions suivantes
- Un anneau autour du multiplicateur $ \ star $ et de l'additif $ \ oplus $
- Les ensembles autres que l'élément unitaire additif $ 0 $ forment un groupe pour le multiplicateur $ \ star $
Si vous remplacez ceci par un mot familier,
- Il y a $ 1 $ et $ 0 $, et vous pouvez effectuer trois opérations: addition, soustraction et multiplication.
- Les éléments autres que $ 0 $ ont un élément inverse multiplicateur, c'est-à-dire qu'ils peuvent être divisés par des éléments autres que $ 0 $
En d'autres termes, c'est un ensemble qui autorise quatre règles de fonctionnement (addition, soustraction, multiplication et division).
Lors de l'implémentation d'une classe, héritez des groupes et des anneaux créés jusqu'à présent, et retournez True si c'est $ 0 $ uniquement lors de l'exécution du test inverse.
FieldType = TypeVar("FieldType", bound="Field")
class Field(Group, Ring):
def testInverse(self: FieldType) -> bool:
if self * self.identity() == super().zero():
return True
else:
return super().testInverse()
Maintenant, faisons un champ de nombres rationnels. Un nombre rationnel est un nombre qui peut être représenté sous la forme $ \ frac {p} {q} $ en utilisant les deux entiers $ p $ et $ q $. Par conséquent, gardez ces $ p $ et $ q $ dans l'instance de la classe de nombres rationnels.
Lorsque vous recherchez des fractions égales, la simple comparaison de $ p $ avec $ q $ pose des problèmes. En effet, le dénominateur peut différer en fonction de l'instance, même si les fractions sont identiques. Il y a deux façons possibles de gérer cela.
Vous pouvez le réduire en utilisant la méthode de division mutuelle euclidienne qui sera implémentée plus tard, mais ici nous utiliserons la méthode simple d'évaluation de $ ps = qr $. Fondamentalement, il s'agit du calcul des fractions apprises au primaire et au collège, il n'est donc pas nécessaire de l'expliquer en particulier.
class Rational(Field):
def __init__(self: "Rational", p: Integer, q: Integer = Integer(1)) -> None:
self.p = p
self.q = q
def __repr__(self: "Rational") -> str:
if self.q == self.q.identity():
return "%s" % self.p
return "%s/%s" % (self.p, self.q)
def __mul__(self: "Rational", x: "Rational") -> "Rational":
return Rational(self.p * x.p, self.q * x.q)
def __add__(self: "Rational", x: "Rational") -> "Rational":
return Rational(self.p * x.q + x.p * self.q, self.q * x.q)
def __eq__(self, x):
if not isinstance(x, Rational):
return NotImplemented
return self.p * x.q == x.p * self.q
def __neg__(self: "Rational") -> "Rational":
return Rational(-self.p, self.q)
def identity(self: "Rational") -> "Rational":
return Rational(self.p.identity(), self.p.identity())
def inverse(self: "Rational") -> "Rational":
return Rational(self.q, self.p)
def zero(self: "Rational") -> "Rational":
return Rational(self.p.zero(), self.p.identity())
Q = Rational
L'alias de «Rational» est «Q».
Maintenant, vérifions le fonctionnement des nombres rationnels.
a = Q(Z( 8), Z(3))
b = Q(Z(-5), Z(4))
c = Q(Z( 3), Z(7))
y = a * b + c
print(y)
# -> -244/84
print(y.inverse())
# -> 84/-244
Ça a marché.
Pour le moment, la réduction n'est pas mise en œuvre, mais elle peut être réduite au moment de l'affichage en utilisant la méthode de division mutuelle euclidienne décrite plus loin.
Python a une classe fractions.Fraction pour exprimer des fractions. Si vous souhaitez simplement travailler avec des fractions, cette classe suffira.
from fractions import Fraction
a = 0
for i in range(10):
a += 1/10
print(a == 1)
# -> False
a = 0
for i in range(10):
a += Fraction(1, 10)
print(a == 1)
# -> True
Un exemple de logiciel qui utilise «Fraction» est l'interface Python du logiciel de conversion vidéo FFMPEG, PyAV. Nous utilisons des fractions pour calculer la fréquence d'images.
À partir de maintenant, il y aura plus d'opportunités pour la division par troncature et les restes. Par conséquent, il serait commode de créer une classe de base abstraite pour l'anneau euclidien sous la forme d'un «anneau qui peut être tronqué et divisé et le reste peut être obtenu».
EuclidianRingType = TypeVar("EuclidianRingType", bound="EuclidianRing")
class EuclidianRing(Ring, metaclass=ABCMeta):
@abstractmethod
def __floordiv__(self: EuclidianRingType, x: EuclidianRingType) -> EuclidianRingType:
pass
@abstractmethod
def __mod__(self: EuclidianRingType, x: EuclidianRingType) -> EuclidianRingType:
pass
Remplacez ensuite la classe parente de ʻInteger from Ring par ʻEuclidianRing pour définir la division de troncature et le reste.
class Integer(EuclidianRing):
# ~~ snip ~~
def __floordiv__(self: "Integer", x: "Integer") -> "Integer":
return Integer(self.v // x.v)
def __mod__(self: "Integer", x: "Integer") -> "Integer":
return Integer(self.v % x.v)
Pour les entiers $ a $, $ b $ et le nombre naturel $ n $, quand $ a --b = n \ mathbb {Z} $ ($ \ mathbb {Z} $ est un entier arbitraire) est valable, "$ a $ et $ b $ est congruente avec $ n $ comme loi », dit $ a \ equiv b \ pmod n $. Un ensemble qui traite deux de ces nombres comme étant identiques est appelé un «module d'anneau excédentaire $ n $».
Maintenant, implémentons la classe d'anneau de classe restante ModRing.
Une instance de la classe d'anneau restante contient $ a $ et la loi $ n $. Assurez-vous que $ a $ et $ n $ acceptent des anneaux euclidiens arbitraires, pas seulement des entiers. De plus, puisque nous voulons que $ a $ soit le plus petit nombre congru de 0 ou plus lors de l'affichage à l'écran, nous calculerons $ a \ bmod n $ lors de la création de l'instance.
Ensuite, vous devez rendre impossible le calcul des nombres avec différentes méthodes. Pour cette raison, ModRing devrait être la classe de base pour tous les anneaux de classe résiduels, et des sous-classes devraient être créées pour chaque méthode différente. Cela permet à la vérification de type d'échouer si vous essayez de calculer des nombres avec différentes méthodes. De plus, définissez __init__ sur @ abstractmethod afin que ModRing lui-même ne puisse pas être instancié.
ModRingType = TypeVar("ModRingType", bound="ModRing")
ModRingBaseType = TypeVar("ModRingBaseType", bound="EuclidianRing")
class ModRing(Ring, metaclass=ABCMeta):
@abstractmethod
def __init__(self: ModRingType, a: ModRingBaseType, n: ModRingBaseType) -> None:
self.a = a % n
self.n = n
def __repr__(self: ModRingType) -> str:
return "%s (mod %s)" % (str(self.a), str(self.n))
def __mul__(self: ModRingType, x: ModRingType) -> ModRingType:
return self.__class__(self.a * x.a)
def __add__(self: ModRingType, x: ModRingType) -> ModRingType:
return self.__class__(self.a + x.a)
def __neg__(self: ModRingType) -> ModRingType:
return self.__class__(-self.a)
def __eq__(self, x):
if not isinstance(x, self.__class__):
return NotImplemented
return self.a == x.a
def identity(self: ModRingType) -> ModRingType:
return self.__class__(self.a.identity())
def zero(self: ModRingType) -> ModRingType:
return self.__class__(self.a.zero())
En définissant self .__ class__ dans chaque méthode, vous pouvez faire référence à une instance d'une classe enfant avec un diviseur, pas à la classe restante.
Par exemple, pour créer une classe d'anneau de reste avec un diviseur de 5, procédez comme suit:
class ModRing_5(ModRing):
def __init__(self, a: Integer) -> None:
super().__init__(a, Integer(5))
Maintenant, vérifions le fonctionnement de l'anneau de reste.
Le premier est le calcul des nombres avec différentes méthodes.
mr_3_5 = ModRing_5(Z(3))
mr_2_4 = ModRing_4(Z(2))
print(mr_3_5 + mr_2_4)
$ mypy ./field_extension.py
field_extension.py:238: error: Unsupported operand types for + ("ModRing_5" and "ModRing_4")
J'ai eu une erreur dans mypy. Si la méthode est la même, aucune erreur ne se produira et le calcul peut être effectué sans problème.
mr_3_5 = ModRing_5(Z(3))
mr_4_5 = ModRing_5(Z(4))
print(mr_3_5 + mr_4_5) # -> 2 (mod 5)
Parmi les anneaux, les éléments autres que $ 0 $ ont un élément inverse multiplicateur, c'est-à-dire que celui qui remplit les conditions suivantes est appelé un corps.
$ x \ star x ^ {-1} = x ^ {-1} \ star x = e $ existe $ x ^ {-1} $
Lorsqu'il est appliqué à l'anneau de classe du reste, trouver l'entier $ p $ qui satisfait l'équation suivante pour $ a \ pmod n $ est l'élément inverse.
D'après la définition congruente ci-dessus, en utilisant l'entier $ q $
La somme (différence) d'un multiple de $ a $ et d'un multiple de $ n $ est un multiple de l'engagement maximal $ GCD (a, n) $ de $ a $ et $ n $. C'est ce qu'on appelle l'équation de Bezoo. Autrement dit, $ GCD (a, n) = 1 $ (élémentaire l'un à l'autre).
Tout $ a $ inférieur à $ n $ et $ n $ qui sont premiers l'un par rapport à l'autre sont des nombres premiers, donc si $ n $ est un nombre premier, alors l'anneau de classe du reste est le champ. C'est ce qu'on appelle un corps fini car c'est un corps composé d'un nombre fini d'éléments.
Vous pouvez utiliser la méthode de division mutuelle euclidienne pour trouver un ensemble d'entiers $ p $, $ q $ et $ r $ qui satisfont l'équation de Bezu $ a p + b q = r = GCD (a, b) $.
La méthode de division mutuelle euclidienne peut être effectuée dans l'anneau euclidien. Cela amène la classe d'anneau euclidienne à implémenter la méthode de division mutuelle euclidienne.
Dans l'indice de type, s'il y a un taple dans l'argument ou la valeur de retour de la fonction, utilisez typing.Tuple et spécifiez le type de chaque élément entre crochets.
from typing import Tuple
EuclidianRingType = TypeVar("EuclidianRingType", bound="EuclidianRing")
class EuclidianRing(Ring, metaclass=ABCMeta):
# ~~ snip ~~
def euclid_gcd(self: EuclidianRingType, b: EuclidianRingType) -> Tuple[EuclidianRingType, EuclidianRingType, EuclidianRingType]:
a = self
p = a.zero()
q = a.identity()
p_1 = a.identity()
q_1 = a.zero()
while True:
c = a % b
if c == c.zero():
break
p_2 = p_1
q_2 = q_1
p_1 = p
q_1 = q
p = p_2 - p_1 * (a // b)
q = q_2 - q_1 * (a // b)
a = b
b = c
return (p, q, b)
Maintenant que nous avons implémenté la méthode de division mutuelle euclidienne, réduisons-la avec le nombre rationnel __init__.
class Rational(Field):
def __init__(self: "Rational", p: Integer, q: Integer = Integer(1)) -> None:
_, _, r = p.euclid_gcd(q)
self.p = p // r
self.q = q // r
Maintenant, créons une classe de corps finie. La classe du corps fini hérite de ModRing et définit la méthode ʻinverse. Le $ n $ fini doit être un nombre premier, mais comme il est difficile de déterminer exactement qu'il s'agit d'un nombre premier, nous ne le vérifions pas lors de la création d'une instance, et nous ne nous vérifions pas les uns les autres en ʻinverse. Je vais vérifier si c'est le cas.
FiniteFieldType = TypeVar("FiniteFieldType", bound="FiniteField")
class FiniteField(Field, ModRing, metaclass=ABCMeta):
def inverse(self: FiniteFieldType) -> FiniteFieldType:
p, q, r = self.a.euclid_gcd(self.n)
if r == r.identity():
return self.__class__(p)
raise Exception("a and n are not co-prime")
Testons-le.
class FiniteField_11(FiniteField):
def __init__(self, a: Integer) -> None:
super().__init__(a, Integer(11))
ff_5_11 = FiniteField_11(Z(5))
print(ff_5_11.inverse())
# -> 9 (mod 11)
Puisque $ 5 \ times 9 = 45 \ equiv 1 \ pmod {11} $, l'inverse de la multiplication de 5 $ \ pmod {11} $ est certainement $ 9 \ pmod {11} $.
La prochaine fois, nous définirons un anneau polypoly et appliquerons les classes ModRing et FiniteField, qui étaient basées uniquement sur des entiers cette fois, aux polynômes. Et enfin, nous élargirons le champ des nombres rationnels.
Recommended Posts