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
Doctord 2020-03-22
여기에서 내가 원하는 대한 조언을 오랜 시간: 한국 뒤로 가기 저를 믿고,최고의 사이트를 찾을 수 없습니다,나는 매우 행복으로 무슨 일이 있었는지 지금 나는 확실히 노력하겠습니다.어떤 경우에는 경우에 당신은 당신의 필요성에 직면하고 최적화를 위해,당신은 여기에서
Community | 멀티 브로드캐스트 플랫폼, 캐스트윗 (CTT)
밝음이 2020-03-16
잘봤오요~~~~~저도 이거 참여하고 있어요!
Community | 리버마운트(RM) 상장 및 IEO 전 라스트 에어드랍 이벤트!!!
뚠뚠초 2020-03-09
마지막이라 아쉽지만 어마어마한 바운티네요 한달 내내 이벤트
Community | 리버마운트(RM) 상장 및 IEO 전 라스트 에어드랍 이벤트!!!
쩜이 2020-03-05
좋은 정보 감사합니다~!!
Community | 대박!! 리버마운트 헤시넷에 등록되다!!!
tokenbank 2020-02-28
고객님 해결 방법을 메일로 안내해 드렸습니다. 추가로 문의가 있으신 경우 홈페이지 우측 하단의 1:1 창구 혹은 cs@tokenbank.co.kr로 문의 주시면 빠른 답변을 받으실 수 있습니다.
Community | 아피스 스왑 뭡니까???
fastest rising posts
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.
닉네임을 설정
닉네임을 설정 후 작성해주세요.