3 ms·

> How can you prove a conjecture that concerns infinite numbers of primes using a finite number system? Your intuition is correct, but doesn't go far enough! I

by dvt 7y ago

> How can you prove a conjecture that concerns infinite numbers of primes using a finite number system? Your intuition is correct, but doesn't go far enough! In fact, the notion of a prime in general doesn't make much sense (in Galois fields) :) The article explains it fairly well. Basically, what was proved was the fact that there exist an infinite number of twin prime polynomials (i.e. polynomials that cannot be factored and differ by a fixed gap) in finite number systems.

AaronFriel 7y ago
An interesting aside is that the encryption system most of us rely on every day, AES, relies on a prime over a finite (Galois) field 2^8. The "subbytes" step is a one to one mapping of a byte to another byte, and it's defined in terms of a prime polynomial in the field GF(2^8). In practice though, the table is pre-computed and hardcoded into AES implementations.
- TimTheTinker 7y ago
  > In practice though, the table is pre-computed and hardcoded into AES implementations. It's often referred to as the "s_box" and the "reverse s_box" (for de-encryption).
eximius 7y ago
Unless Galois Fields doesn't refer to the more specific 'field' class of object, why wouldn't primes make sense in that context? Fields can have divisors. You can define a prime as any number whose only divisor is itself and one. I'm out of practice, so maybe you're staying that because you'd essentially have prime equivalence classes that the meaning is different?
- klodolph 7y ago
  If you want a general definition of prime, you would say that a prime is an element p which p|a*b implies p|a or p|b, with the additional restriction that p|1 is false (such elements are called “units”). This lets you extend the notion of “prime” to rings in general, including objects like polynomials or matrixes. If you are curious about some of the details, we can add that “prime” is not quite the same as “irreducible”, although the prime elements and irreducible elements are the same in the more familiar rings. The reason why “prime” doesn’t make much sense in Galois fields is precisely because it’s a field—technically, there are no primes in Galois fields, because every nonzero element divides 1, therefore every nonzero element is a unit, therefore not a prime. So there are no primes in Galois fields. This is mentioned in the article.

by dvt 7y ago

AaronFriel 7y ago

An interesting aside is that the encryption system most of us rely on every day, AES, relies on a prime over a finite (Galois) field 2^8. The "subbytes" step is a one to one mapping of a byte to another byte, and it's defined in terms of a prime polynomial in the field GF(2^8). In practice though, the table is pre-computed and hardcoded into AES implementations.

TimTheTinker 7y ago
> In practice though, the table is pre-computed and hardcoded into AES implementations. It's often referred to as the "s_box" and the "reverse s_box" (for de-encryption).

eximius 7y ago

Unless Galois Fields doesn't refer to the more specific 'field' class of object, why wouldn't primes make sense in that context? Fields can have divisors. You can define a prime as any number whose only divisor is itself and one. I'm out of practice, so maybe you're staying that because you'd essentially have prime equivalence classes that the meaning is different?

klodolph 7y ago
If you want a general definition of prime, you would say that a prime is an element p which p|a*b implies p|a or p|b, with the additional restriction that p|1 is false (such elements are called “units”). This lets you extend the notion of “prime” to rings in general, including objects like polynomials or matrixes. If you are curious about some of the details, we can add that “prime” is not quite the same as “irreducible”, although the prime elements and irreducible elements are the same in the more familiar rings. The reason why “prime” doesn’t make much sense in Galois fields is precisely because it’s a field—technically, there are no primes in Galois fields, because every nonzero element divides 1, therefore every nonzero element is a unit, therefore not a prime. So there are no primes in Galois fields. This is mentioned in the article.