10x0, 7x1, 5x2, 2x3, 0x4, ...
In [1]:
10*4
Out[1]:
40
In [2]:
7*4+10*1 #najprv 1, potom 0
Out[2]:
38
In [4]:
#2, 1, 0
5*4+7*2+10*1
Out[4]:
44
In [5]:
#2, 0
5*4+10*2
Out[5]:
40
In [6]:
#3, 0
2*4+10*3
Out[6]:
38
In [8]:
2*4+5*3+7*2+10*1
Out[8]:
47
2x0, 1x1, 9x2, 2x3, 0x4, ...

klesajuca postupnost ...

In [9]:
1*4+2*1
Out[9]:
6
In [10]:
2*4
Out[10]:
8
In [ ]:
43210
4210
410
3210
320
310
30
...

Ako rýchlo vieme klesnúť na cenu $c$?

In [8]:
from graphviz import Graph
g = Graph()
In [9]:
g.edge('1', '3', label='0')
In [10]:
g.edge('2', '3', label='0')
In [11]:
g.edge('4', '3', label='1')
In [12]:
g.edge('4', '5', label='0')

image.png

In [19]:
528/(4**2)/3
Out[19]:
11.0
In [20]:
5**4 # celkovo stvoric
Out[20]:
625
In [21]:
5**4-3**4-2**4
Out[21]:
528

Fast modular exponential¶

In [22]:
5**117
Out[22]:
6018531076210112040799931070577897870431567650673088110124808736145496368408203125
In [23]:
5**117 % 19
Out[23]:
1
In [25]:
print(f'{117:b}')

1110101
In [37]:
for i in [2**x for x in range(8)]:
    print(i, 5**i, 5**i % 19)

1 5 5
2 25 6
4 625 17
8 390625 4
16 152587890625 16
32 23283064365386962890625 9
64 542101086242752217003726400434970855712890625 5
128 293873587705571876992184134305561419454666389193021880377187926569604314863681793212890625 6
In [38]:
#1 0  1 0  1 1 1
#5,6,17,4,16,9,5
(5*17*16*9*5) % 19
Out[38]:
1
In [39]:
5*17
Out[39]:
85
In [40]:
(5*17)% 19
Out[40]:
9
In [41]:
(9*16)% 19
Out[41]:
11
In [42]:
n = 19
((((5*17)% n*16)%n*9)%n*5) % n
Out[42]:
1
In [43]:
5**117 % 19
Out[43]:
1
In [44]:
5**(116+1) % 19
Out[44]:
1
In [46]:
5**(2*58+1) % 19
Out[46]:
1
In [48]:
((5**2)**58 * 5**1) % 19
Out[48]:
1
In [49]:
((5**4)**29 * 5**1) % 19
Out[49]:
1
In [50]:
((5**4)**(28+1) * 5**1) % 19
Out[50]:
1
In [51]:
pow(5, 117, 19)
Out[51]:
1
In [ ]: