目次
この記事は、 SHA256を計算する in Pythonのステップ1です。
SHA-256 の計算の中には、 2乗根、3乗根の計算が出てきます。 ハッシュとして生成される最終的な値をできるだけランダムにするために、素数の2・3乗根を計算して使用します。 この2・3乗根は定数として与えられるので(PDFに記述されていた)、わざわざ計算する必要はないのですが、いちいち書き写すのも面倒なので、2・3乗根を計算する関数を作成しておきます。 尚、Pythonでは ** (1/2), ** (1/3) を数値の後ろにつければ 2・3乗根を計算できますので、効率を求めるならわざわざ実装する必要はありません。
SHA-256 の計算では、 小さい方から 1〜64番目 の素数を使います。 64個なら書いてしまうのもいいですが、64個も書き写すと間違えそうです。 Python で素数を計算します。 こちらもライブラリを使って効率よく済ませることもできます。
2乗根
開平法をPythonで記述します。 開平法は、正の数の平方根を計算する方法です。 数学ハンドブック (石川 博朗) で見たことがあります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
def sqrt(n: int, p: int = 16): """ calculate square root >>> 2 - sqrt(2) ** 2 < 10 ** -15 True >>> 3 - sqrt(3) ** 2 < 10 ** -15 True >>> 121 - sqrt(121) ** 2 < 10 ** -12 True >>> 700 - sqrt(700) ** 2 < 10 ** -12 True >>> 999 - sqrt(999) ** 2 < 10 ** -12 True not precise but sufficient for sha-256 calculation. :param n: number that is not more than 100 :param p: :return: """ s = 0 while n > 100: n /= 100 s += 1 r = 0 a = 0 for j in range(p): for i in range(9, -1, -1): if (r + i) * i <= n: a += i / (10 ** j) n = (n - (r + i) * i) * 100 r = (r + i * 2) * 10 break return a * (10 ** s) |
このプログラムは、そんなに精度高くないです。
sqrt(121) は 11 にはならず、 10.999999999999988 になります。
しかし、 SHA-256 を計算する上ではこの程度で十分です。
3乗根
開立法をPythonで記述しました。 開立法は正の数の立方根を計算する方法です。 開立法は3乗というだけあって開平法よりも難しいですが、YouTubeにわかりやすくまとまっていました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
def curt(n: int, p: int = 16): """ calculate cube root >>> 2 - curt(2) ** 3 < 10 ** -14 True >>> 3 - curt(3) ** 3 < 10 ** -14 True >>> 300 - curt(300) ** 3 < 10 ** -13 True >>> 999 - curt(999) ** 3 < 10 ** -12 True :param n: number that is not more than 1000 :param p: :return: """ assert 0 < n < 1000 r1 = 0 r2 = 0 a = 0 for j in range(p): for i in range(9, -1, -1): if (r2 + (r1 + i) * i) * i <= n: n = (n - (r2 + (r1 + i) * i) * i) * 1000 r2 = (r2 + 2 * (r1 + i) * i + i ** 2) * 100 r1 = (r1 + i * 3) * 10 a += i / (10 ** j) break return a |
こちらも上の sqrt と同じように、 SHA-256 の計算では十分な精度になっています。
1000以上の3乗根は計算できませんが、 それでも SHA-256 の計算には十分です。
sqrt のように 10 ** 3 で割ったり、 また掛けたりすれば、精度はともかく1000以上の数値についても計算できるようになります。
素数
ある数が素数であるかどうかは、その数の2乗根以下の素数で割れば確認できます。
2乗根の計算には、 上で実装した sqrt を用いていますが、 精度がよくないので sqrt の計算結果に手を加えています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
class Prime: def __init__(self): self.nums = [2, 3, 5, 7, 11, 13, 17, 19, 23] self.N = self.nums[-1] def _append_if_prime(self, n): """ append n to self.nums if n is prime >>> Prime()._append_if_prime(121) False :param n: :return: """ if n in self.nums: return True if n <= self.N: return False m = int(sqrt(n) + 0.001) for i in self.nums: if i > m: self.nums.append(n) self.N = n return True if n % i == 0: self.N = n return False while i <= m: if n % i == 0: self.N = n return False i += 2 self.N = n self.nums.append(n) return True def numbers(self, num): c = len(self.nums) n = self.N + 1 + self.N % 2 while c < num: if self._append_if_prime(n): c += 1 n += 2 return self.nums[:num] |
計算結果は繰り返し使用できるので、クラスを作成してインスタンス変数を利用しています。
SHA-256 の計算でクラスの外から呼び出されるのは numbers です。
この関数で、素数のリストを返します。
テスト
doctest を使ってテストしておきます。
ファイルの下の方に次のコードを書いて実行します。
|
1 2 3 |
if __name__ == '__main__': import doctest doctest.testmod() |
このテストの記述は、この後の実装でも役に立ちます。
次のステップは 変換関数の実装 です。
