2023-05-04¶
is_valid_hash(hash:str, difficulty:int) -> boolis_prime(n:int) -> bool- Number system
int2base(n:int, base:int) -> strbase2int(n:str, base:int) -> int
- Generator:
- $\mathbb{N}$
- $2\mathbb{N}$
- $2\mathbb{N} + 1$
- $\mathbb{P}$
len_in_bits(n:int) -> int- function with
args&kwargs
Is valid Hash¶
In [1]:
def is_valid_hash(hash: str, difficulty: int):
return hash[:difficulty] == "0" * difficulty
In [2]:
is_valid_hash("00008e1c0cb25c548d7cc7708152d4b23d1161cfaa441c38e1bf1f9d8ce90081", 4)
Out[2]:
True
Is prime¶
In [3]:
def is_prime(n: int):
if n < 2:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
for d in range(3, n, 2):
if n % d == 0:
return False
if n < d**2:
break
return True
In [4]:
is_prime(91)
Out[4]:
False
In [5]:
def is_prime_more_efficient(n):
if n < 2:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
known_primes = []
q = 3
while q**2 <= n:
for p in known_primes:
if q % p == 0:
break
else:
if n % q == 0:
return False
known_primes.append(q)
q += 2
return True
In [6]:
is_prime_more_efficient(91)
Out[6]:
False
In [7]:
def is_prime_most_efficient(n):
if n < 2:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
# https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases
if n < 2_047:
base_witness = [2]
elif n < 1_373_653:
base_witness = [2, 3]
elif n < 9_080_191:
base_witness = [31, 73]
elif n < 25_326_001:
base_witness = [2, 3, 5]
elif n < 3_215_031_751:
base_witness = [2, 3, 5, 7]
elif n < 4_759_123_141:
base_witness = [2, 7, 61]
elif n < 1_122_004_669_633:
base_witness = [2, 13, 23, 1662803]
elif n < 2_152_302_898_747:
base_witness = [2, 3, 5, 7, 11]
elif n < 2_152_302_898_747:
base_witness = [2, 3, 5, 7, 11]
elif n < 3_474_749_660_383:
base_witness = [2, 3, 5, 7, 11, 13]
elif n < 341_550_071_728_321:
base_witness = [2, 3, 5, 7, 11, 13, 17]
elif n < 3_825_123_056_546_413_051:
base_witness = [2, 3, 5, 7, 11, 13, 17, 19, 23]
elif n < 318_665_857_834_031_151_167_461:
base_witness = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
elif n < 3_317_044_064_679_887_385_961_981:
base_witness = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
else:
import math
Warning("It is recommended to use probabilistic test.")
base_witness = range(2, min(n - 2, int(2 * math.log(n)** 2)))
s = 0
d = n - 1
while not d & 1: # n%2 == 1
s+=1
d>>=1 # d//=2
# n - 1 = d * 2^s
for a in base_witness:
x = pow(a, d, n)
for _ in range(s):
y = pow(x, 2, n)
if y == 1 and x != 1 and x != n - 1:
return False
x = y
if y != 1:
return False
return True
In [8]:
is_prime_most_efficient(91)
Out[8]:
False
Number system¶
In [9]:
import string
string.printable
Out[9]:
'0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ \t\n\r\x0b\x0c'
In [10]:
DIGITS = string.printable[:-3]
DIGITS
Out[10]:
'0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ \t\n'
Int to base¶
In [11]:
def int2base(n: int, b: int):
assert b <= len(DIGITS), f"Base cannot exceed {len(DIGITS)}."
assert not n < 0 and isinstance(n, int), "n should be a positive integer."
if n == 0:
return DIGITS[0]
res = ""
while n != 0:
n, i = divmod(n, b)
res = DIGITS[i] + res
return res
In [12]:
int2base(980804196871762145088894647370726397267846519455505854349751109686984833,16)
Out[12]:
'8e1c0cb25c548d7cc7708152d4b23d1161cfaa441c38e1bf1f9d8ce90081'
In [13]:
big_number = 249933671547149819205942447954294398003203213686927841
In [14]:
int2base(big_number,10)
Out[14]:
'249933671547149819205942447954294398003203213686927841'
In [15]:
int2base(big_number,16)
Out[15]:
'29c038ec3e81d447d303b26ffbd623d9fb566c92af1e1'
In [16]:
int2base(big_number,97)
Out[16]:
'This is a surprise for you!'
Base to int¶
In [17]:
def base2int(n: str, b: int):
assert b <= len(DIGITS), f"Base cannot exceed {len(DIGITS)}."
res = 0
for d in n:
d_num = DIGITS.index(d)
assert d_num < b, f"{n} is not a valid number in base {b}."
res = b * res + d_num
return res
Generator¶
$\mathbb{N}$¶
In [18]:
def natural_numbers(start: int = 0, end=None):
n = start
while True:
yield n
n += 1
if end is not None and n> end:
break
$2\mathbb{N}$¶
In [19]:
def even_numbers(start: int = 0):
NN = natural_numbers(start//2)
for n in NN:
yield 2 * n
$2\mathbb{N} + 1$¶
In [20]:
def odd_numbers(start=1):
NN = natural_numbers(start//2)
for n in NN:
yield 2 * n + 1
$\mathbb{P}$¶
In [21]:
def prime_numbers(start=2, end=None):
NN = natural_numbers(start, end)
for n in NN:
if is_prime_most_efficient(n):
yield n
In [22]:
n_first_primes = 50
for i, p in zip(range(1, n_first_primes + 1), prime_numbers()):
print(f"p_{i}\t:\t{p}")
p_1 : 2 p_2 : 3 p_3 : 5 p_4 : 7 p_5 : 11 p_6 : 13 p_7 : 17 p_8 : 19 p_9 : 23 p_10 : 29 p_11 : 31 p_12 : 37 p_13 : 41 p_14 : 43 p_15 : 47 p_16 : 53 p_17 : 59 p_18 : 61 p_19 : 67 p_20 : 71 p_21 : 73 p_22 : 79 p_23 : 83 p_24 : 89 p_25 : 97 p_26 : 101 p_27 : 103 p_28 : 107 p_29 : 109 p_30 : 113 p_31 : 127 p_32 : 131 p_33 : 137 p_34 : 139 p_35 : 149 p_36 : 151 p_37 : 157 p_38 : 163 p_39 : 167 p_40 : 173 p_41 : 179 p_42 : 181 p_43 : 191 p_44 : 193 p_45 : 197 p_46 : 199 p_47 : 211 p_48 : 223 p_49 : 227 p_50 : 229
Length in bits¶
In [23]:
def len_in_bit(n: int):
return len(int2base(n, 2))
In [24]:
len_in_bit(big_number)
Out[24]:
178
In [25]:
bigger_number = 2**256 -1
In [26]:
len_in_bit(bigger_number)
Out[26]:
256
In [27]:
len_in_bit(bigger_number + 1)
Out[27]:
257
In [28]:
int2base(bigger_number,16)
Out[28]:
'ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff'
In [29]:
bit_size = 7
bit_size_primes = []
for p in prime_numbers(2**(bit_size-1), 2**bit_size-1):
bit_size_primes.append(p)
print(f"{bit_size} bits primes are {bit_size_primes}.")
7 bits primes are [67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127].
In [ ]: