Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there any information on the internet concerning analysis of subsets of bits of the (unknown) factors of any given integer n? Me being unskilled with phrasing things properly for google has given me no useful information.

here's an example: say you are given 0b110111 (55) , whose factors are 0b101 (5) and 0b1011 (11), and are currently unknown to you. is there some way of manipulating subsets of the bits of the factors, say 0b01 and 0b011 so that it can be verified that at least these two bit sequences are some of the (lower) bits of the factors? i know the basic way of simply comparing their product with the number being factored, but is there more research into other things that can be done through bit manipulation?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Let me express your question a bit more constructively:

Question Rephrased:

If you take a number $a$ and split it into it's upper bits and lower bits at bit $n$ for an $N$ bit number:

$$a = 2^{(N-n)} + r$$

where $r$ is the remainder, and $N \ge n$. Then you can easily see that:

$$a \equiv 2^{(N-n)} \pmod r$$

for your example $5 = 2^2+1$ when split at bit number 2, then $5 \equiv 2^2 \pmod 1$ and 11 is $2^3+3$ when split at bit 3, then $11 \equiv 2^3 \pmod 3$.

So the question you are asking is, is it possible to figure out something about a composite number $c = a_1 \times a_2$ by looking at its factors and examining to see if something can be derived examining $r_1$ and $r_2$ by noting that $a_1 \equiv 2^{k_1} \pmod {r_1}$ and $a_2 \equiv 2^{k_2} \pmod {r_2}$ for some ${k_1}$ and ${k_2}$, where ${k_1}$ and ${k_2}$ are as yet unknown.

answer:

The answer in general is no you cannot derive interesting information, because your choice of where to split the number (bits $n_1$ and $n_2$) is not known.

$k_1 = N-n_1$ and $k_2 = N-n_2$ and you stipulated that you don't know $k_1$ and $k_2$.

Now the next question is, what if you randomly chose $n_1$ and $n_2$? Well you are now starting to stumble upon probabilistic methods of tests of primality.

You still need to put strong limits on choices of $n_1$ and $n_2$. As an exercise, you can try to reason out what type of limits on $n_1$ and $n_2$ before the test becomes "interesting".

For example, you would probably want to avoid $n_1 = N$. For that what if you chose $N \gg n_1$ ? Is that sufficient? can you find a counter example? What if ${n_1} \approx N/2$ or $N/4$ is that okay? can you find a counter example?

For further reading have a look at Miller-Rabin primality test and Lucas-Lehmer primality test. If you are really into it you can also look at this paper $\text{Common factors of resultants}\mod p$, it may give you more interesting insights.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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