Negative XOR primes

Question

About a year ago you were asked to find the XOR primes. These are numbers whose only factors are 1 and themselves when performing XOR multiplication in base 2. Now were are going to spice things up a bit.

We are going to find the XOR primes in base -2

Converting to Base -2

Base -2 is a lot like every other base. The left most place is the 1s place (1 = (-2)⁰), next to that its the -2s place (-2 = (-2)¹), next to that is the 4s place (4 = (-2)²), and so on and so forth. The big difference is that negative numbers can be represented in base -2 without any negative sign.

Here are some example conversions:

Decimal | Base -2
-----------------
 6 | 11010
-7 | 1001
 12 | 11100
-15 | 110001

XOR addition in Base -2

XOR addition in Base -2 is pretty much the same as XOR addition in binary. You simply convert the number to Base -2 and XOR each digit in place. (This is the same as addition without the carry)

Here is an example worked through step by step:

(We will use the symbol +' to indicate Base -2 XOR addition)

Start in base 10:

6 +' 19

Convert to base -2:

11010 +' 10111

Add them without carrying:

 11010
+' 10111
---------
 01101

Convert your result back into base 10:

-3

XOR multiplication in Base -2

Once again XOR multiplication in base -2 is nearly the same as XOR multiplication in binary. If you are not familiar with XOR multiplication in base 2 there is an excellent explanation here I suggest you take a look at that first.

XOR multiplication in Base -2 is the same as performing long multiplication in base -2 except when it comes to the last step instead of adding up all of the numbers with a traditional + you use the +' we defined above.

Here is an example worked out below:

Start in decimal:

8 *' 7

Convert to Base -2:

11000 *' 11011

Set up long division:

 11000
*' 11011
---------

Multiply the first number by every place in the second

 11000
*' 11011
------------
 11000
 11000
 0
 11000
 11000

Add up all the results using base -2 XOR addition

 11000
*' 11011
-------------
 11000
 11000
 0
 11000
+' 11000
-------------
 101101000

Convert the result back to decimal:

280

The challenge

Your challenge is to verify whether or not a number is an XOR prime in base -2. A number is an XOR prime in base -2 if the only pair of integers that multiply to it in base are 1 and itself. (1 is not prime)

You will take in a number and output a boolean, truthy if the input is an XOR prime in base -2 falsy otherwise.

Solutions will be scored in bytes with attaining the lowest number of bytes as the goal.

Test cases

The following are all XOR primes in base -2:

-395
-3
-2
 3
 15
 83

The following are not XOR primes in base -2:

-500
-4
 0
 1
 258
 280

• JungHwan Min: 258 seems to equal -2 *' -129 = 10 *' 10000011
• Wheat Wizard: @JungHwanMin my bad that one was supposed to be in the other category. I apologize if this has caused you any trouble.
• ZaMoC: In your addition example 6 +' -19 you actually use 19 not -19.

Answer 1

Mathematica, (削除) 156 (削除ここまで) 101 bytes

IrreduciblePolynomialQ[FromDigits[{#}//.{a_,p___}/;a!=1&&a!=0:>{-⌊a/2⌋,a~Mod~2,p},x],Modulus->2]&

As stated here, this works because XOR multiplication is essentially multiplication in the polynomial ring F_2.

Explanation

{#}//.{a_,p___}/;a!=1&&a!=0:>{-⌊a/2⌋,a~Mod~2,p}

Start with {input}. Repeatedly replace a number a (except 0 and 1) by a mod 2 and prepend -floor(a/2), until it does not change. This calculates the input in base -2.

FromDigits[ ... ,x]

Create a polynomial using the digits of the base -2 number, using x as the variable. e.g. {1, 1, 0} -> x^2 + x

IrreduciblePolynomialQ[ ... ,Modulus->2]

Check whether the resulting polynomial is irreducible, with modulus 2.

Old version (156 bytes)

If[#==1,1,Outer[FromDigits[BitXor@@(#~ArrayPad~{i++,--l}&)/@Outer[i=0;l=m;1##&,##],-2]&,k=Tuples[{0,1},m=Floor@Log2[8Abs@#~Max~1]]~Drop~{2},k,1,1]]~FreeQ~#&

List of primes

Here's a list of base -2 XOR primes between -1000 and 1000 (pastebin)

Answer 2

APL (Dyalog Extended), 36 bytes

{2=≢⍸⍵=∘.{ ×ばつ1+|⍵}

Try it online!

Simple brute-force, and extremely inefficient (input 15 takes ~1s). Given an integer n, it generates a range large enough that their binary representation evaluated in negabinary includes n, evaluates its multiplication table (last step evaluated to negabinary instead of binary), then checks if the input appears exactly twice.

The algorithm was inspired by a solution to regular XOR primes.

How it works

{2=≢⍸⍵=∘.{ ×ばつ1+|⍵} ⍝ Inline function; ⍵←n
 ×ばつ1+|⍵ ⍝ ×ばつ(1+abs(n))
 1+⍳ ⍝ 1-based range of above
 ∘.{ }⍨ ⍝ Evaluate XORmul table
 ⊤⍵ ⍝ Binary of right arg
 2*⍸⌽ ⍝ Digit values of ones
 ×ばつ ⍝ Multiply left arg and convert each to binary
 ≠/ ⍝ Digit-wise XOR
 ̄2⊥ ⍝ Interpret as negabinary and convert to integer
 2=≢⍸⍵= ⍝ Does n appear exactly twice in the table?