Project Euler 810 - XOR-Primes

Official link: https://projecteuler.net/problem=810

Thought Process

Some quick brute force showed me that the first 10 primes were most likely [2, 3, 7, 11, 13, 19, 25, 31, 37, 41] which corresponds to https://oeis.org/A014580, which to my delight is something that I learnt recently in university from a course called Galois and Field Theory.

For those unfamiliar with this topic this problem will be very difficult to understand, but I will try my best to give an overview.

Let's breakdown the description of the sequence listed on OEIS which is "Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2."

The ring GF(2)[X] = all polynomials with co-efficient's living in the modulo 2 world
1. For example 3x + 1 = x + 1 because 3 = 1 (mod 2)
2. (x) + (x + 1) = 2x + 1 = 1 since 2 = 0 (mod 2)
Binary irreducible polynomials are polynomials in the above ring which have no proper factors
1. For example x is irreducible since it's only divisors are 1 and x
2. x^2 + 1 is reducible since x^2 + 1 = (x + 1)(x + 1)
Evaluating at X = 2 is clear.

The first few irreducible polynomials are x, x + 1, x^2 + x + 1, x^3 + x + 1, x^3 + x^2 + 1 which correspond to the values: 2, 3, 7, 11, 13.

Knowing this I thought the problem would be to find a way to efficiently calculate all irreducible polynomials. Hence, I tried to solve it using the below theorem:

To implement this in python I found an amazing galois theory python package and was able to implement the recursive method above, however constantly dividing polynomials was an expensive task and the program was too slow. But then I remembered another crucial fact which would make my code much faster

Using my previously built Mobius Sieve I can now easily calculate the number of irreducible polynomials of any degree. Using this I can find that the total number of irreducible polynomials surpasses 5,000,000 once we add the degree 26 irreducible polynomials, so our 5,000,000th XOR-Prime is a degree 26 polynomial.

Knowing this I simly generate all degree 26 polynomials in binary form ("111" = x^2 + x + 1", "101" = x^2 + 1, etc, etc) and then using the above galois package I test if that polynomial is irreducible. This was much faster and I could find the 10,000th prime in around a minute, which is still too slow...

After many attempts of making it faster I came back to the "obvious" idea of just sieving all the numbers which I initially dismissed because I thought there would be a more beautiful solution, sadly it was not to be.

Since the XOR-Product between 2 numbers is always bigger than the 2 numbers, a sieve works perfectly fine. The problem then becomes just making an efficient sieve, which falls short of what I wanted from this problem, but either way I include all of my steps because Field and Galois Theory are some of my personal favourite topics in math!

I include my code for the XOR-Product with comments as if this function is unoptimized the code runs very slowly.

Interactive Code

Enter an integer (yourinput)

Code will output the yourinput-th XOR-Prime

Page updated

Google Sites

Report abuse