0
$\begingroup$

There's a question I've long had about reversible computing: do non-trivial algorithms usually end up generating strongly pseudorandom data as an artifact of the computation?

The most straightforward example of this would be if you used Fredkin gates or equivalent to wire together a binary multiplier circuit. My understanding is that implementing this, along with most reversible computing tasks, necessitates generating "junk bits" as a byproduct which get channeled along but ultimately ignored.

In the case of a multiplier, if the junk bits had any straightforward or simplistic correlation to the output value, there would potentially be a mechanism for fast factorization of semiprimes; you could essentially run the program in reverse, filling in the product and the junk bits and discovering the factors.

Of course, the problem is determining the junk bits. Presumably a semiprime product must have virtually no bearing on what the junk bits have to be to successfully reverse the program, aside from maybe the conservation of overall bit count. If this is the case, it seems like that could provide a strong method for the generation of pseudorandom data or hash values.

This seems like something that has surely been thoroughly studied, but I haven't been able to find anything in my searching. I'm hoping someone can either explain whether this does or doesn't work as I suspect, or point me towards relevant reading material. I'm mostly interested in something like the specific example I provided, but also any general results about the degree of randomness of junk data in reversible computing would be nice as well.

$\endgroup$
1
  • $\begingroup$ For example, when you add two numbers, 10+01, and the result is 11, to reverse it you have to know one of the original numbers, so the output is 1101 and the 01 are considered junk bits. (Or something equivalently unambiguous; maybe there's a solution where the junk bits store which carries occurred and which input number was higher, or something like that) $\endgroup$
    – user253751
    Feb 9, 2023 at 14:30

1 Answer 1

2
$\begingroup$

I am not aware of any reason to believe that the junk bits will be strongly pseudorandom (for instance, in the sense of polynomial-time indistinguishability from random or cryptographic pseudorandomness), and I would be surprised if they were for most algorithms. I would not expect this to provide a strong method for generation of pseudorandom values.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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