After writing the Vernam Cipher post, I started thinking about alternatives to using bit-wise XOR in order to translate numbers. I started thinking about XOR for base 3. Therefore I concentrated on what makes XOR so great.
What makes XOR stand out from other operators is the fact that assuming the use of two numbers to generate a third number, you can always use the same operator with the third number and one of the first two numbers to generate the missing number. In other words, there is a one-to-one relationship between every combination and a given number.
Requirement
Let’s say that A and B are the numbers that will XOR’ed and C will be the result. In that case, the following six statements will always be true:
- A ⊕ B = C
- A ⊕ C = B
- B ⊕ A = C
- B ⊕ C = A
- C ⊕ A = B
- C ⊕ B = A
In binary this is true:
- 0 ⊕ 0 = 0
- 0 ⊕ 1 = 1
- 1 ⊕ 0 = 1
- 1 ⊕ 1 = 0
Results In Other Bases
After some trial and error I found a way to mimic this relationship with ternary:
| A | B | A ⊕ B = C |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 2 |
| 0 | 2 | 1 |
| 1 | 0 | 2 |
| 1 | 1 | 1 |
| 1 | 2 | 0 |
| 2 | 0 | 1 |
| 2 | 1 | 0 |
| 2 | 2 | 2 |
After that here is an XOR table which works for base 4:
| A | B | A ⊕ B = C |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 3 |
| 0 | 2 | 2 |
| 0 | 3 | 1 |
| 1 | 0 | 3 |
| 1 | 1 | 2 |
| 1 | 2 | 1 |
| 1 | 3 | 0 |
| 2 | 0 | 2 |
| 2 | 1 | 1 |
| 2 | 2 | 0 |
| 2 | 3 | 3 |
| 3 | 0 | 1 |
| 3 | 1 | 0 |
| 3 | 2 | 3 |
| 3 | 3 | 2 |
The Code
Do you notice the pattern? Do you notice how we could expand it to have multiple XOR translations for each base? After some testing to make sure everything worked out, I came up with the following function in JavaScript which can find the xor of any two numbers in any integer base greater than 1:
/**
* @license Variable Base XOR - By Chris West - MIT License
*/
function xor(num1, num2, base, offset) {
base = base > 2 ? base : 2;
offset = offset || 0;
return (base - (offset + num1 + num2) % base) % base;
}
The base for this function defaults to base 2. The offset defaults to 0 and can be used to generate an alternative value. The offset should only have a range of 0 to base - 1.
Final Notes
There may be quite a few ways of apply this to the real world but the first one that comes to mind deals with encryption. Instead of using bit-wise XOR now you have the option of using an XOR of any other base. Have fun with this and let me know what you think. 8)
1 Comment
shivam · September 3, 2019 at 1:04 AM
this is not correct and it does not follow the property of XOR in binary, like AxA=0 and (AxB)xC=Ax(BxC) these are crucial properties to solve any problem in using XOR, I applied your formula to a puzzle, it doesn’t fit and it doesn’t produce the correct result.