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.