Powers of Base 2 and Groups
Uploaded by
david AbotsitsePowers of Base 2 and Groups
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
Common questions
Powered by AIIn the field Z/7Z, the inverse of 4 can be calculated using Fermat's Little Theorem, which implies that a^(p-1) ≡ 1 (mod p) for a prime p, hence a^(p-2) is the inverse. For a = 4, a^(7-2) mod 7 = 4^5 mod 7 = 4 * (16 mod 7) * (16 mod 7) = 4 * 2 * 2 mod 7 = 2, thus the inverse is 2 .
The integers Z \{0} do not form a group under multiplication because not every integer has a multiplicative inverse within the set. For example, 2 does not have an integer multiplicative inverse, hence the set fails to satisfy the inverse property required in group theory .
The natural numbers N with standard addition do not form a group because they fail to meet the inverse property, which requires every element to have an inverse within the set under the operation. Since natural numbers do not include negative numbers, there is no additive inverse for nonzero elements .
To find the number of digits in the binary representation of the prime number p = 2^82589933 − 1, note that binary representation of such Mersenne prime has 82589933 digits, as each bit corresponds to a power of two .
If G is a group of prime order, all subgroups H of G can only have an order of 1 or the same prime order as G. By Lagrange's theorem, the order of a subgroup must divide the order of the group, leading to these two possibilities in groups of prime order .
To prove the sum formula 2^0 + 2^1 + ... + 2^(n-1) = 2^n - 1, let S = 2^0 + 2^1 + ... + 2^(n-1). Then consider the equation 2S, which equals 2^1 + 2^2 + ... + 2^n. Subtract S from 2S, resulting in 2S - S = 2^n - 2^0. Simplifying, we have S = 2^n - 1 .
Scalar multiplication of 16 × g on an elliptic curve in Z/37Z involves repeated addition of the point g: Start with g, compute 2g = g + g, 4g = 2g + 2g, 8g = 4g + 4g, and finally 16g = 8g + 8g. Each of these steps involves using the curve's addition formula, a critical aspect of elliptic curve cryptography .
The set of powers {2^k | k ∈Z} is not a group under addition since there is no inverse; elements are all positive integers, so no additive inverse exists. However, under multiplication, it forms a group because multiplication is closed, there exists a multiplicative identity (1), and each element has an inverse that's a power of 2, like 2^(-k).
The hexadecimal number AFFE16 is represented as the binary number 10101111111111102 .
The number 2^64 - 1 is represented in binary as a sequence of 64 ones: 111...1112 and in hexadecimal as FFFF...FF16 consisting of 16 digits. This indicates that 2^64 - 1 is a Mersenne number, which is closely related to primality testing and representation .