## 2019年9月3日火曜日

### Algorithm - Python - 現代の暗号 - RSA暗号を解読してみよう(復号化) - フェルマーの小定理、互いに素、剰余

1. $\begin{array}{l}\left(7,11\right)=1\\ {7}^{11-1}\equiv 1\left(mod7\right)\\ {7}^{10}\equiv 1\left(mod7\right)\\ {7}^{100}\\ \equiv {\left({7}^{10}\right)}^{10}\\ \equiv {1}^{10}\\ \equiv 1\\ \left(mod7\right)\end{array}$

よって求める余り は1。

2. $\begin{array}{l}\left(5,23\right)=1\\ {5}^{23-1}\equiv 1\left(mod23\right)\\ {5}^{22}\equiv 1\left(mod23\right)\\ {5}^{100}\\ \equiv {\left({5}^{22}\right)}^{4}·{5}^{12}\\ \equiv {5}^{12}\\ \equiv {\left({5}^{2}\right)}^{6}\\ \left(mod23\right)\\ {5}^{2}\\ \equiv 25\\ \equiv 2\\ \left(mod23\right)\\ {\left({5}^{2}\right)}^{6}\\ \equiv {2}^{6}\\ \equiv 64\\ \equiv 64-23·2\\ \equiv 18\\ \left(mod23\right)\end{array}$

よっと求める余りは18。

コード

Python 3

#!/usr/bin/env python3
from unittest import TestCase, main

class MyTest(TestCase):
def setUp(self):
pass

def tearDown(self):
pass

def test(self):
spam = [7 ** 10 % 11, 5 ** 100 % 23]
egg = [1, 18]
for s, t in zip(spam, egg):
self.assertEqual(s, t)

if __name__ == '__main__':
main()


$./sample2.py . ---------------------------------------------------------------------- Ran 1 test in 0.000s OK$