Chapter 1: Warm Up - Solution: 1 Powers of Base 2
Uploaded by
david AbotsitseChapter 1: Warm Up - Solution: 1 Powers of Base 2
Uploaded by
david AbotsitseChapter 1: Warm up - Solution
Blockchain and Distributed Ledgers
2020
September
1 Powers of base 2
Compute 20 + 21 + 22 + 23 .
20 + 21 + 22 + 23 = 1 + 2 + 4 + 8 = 15
Prove that 20 + 21 + ... + 2n−1 = 2n − 1.
Let S = 20 + 21 + ... + 2n−1 .
Hence, 2S − S = S.
2S − S = 2 × (20 + 21 + ... + 2n−1 ) − (20 + 21 + ... + 2n−1 ) = (21 + 22 +
... + 2n ) − (20 + 21 + ... + 2n−1 ) = 2n − 1
Compute 24000 /16999 .
24000 24×1000 161000
16999 = 16999 = 16999 = 16
Your new favourite prime number shall be 2256 − 232 − 29 − 28 − 27 − 26 −
24 − 1. Estimate the number of digits.
2256 = 210×25+6 = (210 )25 × 26 ≈ 64 × (103 )25 ≈ 64 × 1075 = 6.4 × 1076 :
Note that we are underestimating here because 103 < 210 .
2 Binary and hexadecimal numbers
Render the hexadecimal number AF F E16 as a binary number.
AF F E16 = 10101111111111102
Compute 810 × 1101101001012 . State the result as a binary number.
1
810 = 2310 = 10002 .
Hence it is just a shift. 1101101001012 × 10002 = 1101101001010002
The biggest known prime number today is p = 282589933 − 1. How many
digits has p if expressed as a binary number.
p = 282589933 − 1 has 82589933 digits as a binary number. They are all 1.
3 The rice and the chessboard
Estimate the number of container ships you would need to transport the
264 − 1 grains of rice. Note that 1000 grams of rice contain approximately
50000 grains. Before you start the computation submit a guess. Make
sure you carefully state your assumptions.
Big containership: 20000 = 2 × 104 containers.
One container is 40t = 4 × 104 kg = 4 × 104 × 50000.
1ship ≈ 2 × 104 × 4 × 104 × 50000 = 4 × 1013 grains.
19
nbShips = 1.84×10
4×1013 ≈ 5 × 10 .
5
Express 264 − 1 as a binary number and as a hexadecimal number.
264 − 1 = 111....1112 (64 digits) = F F....F F16 (64/4 = 16 digits).
4 Groups
Are the natural numbers N with the standard addition a group?
A group G is a finite or infinite set of elements together with a binary
operation (called the group operation) that together satisfy the four fun-
damental properties of closure, associativity, the identity property, and
the inverse property.
The natural numbers N with the standard addition is not a group because
it does not satisfy the inverse property.
Are the integer numbers Z \{0} with the standard multiplication a group?
No, not every element of Z has a (multiplicative) inverse.
Construct a group with exactly two elements. Call them 0 and 1. What
can you say for 1 + 1?
2
Group with set G = {0, 1}, where 0 is the neutral element. Hence
0+1=1+0 =1. The inverse element of 1 has to be 1 : 1 + 1 = 0.
Is there a group with only one element? If so, what element is generating
this group?
Yes, the group with the set G = {0} and 0 + 0 = 0. The generator is 0.
This is the trivial group.
Assume a finite group G is of prime order. The group H is a subgroup of
G. What can you say about the order of H.
H is of order 1 or of the same prime order.
Are the even integer numbers a cyclic subgroup of Z?
Together with the addition they are. Adding even numbers the result is
always an even number.
Is there a group based on an empty set?
No, you need the neutral element.
Are the powers {2k |k ∈ Z} a group with the standard addition? How
about the multiplication?
Together with the addition they are not a group. There is no inverse. Note
that all elements of the set are positive! Together with the multiplication
they are a group! As 2a × 2b = 2(a+b) which is a power of 2. Inverse,
check! Neutral, check.
5 Modular arithmetic
We consider the field K = Z/7Z.
Determine a ∈ K such that a × 4 ≡ 1 mod 7
a × 4 = 1 mod 7 → a is the inverse of 4. Hence, according to Fermat’s
little theorem:
a = 47−2 mod 7 = 45 mod 7 = 4 × 16 × 16 mod 7 = 4 × (16 mod 7)(16
3
mod 7) = 4 × 2 × 2 mod 7 = 2 mod 7.
Compute 3n mod 7 for n ∈ {1, 2, 3, 4, 5, 6}. Do the same for 4 . Do you
notice a difference?
3n results in a bigger set of values.
6 Elliptic curves
We consider the field K = Z/37Z.
Discuss how would you compute the 16 × g where g is a solution of the
Weierstrass equation?
Elliptic curve scalar multiplication is the operation of successively adding
a point along an elliptic curve to itself repeatedly.
Steps: g + g = 2g
4g = 2g + 2g
8g = 4g + 4g
16g = 8g + 8g
