Modular multiplicative inverse (original) (raw)
في الحسابيات النمطية، مقلوب عدد نمطي أو معاكس ضربي نمطي (بالإنجليزية: Modular multiplicative inverse) لعدد صحيح a بتردد عدد طبيعي m هو عدد صحيح x حيث: هناك مقلوب ضربي واحد فقط إذا كان العددان و أوليين فيما بينهما، بمعنى أن قاسمهما المشترك الأكبر يساوي واحدا. أي . يعبر أيضاً عن هذا العدد ، إن وجد، بالرمز دلالةً على أنه المقلوب للعدد في المتطابقة السابقة.
| Property | Value |
|---|---|
| dbo:abstract | في الحسابيات النمطية، مقلوب عدد نمطي أو معاكس ضربي نمطي (بالإنجليزية: Modular multiplicative inverse) لعدد صحيح a بتردد عدد طبيعي m هو عدد صحيح x حيث: هناك مقلوب ضربي واحد فقط إذا كان العددان و أوليين فيما بينهما، بمعنى أن قاسمهما المشترك الأكبر يساوي واحدا. أي . يعبر أيضاً عن هذا العدد ، إن وجد، بالرمز دلالةً على أنه المقلوب للعدد في المتطابقة السابقة. (ar) En la aritmética modular, el inverso multiplicativo de un número entero n módulo p es otro entero m (módulo p) tal que el producto mn es congruente con 1 (módulo p). Esto significa que tal número m es el inverso multiplicativo en el anillo de los enteros módulo p, es decir, n-1 ≡ m (mod p). Se habla de inverso multiplicativo para distinguirlo del elemento inverso, tal y como es entendido en teoría de grupos. El inverso multiplicativo de n módulo p existe si y solo si n y p son coprimos, es decir, si mcd(n, p)=1. Si existe el inverso multiplicativo de un número n módulo p, entonces se puede definir la operación de división de cualquier otro número entre n módulo p, mediante la multiplicación de ese número por el inverso n-1. Si p es un número primo, entonces todos los números excepto el cero (y sus congruentes —los múltiplos de p) son invertibles, lo que convierte al anillo de los enteros módulo p en un cuerpo. (es) Biderketarekiko alderantzizko modularra aritmetika modularrareko eragiketa bat da. zenbaki oso baten biderketarekiko alderantzizkoa modulu beste zenbaki oso bat da non: hau da, biderketa 1-arekin kongruentea den (modulu ). zenbakia zenbakiaren alderantzizkoa modulu dela horrela adierazten da: Biderketarekiko alderantzizko modularra ez da beti existitzen. -ren alderantzizko modularra existitzen da baldin eta soilik baldin eta elkarrekiko lehenak badira, hau da, bada. zenbakiaren alderantzizkoa modulu existitzen denean, orduan beste zenbaki bat balioaz zatitzearen eragiketa (modulu ) defini daiteke; zenbaki bat balioaz zatitzea alderantzizko modularraz biderkatzea da. zenbaki lehena bada, orduan zenbaki guztiak dira alderantzikagarriak, -a izan ezik. (eu) In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. In the standard notation of modular arithmetic this congruence is written as which is the shorthand way of writing the statement that m divides (evenly) the quantity ax − 1, or, put another way, the remainder after dividing ax by the integer m is 1. If a does have an inverse modulo m, then there are an infinite number of solutions of this congruence, which form a congruence class with respect to this modulus. Furthermore, any integer that is congruent to a (i.e., in a's congruence class) has any element of x's congruence class as a modular multiplicative inverse. Using the notation of to indicate the congruence class containing w, this can be expressed by saying that the modulo multiplicative inverse of the congruence class is the congruence class such that: where the symbol denotes the multiplication of equivalence classes modulo m.Written in this way, the analogy with the usual concept of a multiplicative inverse in the set of rational or real numbers is clearly represented, replacing the numbers by congruence classes and altering the binary operation appropriately. As with the analogous operation on the real numbers, a fundamental use of this operation is in solving, when possible, linear congruences of the form Finding modular multiplicative inverses also has practical applications in the field of cryptography, i.e. public-key cryptography and the RSA algorithm. A benefit for the computer implementation of these applications is that there exists a very fast algorithm (the extended Euclidean algorithm) that can be used for the calculation of modular multiplicative inverses. (en) En mathématiques et plus précisément en arithmétique modulaire, l'inverse modulaire d'un entier relatif pour la multiplication modulo est un entier satisfaisant l'équation : En d'autres termes, il s'agit de l'inverse dans l'anneau des entiers modulo n, noté ℤ/nℤ ou ℤn. Une fois ainsi défini, peut être noté , étant entendu implicitement que l'inversion est modulaire et se fait modulo . La définition est donc équivalente à : L'inverse de a modulo existe si et seulement si et sont premiers entre eux, (c.-à-d. si PGCD(a, n) = 1). Si cet inverse existe, l'opération de division par modulo équivaut à la multiplication par son inverse. (fr) 合同算術におけるモジュラ逆数（モジュラぎゃくすう、英: modular multiplicative inverse）は、与えられた整数 a と法 m に関して という関係にある整数 x の属する合同類（あるいはその標準的な代表元）をいう。即ち、整数の法 m に関する合同類環 における乗法逆元である。この式は と書いても同じである。ある種の応用においては、モジュラ逆数 x が に属さないような場合を考えることもある。 a の m を法とする逆数が存在するための必要十分条件は a と m とが互いに素（即ち、最大公約数 gcd(a, m) が 1）となることである。法 m に関する a のモジュラ逆数が存在するならば、m を法とした a による除法（「余り付き除法」ではない）を、モジュラ逆数を掛けることとして定義することができる。 (ja) Обратное по модулю целого a — это такое целое число x, что произведение ax сравнимо с 1 по модулю m. В стандартных обозначениях модульной арифметики эта эквивалентность записывается как: что является сокращённым способом записи утверждения, что m делит (без остатка) величину ax − 1, или, выражаясь другим способом, остаток от деления ax на целое m равен 1. Если a имеет обратный по модулю m, то имеется бесконечное количество решений этой эквивалентности, которые образуют класс вычетов для этого модуля. Более того, любое целое, которое эквивалентно a (то есть из класса эквивалентности a) будет иметь любой элемент класса эквивалентности x в качестве обратного элемента. Используя обозначения для класса эквивалентности, содержащего , утверждение выше может быть записано следующим образом: обратный элемент по модулю класса эквивалентности есть класс эквивалентности , такой что где символ означает умножение классов эквивалентности по модулю m. Такой вид записи представляет аналог обычной концепции обратного числа в множестве рациональных или вещественных чисел, если заменить числа классами эквивалентности и должным образом определения бинарных операций. Фундаментальное использование этой операции — решение линейной эквивалентности вида: Нахождение модульного обратного имеет практическое приложение в области криптографии, например, криптосистема с открытым ключом и алгоритм RSA . Преимущество для реализации этих приложений в том, что существует очень быстрый алгоритм (расширенный алгоритм Евклида), который может быть использован для вычисления модульных обратных. (ru) 模反元素也称为模倒数，或者模逆元。 一整数a對同餘n之模反元素是指滿足以下公式的整數 b 也可以寫成以下的式子 或者 整数 a 對模数 n 之模反元素存在的充分必要條件是 a 和 n 互質，若此模反元素存在，在模数 n 下的除法可以用和對應模反元素的乘法來達成，此概念和實數除法的概念相同。 (zh) Обернене за модулем щодо цілого число a за модулем m — це ціле x, таке що Тобто, це обернене число в кільці цілих за модулем m. Тотожно до Обернене за модулем число щодо a по модулю m існує, якщо a і m взаємно прості (тобто, якщо НСД(a, m) = 1). Якщо обернене за модулем число щодо a по модулю m існує, операцію ділення на a за модулем m можна визначити як множення на обернене, яке по суті є тією самою концепцією, що і ділення в полі дійсних чисел. Часто його знаходять за допомогою розширеного алгоритму Евкліда. (uk) |
| dbo:wikiPageExternalLink | http://www.math.utah.edu/~fguevara/ https://www.math.utah.edu/~fguevara/ACCESS2013/Euclid.pdf |
| dbo:wikiPageID | 9815338 (xsd:integer) |
| dbo:wikiPageLength | 24605 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1079780574 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Binary_relation dbr:Curve25519 dbr:Unit_(ring_theory) dbr:Inversive_congruential_generator dbr:Multiplicative_inverse dbr:Cryptography dbr:Mathematics dbr:Greatest_common_divisor dbr:Modular_arithmetic dbr:Modular_exponentiation dbr:Congruence_relation dbr:Coprime_integers dbr:Parallel_computing dbr:Public-key_cryptography dbr:Prefix_sum dbr:Bézout's_identity dbc:Modular_arithmetic dbr:Well-defined dbr:Cyclic_group dbr:Equivalence_relation dbr:Euclidean_algorithm dbr:Euler's_theorem dbr:Euler's_totient_function dbr:Extended_Euclidean_algorithm dbr:Factorization dbr:Finite_field dbr:Isomorphism dbr:Ring_(mathematics) dbr:Group_(mathematics) dbr:Prime_number dbr:Arithmetic dbr:Abuse_of_notation dbc:Binary_operations dbr:Chinese_Remainder_Theorem dbr:Least_common_multiple dbr:Big_O_notation dbr:Binary_operation dbr:Montgomery_reduction dbr:Coprime dbr:If_and_only_if dbr:Integer dbr:Kloosterman_sum dbr:Order_(group_theory) dbr:RSA_(cryptosystem) dbr:Rational_number dbr:Real_number dbr:Side-channel_attack dbr:Reduced_residue_system dbr:Rational_reconstruction_(mathematics) dbr:Ring_with_a_unit dbr:Division_algorithm_for_integers dbr:Least_residue_system_modulo_m dbr:Complete_residue_system_modulo_m dbr:Binary_exponentiation |
| dbp:id | ModularInverse (en) |
| dbp:title | Modular Inverse (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Cite_book dbt:Main dbt:Math dbt:MathWorld dbt:Mvar dbt:Reflist dbt:Wikibooks dbt:Su dbt:Abs |
| dct:subject | dbc:Modular_arithmetic dbc:Binary_operations |
| rdfs:comment | في الحسابيات النمطية، مقلوب عدد نمطي أو معاكس ضربي نمطي (بالإنجليزية: Modular multiplicative inverse) لعدد صحيح a بتردد عدد طبيعي m هو عدد صحيح x حيث: هناك مقلوب ضربي واحد فقط إذا كان العددان و أوليين فيما بينهما، بمعنى أن قاسمهما المشترك الأكبر يساوي واحدا. أي . يعبر أيضاً عن هذا العدد ، إن وجد، بالرمز دلالةً على أنه المقلوب للعدد في المتطابقة السابقة. (ar) 合同算術におけるモジュラ逆数（モジュラぎゃくすう、英: modular multiplicative inverse）は、与えられた整数 a と法 m に関して という関係にある整数 x の属する合同類（あるいはその標準的な代表元）をいう。即ち、整数の法 m に関する合同類環 における乗法逆元である。この式は と書いても同じである。ある種の応用においては、モジュラ逆数 x が に属さないような場合を考えることもある。 a の m を法とする逆数が存在するための必要十分条件は a と m とが互いに素（即ち、最大公約数 gcd(a, m) が 1）となることである。法 m に関する a のモジュラ逆数が存在するならば、m を法とした a による除法（「余り付き除法」ではない）を、モジュラ逆数を掛けることとして定義することができる。 (ja) 模反元素也称为模倒数，或者模逆元。 一整数a對同餘n之模反元素是指滿足以下公式的整數 b 也可以寫成以下的式子 或者 整数 a 對模数 n 之模反元素存在的充分必要條件是 a 和 n 互質，若此模反元素存在，在模数 n 下的除法可以用和對應模反元素的乘法來達成，此概念和實數除法的概念相同。 (zh) Обернене за модулем щодо цілого число a за модулем m — це ціле x, таке що Тобто, це обернене число в кільці цілих за модулем m. Тотожно до Обернене за модулем число щодо a по модулю m існує, якщо a і m взаємно прості (тобто, якщо НСД(a, m) = 1). Якщо обернене за модулем число щодо a по модулю m існує, операцію ділення на a за модулем m можна визначити як множення на обернене, яке по суті є тією самою концепцією, що і ділення в полі дійсних чисел. Часто його знаходять за допомогою розширеного алгоритму Евкліда. (uk) Biderketarekiko alderantzizko modularra aritmetika modularrareko eragiketa bat da. zenbaki oso baten biderketarekiko alderantzizkoa modulu beste zenbaki oso bat da non: hau da, biderketa 1-arekin kongruentea den (modulu ). zenbakia zenbakiaren alderantzizkoa modulu dela horrela adierazten da: Biderketarekiko alderantzizko modularra ez da beti existitzen. -ren alderantzizko modularra existitzen da baldin eta soilik baldin eta elkarrekiko lehenak badira, hau da, bada. (eu) En la aritmética modular, el inverso multiplicativo de un número entero n módulo p es otro entero m (módulo p) tal que el producto mn es congruente con 1 (módulo p). Esto significa que tal número m es el inverso multiplicativo en el anillo de los enteros módulo p, es decir, n-1 ≡ m (mod p). Se habla de inverso multiplicativo para distinguirlo del elemento inverso, tal y como es entendido en teoría de grupos. (es) En mathématiques et plus précisément en arithmétique modulaire, l'inverse modulaire d'un entier relatif pour la multiplication modulo est un entier satisfaisant l'équation : En d'autres termes, il s'agit de l'inverse dans l'anneau des entiers modulo n, noté ℤ/nℤ ou ℤn. Une fois ainsi défini, peut être noté , étant entendu implicitement que l'inversion est modulaire et se fait modulo . La définition est donc équivalente à : (fr) In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. In the standard notation of modular arithmetic this congruence is written as where the symbol denotes the multiplication of equivalence classes modulo m.Written in this way, the analogy with the usual concept of a multiplicative inverse in the set of rational or real numbers is clearly represented, replacing the numbers by congruence classes and altering the binary operation appropriately. (en) Обратное по модулю целого a — это такое целое число x, что произведение ax сравнимо с 1 по модулю m. В стандартных обозначениях модульной арифметики эта эквивалентность записывается как: что является сокращённым способом записи утверждения, что m делит (без остатка) величину ax − 1, или, выражаясь другим способом, остаток от деления ax на целое m равен 1. Если a имеет обратный по модулю m, то имеется бесконечное количество решений этой эквивалентности, которые образуют класс вычетов для этого модуля. Более того, любое целое, которое эквивалентно a (то есть из класса эквивалентности a) будет иметь любой элемент класса эквивалентности x в качестве обратного элемента. Используя обозначения для класса эквивалентности, содержащего , утверждение выше может быть записано следующим образом: обрат (ru) |
| rdfs:label | مقلوب عدد نمطي (ar) Inverso multiplicativo (aritmética modular) (es) Biderketarekiko alderantzizko modular (eu) Inverse modulaire (fr) モジュラ逆数 (ja) 모듈러 역원 (ko) Modular multiplicative inverse (en) Обратное по модулю число (ru) 模反元素 (zh) Обернене за модулем число (uk) |
| owl:sameAs | freebase:Modular multiplicative inverse yago-res:Modular multiplicative inverse wikidata:Modular multiplicative inverse dbpedia-ar:Modular multiplicative inverse dbpedia-es:Modular multiplicative inverse dbpedia-eu:Modular multiplicative inverse dbpedia-fa:Modular multiplicative inverse dbpedia-fi:Modular multiplicative inverse dbpedia-fr:Modular multiplicative inverse dbpedia-he:Modular multiplicative inverse dbpedia-ja:Modular multiplicative inverse dbpedia-ka:Modular multiplicative inverse dbpedia-ko:Modular multiplicative inverse dbpedia-ru:Modular multiplicative inverse dbpedia-uk:Modular multiplicative inverse dbpedia-zh:Modular multiplicative inverse https://global.dbpedia.org/id/2YroB |
| prov:wasDerivedFrom | wikipedia-en:Modular_multiplicative_inverse?oldid=1079780574&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Modular_multiplicative_inverse |
| is dbo:wikiPageRedirects of | dbr:Discrete_inverse dbr:Modular_inverse dbr:Modular_reciprocal dbr:Multiplicative_modular_inverse |
| is dbo:wikiPageWikiLink of | dbr:Method_of_successive_substitution dbr:Inversive_congruential_generator dbr:Multiplicative_inverse dbr:Modular_arithmetic dbr:Modular_exponentiation dbr:Modulo_operation dbr:Coprime_integers dbr:Rolling_hash dbr:Zero-knowledge_proof dbr:Affine_cipher dbr:Euclidean_algorithm dbr:Euclidean_division dbr:Extended_Euclidean_algorithm dbr:Fermat's_little_theorem dbr:Hill_cipher dbr:Kaprekar_number dbr:Rader's_FFT_algorithm dbr:ElGamal_encryption dbr:Division_(mathematics) dbr:Fermat_quotient dbr:RSA_(cryptosystem) dbr:Finite_field_arithmetic dbr:Multiplicative_group_of_integers_modulo_n dbr:Paillier_cryptosystem dbr:Discrete_inverse dbr:Modular_inverse dbr:Modular_reciprocal dbr:Multiplicative_modular_inverse |
| is foaf:primaryTopic of | wikipedia-en:Modular_multiplicative_inverse |