3
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm not really looking for efficiency here. I'm just thinking about "What can I do with just bit manipulation?" and "How much information can I get from just a single bit field?" $\endgroup$ – John Zhau Dec 26 '19 at 1:50
  • $\begingroup$ @JohnZhau, modular reduction is a form of bit manipulation, so I don't think there is any principled line one can draw between checking (say) divisibility by 3 vs divisibility by any other number. Of course divisibility by values of the form $2^k \pm 1$ are particularly easy, but one can also come up with more complex tricks for more complex divisors; ultimately the limit of that progression is that you end up re-inventing modular reduction. $\endgroup$ – D.W.♦ Dec 26 '19 at 3:53
  • $\begingroup$ Can such divisibility be done just from staring at the binary of the given number and without doing some operations like and, or, xor with the binary of 3? I'm looking to extract data just from looking at the bit field and without the given binary doing anything like another number/binary. $\endgroup$ – John Zhau Dec 26 '19 at 4:00
  • $\begingroup$ @JohnZhau, depends on who is doing the staring and their mental abilities. (The same could be said about the sum of digits modulo 9.) I don't think there is a clear line you can draw anywhere here. $\endgroup$ – D.W.♦ Dec 26 '19 at 4:04
  • $\begingroup$ "Staring" is just an over-simplified example of things humans do. I'm thinking of using only operations that take in only 1 argument to extract information. "Is this a 1?" and not are such operations. $\endgroup$ – John Zhau Dec 26 '19 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.