Prime checking and factorization with just bit cheking

Question

I've read about some methods of prime factorization like here and here. However, I'm wondering: what can we do in prime factorization with just some bit manipulation and without other variables/constants?

In base 10, we can get some hints about the factors of an integer just be checking the digits:

• digit's place is even --> int is even
• digit's place is 0 of 5 --> int is divisible by 5
• sum_of_digit % 3 = int % 3
• sum_of_digit % 9 = int % 9

Given an integer num as a bit array, how can we check for num's primality and guess or extract its prime factors just by looking at its bits like we do with digits in base 10?

   There are 5 0's --> (num % (2^5)) = 0
            / \
           /   \
           |   |  
1010101110100000
      | |      ^
      | |      | last bit is 0 --> num is even
      | |
       v
may be these 3 bits can give some information?

What's allowed:

• bit-manipulations which take 1 argument are allow. This includes functions like not but not xor.

• ifs and loops are allowed but bits in num will be used for the flag. (no using if num > 2)

• num is the only variable/constant allowed to be declared. We can not(num) (flip every bits in num) but not num - 2 (2 is another var/const).

• Operating on bits only in num like summing all the bits (bit_sum(20) = bit_sum(b1010) = 2 because there are 2 1s)

Bonus if the operation can quickly be done by hand like the given examples for base 10.

Answer 1

Given any specific candidate divisor $d$, it is easy to check whether $d$ is a divisor of the number (the standard modular reduction algorithm is a generalization of those tricks you mentioned). This can be done for all $d$. However, it doesn't help with efficient factorization, because there are exponentially many candidate divisors, so trying each one, one-by-one, is far too inefficient.

In other words, this approach to factorization is not likely to be useful, no matter how many tricks you accumulate.