# Using XOR operation, a MOD operation compute a function f(n)

I had a difficult assignment in my Data Structures and Algorithms class.

We need to implement a program that computes a function f(n) based on the following known values of n and f(n):

n : 9689 9941 11213 19937 21701 23209 44497 86243 110503 132049

f(n) : 3 5 7 13 17 19 23 37 47 59

n : 216091 756839 859433 1257787 1398269 2976221 3021377

f(n) : 61 67 71 79 89 101 103

The requirements of the assignment are as follows：

1. We are allowed to use a pre-initialized array with 17 numbers.
2. We can use one XOR operation and one MOD operation.
3. We can access the array in a read-only manner.
4. The program should not crash if an input n is not listed. The output can be arbitrary in such cases.

Another requirement may be to minimize operations and memory usage.

The first thing I want to know is what knowledge I should apply to this problem. I have currently written a program that stores f(n) in an array and when we enter n, takes the remainder of each input n and each number in the array. I printed out the results to try to be able to get some insight. But I wasn't. My other thought is that maybe this question has something to do with hashing, but I don't have a clue. My biggest doubt is how should we use XOR in the question.

I am open to suggestions and alternative approaches. Thank you in advance!

• Does or doesn't a pre-initialized array with 17 numbers mean an array of size 17? The task may be simpler with a 23-element array, trivial with a 3020100 element one. Commented May 20 at 17:38
• In the task is what I wrote above. My understanding is that it can be thought of as an Array of size 17 Commented May 20 at 19:52
• If you look at the seventeen function values provided, they all share a particular mathematical property. Coincidence? I think not. Commented May 21 at 11:42

As we want to use both operations, we only have two possible combinations: $$\left(n \oplus x\right) \mod s\tag{1}\label{1}$$ $$\left(n \mod x\right) \oplus s\tag{2}$$
If we store $$f\left(n\right)$$ in an array $$a$$ of length $$17$$, we want our index $$i$$ to lie within the interval $$\left[0,16\right]$$. We can achieve this by choosing $$\eqref{1}$$ with $$s = 17$$.
Now we need to find $$x \;\forall\; n : a\left[\left(n\oplus x\right) \mod 17\right]=f\left(n\right)$$
Considering that we can store our elements $$f\left(n\right)$$ in $$a$$ in any order, this problem can be brute forced quite easily.