Collision free one way function I was playing with a function that I think is collision free and uninvertible assuming the hardness of integer factorization. I am unfortunately not as skilled at math as I would like to be, and do not know how to prove or disprove the function as being collision free. My only proof so far has been from unit testing all possible inputs, which for all 2 byte combinations has proven successful, but is obviously not concrete. 

The algorithm iterates over a sequence of bits. It counts upwards through prime numbers, beginning at 2. For each contiguous '1' bit in the input bits, an exponent counter is incremented. When a '0' bit is encountered, the current prime is exponentiated and composed into the running output, the exponent counter reset to 0, and the current prime is set to the next prime.

For example:

"11001101"


Is interpreted as:

(2 ** 2) * (3 ** 0) * (5 ** 2) * (7 ** 1)


Is this function provably collision free, assuming the output is not truncated? 

Is the function uninvertible for sufficiently large inputs/outputs? 

Lastly, does the function become harder to invert if the output is modified (i.e. truncated or rotated)? 

Edit in response to an answer:
Let me rephrase the question to be more accurate with what I was actually doing. Suppose we iterate through integers, starting at 0 and incrementing by one. Convert each integer to it's binary form and process it in the manner described above. Do any output values produced this way ever collide?
No, it is not collision-free. All possible sequences of 0's produce the same output:

0    --&gt; (2 ** 0) = 1
00   --&gt; (2 ** 0) * (3 ** 0) = 1
000  --&gt; (2 ** 0) * (3 ** 0) * (5 ** 0) = 1
0000 --&gt; (2 ** 0) * (3 ** 0) * (5 ** 0) * (7 ** 0) = 1


In fact, it can be seen that $f(s) = f(s||0)$, for every bit-string $s$.

This could be easily solved by initializing the exponents to 1, and not to 0. 

Anyway, I'm afraid you have not discovered anything new. The Fundamental theorem of arithmetic states that any positive integer can be represented uniquely by a product of prime numbers:

$$n
= p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}
= \prod_{i=1}^{k}p_i^{\alpha_i}$$

Your idea is basically a method for interpreting the bit string as the sequence of exponents $\alpha_1, \alpha_2, ..., \alpha_{k}$.

It is also very easy to invert (leaving aside the issue of the number of trailing 0's). Let us assume that $f(s) = n$. If $n$ is divisible by 2, then the first bit of $s$ is 1. Now you divide by 2 and if the result is divisible by 2, then the next bit of $s$ is also 1. Repeat until it is not divisible by 2, and you know the next bit is 0. Repeat this process with the divisibility of 3, 5, 7, etc.



With respect to the new question you added: yes, there are collisions. 

For example: $f(1) = f(2) = f(4) = ... = f(2^k) = 2$

In fact, for any integer $n$, it can be seen that $f(n) = f(n\cdot 2^k)$, for every integer $k&gt;0$, which means that for each integer there are infinite collisions.