Be a crypto hero in the market by logging in
Don't you have an account? Sign in
Market trends report
Token price
Loopring is creating a new “Learning Cryptography” series to educate the wider crypto community about this fascinating field. This series will begin from the basics, and work its way up to the advanced tools that make our scalable 3.0 DEX protocol — which utilises zero-knowledge proofs — possible.
For many developers like myself, understanding cryptography feels like a dark art/magic. It’s not that we find math hard, in fact many of us probably excelled in it in high school/college courses.
The problem lies with the fact that there’s no resource which balances the mathematics and presentation of ideas in an easy-to-understand manner. Facing this problem first hand, I decided to start this series to consolidate my learning, but also help various developers in their journey of understanding cryptography.
After reading through enough of these articles you should be able to understand and grasp more complicated cryptographic primitives in detail such as zero-knowledge proofs, threshold relay signatures and more.
Mathematical notation will gradually be introduced but pictures and repeated explanations will be present so you should hopefully be able to follow along!
Finite Fields, also known as Galois Fields, are cornerstones for understanding any cryptography. A field can be defined as a set of numbers that we can add, subtract, multiply and divide together and only ever end up with a result that exists in our set of numbers. This is particularly useful for crypto as we can deal with a limited set of extremely large numbers.
To have a finite field you need the following properties:
(the doughnut symbol ◦ denotes the remainder after multiplying/adding two elements)
The most crucial property of a finite field is that it has p^m elements where p is a prime number and m is whatever you choose. A finite field with 11 elements can be defined as GF(11¹). A finite field with 256 elements would be written as GF(28). You can’t have a finite field with 12 elements since you’d have to write it as 22 * 3 which breaks the convention of p^m.
With our notation of GF(p^m):
The notation GF(p) means we have a finite field with the integers {0, … , p-1}. Suppose we have GF(5), our initial set will be {0, 1, 2, 3, 4}. Let’s put this into practice by trying out different operations. Any operations we do below should return 0, 1, 2, 3 or 4 (closure property).
Addition:
Subtraction:
Multiplication:
Division/Inversion:
It seemed like our finite field was coming along perfectly until we came across the identity for 0. So what do we do? Eliminate it and represent our field as F11* rather than F11. When referring to finite fields as F* it means 0 is not included as part of the set.
Unlike finite fields, whose elements are integers, extension fields’ elements are polynomials. Extension fields = GF(2m) where m > 1
These polynomials take the form of:
To make it less cryptic, let’s use the example of GF(23) which will result in the equation form:
GF(23) = GF(8) which means there’ll be a total of 8 elements in this set.
If we write out the elements they’ll have the following values for (a2,a1,a0) where a1, a2 or a0 can only ever be 0 or 1.
(a2, a1, a0)
(0, 0, 0) = 0
(0, 0, 1) = 1
(0, 1, 0) = x
(1, 0, 0) = x²
(0, 1, 1) = x +1
(1, 1, 0) = x²+x
(1, 0, 1) = x²+1
(1, 1, 1) = x²+x+1
Putting it all together, GF(23) = {0, 1, x, x², x +1, x²+x, x²+1, x²+x+1}
Although this form looks much different to our integers, we can still do our addition, subtraction, multiplication and division and return an element in our set.
To keep it short and simple let’s add x²+1 and x²+x+1which gives us:
(1+1) x²+x+(1+1)
Since 1 + 1 mod 2 = 0, our equation simplifies to x which is contained in our original set!
Let’s try another example but a little bit harder.
A ◦ B = (x²+1), (x²+x+1)
= x⁴+x³+x²+x²+1
= x⁴+x³+(1+1)x²+1
= x⁴+x³+1
Unfortunately, x⁴+x³+1 doesn’t exist in our finite field. So what do we do? Cue irreducible polynomials which are defined as polynomials which can’t be broken down into smaller polynomials (from the power of original polynomial).
In the case of GF(23) our irreducible polynomial is x³+x+1. If we divide x⁴+x³+1 with our irreducible prime we ultimately get x²+x which exists in our set — yay!
It seems quite mundane to go over such a basic concept in detail, but without doing so it can lead to difficulty understanding more advanced concepts down the line, especially when it comes to the generalized discrete logarithm problem and elliptic curve cryptography!
Loopring is a decentralized exchange protocol utilizing zkSNARKs to bring highly scalable, non-custodial trading to the masses. You can sign up for our bi-weekly update, and learn more at:
⭑ Twitter: twitter.com/loopringorg
⭑ Reddit: reddit.com/r/loopringorg
⭑ Telegram: t.me/loopring_en & t.me/loopringfans (Chinese)
⭑ Discord: discord.gg/KkYccYp
⭑ GitHub: https://github.com/Loopring
⭑ Kakao: open.kakao.com/o/gJbSZdF (Korean)
Learning Cryptography: Finite Fields was originally published in Loopring Protocol on Medium, where people are continuing the conversation by highlighting and responding to this story.
Newest comments
leo 6 시간전
하려는 친구들이 많아야 미래가 밝다고 할 수 있겠죠.
Community | 인하대에서 인천 중·고생에게 블록체인 교육 실시한다네요
토토즐 6 시간전
블록체인의 새싹들이 무럭무럭 기대됩니다~!
Community | 인하대에서 인천 중·고생에게 블록체인 교육 실시한다네요
토토즐 2020-01-16
지갑-이오스렉스-렉스 신청현황 테이블 보시면 보상수량 나올거에요 또는 이오스 지갑에 거래내역 보시면 입금과 보상 입금이 있을겁니다. 보상입금이 수익입니다.
Community | [중요] 이오스 렉스 참여방법 (EOS 입금부터 수익금 확인방법까지)
lojqwer 2020-01-14
해지해서 렉스가 나갔는데 이오스만 들어왔어용 다른 수익이 어떤것으로 들어오나용 ㅠㅠ
Community | [중요] 이오스 렉스 참여방법 (EOS 입금부터 수익금 확인방법까지)
lojqwer 2020-01-14
해지해서 렉스가 나갔는데 이오스만 들어왔어용 다른 수익이 어떤것으로 들어오나용 ㅠㅠ
Community | [중요] 이오스 렉스 참여방법 (EOS 입금부터 수익금 확인방법까지)
Write a post
delete
Are you sure you want to delete this post?
News
Are you sure you want to delete this comment?
Purchase has been completed.
닉네임을 설정
닉네임을 설정 후 작성해주세요.