рдЧреБрдгрд╛рддреНрдордХ рдкреНрд░рддрд┐рд▓реЛрдо рдХреНрдпрд╛ рд╣реЛрддрд╛ рд╣реИ?
рдХрд┐рд╕реА рд╕рдВрдЦреНрдпрд╛ рдХрд╛ рдЧреБрдгрд╛рддреНрдордХ рдкреНрд░рддрд┐рд▓реЛрдо рд╡рд╣ рдорд╛рди рд╣реЛрддрд╛ рд╣реИ рдЬрд┐рд╕рд╕реЗ рдЙрд╕реЗ рдЧреБрдгрд╛ рдХрд░рдиреЗ рдкрд░ рдкрд░рд┐рдгрд╛рдо 1 рдЖрддрд╛ рд╣реИред рдХрд┐рд╕реА рд╕рд╛рдорд╛рдиреНрдп рд╡рд╛рд╕реНрддрд╡рд┐рдХ рд╕рдВрдЦреНрдпрд╛ a рдХреЗ рд▓рд┐рдП рдпрд╣ рдкреНрд░рддрд┐рд▓реЛрдо рдмрд╕ рдЙрд╕рдХрд╛ рд╡реНрдпреБрддреНрдХреНрд░рдо \(1/a\) рд╣реЛрддрд╛ рд╣реИ тАФ рдЙрджрд╛рд╣рд░рдг рдХреЗ рддреМрд░ рдкрд░, 4 рдХрд╛ рдкреНрд░рддрд┐рд▓реЛрдо 0.25 рд╣реИ рдХреНрдпреЛрдВрдХрд┐ \(4 \times 0.25 = 1\)ред рд╢реВрдиреНрдп рдХрд╛ рдХреЛрдИ рдкреНрд░рддрд┐рд▓реЛрдо рдирд╣реАрдВ рд╣реЛрддрд╛, рдХреНрдпреЛрдВрдХрд┐ рд╢реВрдиреНрдп рд╕реЗ рдЧреБрдгрд╛ рдХрд░рдиреЗ рдкрд░ рдХрд┐рд╕реА рднреА рд╕рдВрдЦреНрдпрд╛ рдХрд╛ рдкрд░рд┐рдгрд╛рдо 1 рдирд╣реАрдВ рдмрди рд╕рдХрддрд╛ред
$$a^{-1} = \frac{1}{\text{Number (a)}}$$
рдореЙрдбреНрдпреВрд▓рд░ рдЗрдиреНрд╡рд░реНрд╕
рдореЙрдбреНрдпреВрд▓рд░ рдЕрдВрдХрдЧрдгрд┐рдд рдореЗрдВ, a (mod m) рдХрд╛ рдЧреБрдгрд╛рддреНрдордХ рдкреНрд░рддрд┐рд▓реЛрдо рд╡рд╣ рдкреВрд░реНрдгрд╛рдВрдХ x рд╣реЛрддрд╛ рд╣реИ рдЬреЛ 0 рд╕реЗ mтИТ1 рдХреА рд╕реАрдорд╛ рдореЗрдВ рд╣реЛ рдФрд░ рдЬрд┐рд╕рдХреЗ рд▓рд┐рдП \(a \cdot x \equiv 1 \pmod{m}\) рд╕рд╣реА рд╣реЛред рдпрд╣ рд╕рдВрдЦреНрдпрд╛ рд╕рд┐рджреНрдзрд╛рдВрдд (number theory) рдФрд░ рдХреНрд░рд┐рдкреНрдЯреЛрдЧреНрд░рд╛рдлреА (RSA, рд╣реИрд╢рд┐рдВрдЧ, рддреНрд░реБрдЯрд┐-рд╕реБрдзрд╛рд░ рдХреЛрдб) рдореЗрдВ рдмрд╛рд░-рдмрд╛рд░ рдХрд╛рдо рдЖрддрд╛ рд╣реИред рдореЙрдбреНрдпреВрд▓рд░ рдЗрдиреНрд╡рд░реНрд╕ рддрднреА рдореМрдЬреВрдж рд╣реЛрддрд╛ рд╣реИ рдЬрдм a рдФрд░ m рд╕рд╣рдЕрднрд╛рдЬреНрдп (coprime) рд╣реЛрдВ тАФ рдпрд╛рдиреА \(\gcd(a, m) = 1\) рд╣реЛред рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдЗрд╕реЗ рд╡рд┐рд╕реНрддрд╛рд░рд┐рдд рдпреВрдХреНрд▓рд┐рдбрд┐рдпрди рдПрд▓реНрдЧреЛрд░рд┐рдереНрдо (extended Euclidean algorithm) рдХреА рдорджрдж рд╕реЗ рдирд┐рдХрд╛рд▓рддрд╛ рд╣реИред
$$\text{Number (a)} \cdot a^{-1} \equiv 1 \pmod{\text{Modulus (m)}}$$
рдЗрд╕ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХреИрд╕реЗ рдХрд░реЗрдВ
рдЕрдкрдиреА рд╕рдВрдЦреНрдпрд╛ a рджрд░реНрдЬ рдХрд░реЗрдВред рдпрджрд┐ рдЖрдкрдХреЛ рд╕рд┐рд░реНрдлрд╝ рд╕рд╛рдзрд╛рд░рдг рд╡реНрдпреБрддреНрдХреНрд░рдо \(1/a\) рдЪрд╛рд╣рд┐рдП, рддреЛ рдореЙрдбреНрдпреВрд▓рд╕ рдХреЛ 0 (рдпрд╛ рдЦрд╛рд▓реА) рд╣реА рд░рд╣рдиреЗ рджреЗрдВред рдореЙрдбреНрдпреВрд▓рд░ рдЗрдиреНрд╡рд░реНрд╕ рдирд┐рдХрд╛рд▓рдиреЗ рдХреЗ рд▓рд┐рдП 1 рд╕реЗ рдмрдбрд╝рд╛ рдХреЛрдИ рдореЙрдбреНрдпреВрд▓рд╕ m рджрд░реНрдЬ рдХрд░реЗрдВ; рдХреИрд▓рдХреБрд▓реЗрдЯрд░ a рдХреЛ m рд╕реЗ рдореЙрдбреНрдпреВрд▓реЛ рдХрдо рдХрд░рдХреЗ рдЗрдиреНрд╡рд░реНрд╕ рд▓реМрдЯрд╛ рджреЗрдЧрд╛, рдпрд╛ рдпрджрд┐ a рдФрд░ m рдореЗрдВ рдХреЛрдИ рдЙрднрдпрдирд┐рд╖реНрда рдЧреБрдгрдирдЦрдВрдб рд╣реЛ рддреЛ рдмрддрд╛ рджреЗрдЧрд╛ рдХрд┐ рдХреЛрдИ рдЗрдиреНрд╡рд░реНрд╕ рдореМрдЬреВрдж рдирд╣реАрдВ рд╣реИред
рд╣рд▓ рдХрд┐рдпрд╛ рдЧрдпрд╛ рдЙрджрд╛рд╣рд░рдг
3 рдХрд╛ рдкреНрд░рддрд┐рд▓реЛрдо рдореЙрдбреНрдпреВрд▓реЛ 11 рдирд┐рдХрд╛рд▓рд┐рдПред рд╣рдореЗрдВ рдРрд╕рд╛ x рдЪрд╛рд╣рд┐рдП рдЬрд┐рд╕рдХреЗ рд▓рд┐рдП \(3x \equiv 1 \pmod{11}\) рд╣реЛред x = 4 рдЖрдЬрд╝рдорд╛рдиреЗ рдкрд░ $$3 \times 4 = 12 = 11 + 1 \equiv 1 \pmod{11}$$ рдорд┐рд▓рддрд╛ рд╣реИред рдЗрд╕рд▓рд┐рдП рдореЙрдбреНрдпреВрд▓рд░ рдЗрдиреНрд╡рд░реНрд╕ рд╣реИ 4ред рд╡реНрдпреБрддреНрдХреНрд░рдо рдХреЗ рд░реВрдк рдореЗрдВ, 3 рдХрд╛ рдкреНрд░рддрд┐рд▓реЛрдо \(1/3 \approx 0.333333\) рд╣реИред
рдЕрдХреНрд╕рд░ рдкреВрдЫреЗ рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рд╕рд╡рд╛рд▓
рд╢реВрдиреНрдп рдХрд╛ рдХреЛрдИ рдкреНрд░рддрд┐рд▓реЛрдо рдХреНрдпреЛрдВ рдирд╣реАрдВ рд╣реЛрддрд╛? рдХреНрдпреЛрдВрдХрд┐ рдХрд┐рд╕реА рднреА рд╕рдВрдЦреНрдпрд╛ рдХреЛ 0 рд╕реЗ рдЧреБрдгрд╛ рдХрд░рдиреЗ рдкрд░ рдкрд░рд┐рдгрд╛рдо рд╣рдореЗрд╢рд╛ 0 рдЖрддрд╛ рд╣реИ, рдХрднреА 1 рдирд╣реАрдВред
рдореЙрдбреНрдпреВрд▓рд░ рдЗрдиреНрд╡рд░реНрд╕ рдХрдм рдореМрдЬреВрдж рдирд╣реАрдВ рд╣реЛрддрд╛? рдЬрдм \(\gcd(a, m) \neq 1\) рд╣реЛ тАФ рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, 4 рдХрд╛ mod 8 рдореЗрдВ рдХреЛрдИ рдЗрдиреНрд╡рд░реНрд╕ рдирд╣реАрдВ рд╣реИ рдХреНрдпреЛрдВрдХрд┐ рджреЛрдиреЛрдВ рдореЗрдВ рдЙрднрдпрдирд┐рд╖реНрда рдЧреБрдгрдирдЦрдВрдб 4 рд╣реИред
рдХреНрдпрд╛ рдореИрдВ рдореЙрдбреНрдпреВрд▓рд░ рдЗрдиреНрд╡рд░реНрд╕ рдХреЗ рд▓рд┐рдП рдЛрдгрд╛рддреНрдордХ рд╕рдВрдЦреНрдпрд╛ рдЗрд╕реНрддреЗрдорд╛рд▓ рдХрд░ рд╕рдХрддрд╛ рд╣реВрдБ? рд╣рд╛рдБ; рдЗрдиреНрд╡рд░реНрд╕ рдирд┐рдХрд╛рд▓рдиреЗ рд╕реЗ рдкрд╣рд▓реЗ рдЙрд╕реЗ рдкрд╣рд▓реЗ 0 рд╕реЗ mтИТ1 рдХреА рд╕реАрдорд╛ рдореЗрдВ рдХрдо рдХрд░ рд▓рд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред