Hello. This is Tenmei Watanabe from Dragon Blog. Last time and the day before last, we explained two keywords for mixing in this article. In other words, it's about linear congruences and Fermat's little theorem. Do you remember? about me. It's not a friend I haven't seen in a while, but I would like to check these two keywords again.
Now, the first-order congruence expression is ``a and b are congruent modulo m.'' I'm trying to confuse the reader right away, but the expression a ≡ b (mod m) means that the remainders when a and b are divided by m are the same. In a fantasy world, my confusion strategy is to use things like evening primrose to solve confusion, but next time I'll use Fermat's Little Theorem, which is even more difficult.
Fermat's little theorem is an impregnable cipher with the formula a^(p-1)≡1 (mod p), where if p is a prime number, then a has a value from 1 to p-1 and becomes 1 with mod p. is. This time, I would like to talk about elliptic curve cryptography, so please think of the keyword "cipher" as a foreshadowing.
If you remember the name Euler's phi function from last time, you should remember that the correct name is a^φ(p)= 1 mod p. I'll put a link to the previous article here. I generally don't like to read articles, so if you fall and have to call an ambulance, I'll immediately transport you to a fantasy world and teach you a spell that will help you walk without legs. Is it a ghost? ? It's a little surreal (lol).
Well, I'll leave the idle gag here for the first time in a while. φ(p) is the number of numbers for which p is relatively prime. In other words, if p is a prime number 7, then there are 7-1 = 6, and if p is a non-prime composite number 9, there are 6, 1, 2, 4, 5, 7, and 8. In this case, φ(7)=6 and φ(9)=6, respectively. In other words, if we multiply a six times and mod p, then if a and p are relatively prime, we get 1 mod p.
Well, I've explained it quite quickly and sloppily so far. This is a review, but if you want to know more, please refer to the previous and previous articles.
Now let's talk about codes. This is a story about the demon world called codes, so please continue to enjoy my story if you like.
When you think of codes, some people may think of the runes of ancient civilizations. From the point of view of modern people, the letters used in the distant past are truly worthy of the name cipher. Let's code! !
Among the codes that are often used in modern times, the codes that are commonly used in modern times are the RSA code, which involves decomposition of prime factors, and the elliptic curve code, which uses elliptic curves. RSA encryption, which is a prime factorization code, is used to send credit card pin numbers to the bank where you have your deposit account. On the other hand, what do you think about elliptic curves even if you ask an elderly person? It is used in codes related to cryptocurrencies, which may be said to be.
This time, I would like to introduce a method to easily find a solution for this elliptic curve. Hello everyone? Primary congruence? Fermat's little theorem? What was it? Instead, please try to prepare and review the previous article. If you do that, you should be able to see the beginning of my story.
Now, what is the elliptic curve cryptography used in Bitcoin? First, look at the following formula: This time, it is not meant to be multiplied by x, but expressed as a single variable. Be careful! !
y^2 ≡ x^3 + 7 mod p
Those who think that complicated surgical techniques should not be used. Please rest assured. Since the values of y and p are known in advance, only x is found. By the way, the symbol "^" means y^2, which is the square of y. In other words, y is multiplied twice. x^3 is x to the third power. In other words, it means x multiplied three times.
For example, let's say y=11, p=17. Actually, if you substitute the numerical values and organize them, you will get the following.
11^2 ≡ x^3 + 7 mod 17
121 – 7 ≡ x^3 mod17
x^3 ≡ 114 mod 17 ≡ 12 mod 17
x^3 ≡ 12 mod 17
Here, the remainder when dividing 114 by 17 is 12. One of the points is that the equation of this elliptic curve is a cubic congruence. In other words, it is a congruence of x to the third power. Let's apply Fermat's little theorem to this. Let's raise both sides to the 5th power.
x^(3×5) ≡ 12^5 mod 17
Since p=17 is a prime number, x^16 is 1mod17 if x and p are relatively prime. Then multiply both sides by x.
x^(3×5+1) ≡ x(12^5) mod17
x^16 mod 17 ≡ 1mod17 ①
(12^5)x mod 17 ≡ 248832x mod17 ≡ 3x mod17 ②
3x mod 17 ≡ 1 mod 17 ②=①
Multiplying both sides by 6 gives 18x, which becomes 17x+x ≡ x mod17. For information on how to find 6 multiplied by both sides, please refer to Euclid's mutual division method in the previous article.
x mod 17 ≡ 6 mod 17
Answer: x = 6 mod 17
Calculation: x^3 ≡ 6^3 ≡ 12 mod 17
Therefore, you know the answer. Let's take another example. What if y=8,p=17?
8^2 ≡ x^3 + 7 mod 17
64 – 7 ≡ x^3 mod17
x^3 ≡ 57 mod 17 ≡ 6 mod 17
x^3 ≡ 6 mod 17
x^(3×5) ≡ 6^5 mod 17
x^(3×5+1) ≡ x(6^5) mod 17
x^16 ≡ 1 mod 17 ≡ (6^5)x mod 17 ≡ 7776x mod 17 ≡ 7x mod 17
7x ≡ 1 mod 17
Multiply both sides by 5.
35x ≡ x ≡ 5 mod 17
x ≡ 5 mod 17
x^3 ≡ 5^3 ≡ 6 mod 17
So, I know the answer. The key point here is Fermat's little theorem. The key point is that depending on how you use Fermat's little theorem, a^(p-1) becomes 1 mod p. No matter how many a's are multiplied together, it can be converted to 1 mod p depending on the conditions.
This time we explained how to find the answer for an elliptic curve, but for example, it is also possible to find a, b, and c for a given value of p for a^3+b^3+c^3=p. maybe. Let's do the math on this one ourselves. The difficulty level is quite high. Let's make a legend meeting.
How was it. It seems that the linear congruence equation and Fermat's little theorem are closely related, but by synthesizing them, I was able to discover a new way to solve the mathematical equation. This time I just mixed two keywords, but you might be able to find a more advanced way of thinking if you mix three keywords. This time is over. See you soon.