I'm in the midst of developing a game for several friends as a friendly competition.

It begins with generating the largest distinct semiprime feasible with factors that closely related in length where the 8 highest order bits are all '1's.

In contemplating this I realize that this is, I believe, rather trivial in as much as 256 runs of Openssl genrsa have an even chance of giving rise to such an example at lengths sufficient for RSA.

To remedy this I'm looking at a 2nd rule which would insist that the reverse of the binary expansion of this semiprime, itself be a distinct semiprime (again, with factors that closely related in length).

In this fashion, with the competitor providing both the semiprime and both pairs of factors (the original and reversed), it will be assured that they have done some legwork.

Questions: 1. Am I missing anything from the perspective of the complexity of the task? I recognize collisions of this sort (where the original binary expansion of a number and its reverse are both distinct semiprimes with factors that are closely related in length) become vanishingly small at some point, but I'm not clear where it drops to effectively 0 for my purposes.

  1. Perhaps I'm overthinking this? I'm looking for semiprimes with interesting features but it is too easy, I think, using the back way around wherein we simply generate primes and then test to see if they produce semiprimes with the interesting feature sought. My 2nd rule looks to control for this. If there is a means to avoid this shortcut without adding the 2nd rule I would be interested in hearing of it. Perhaps there is another mathematical puzzle (who knows, elliptic curves??) that would provide a similar challenge without the shortcut. I'm open to suggestions.

  2. The other idea I had was to use a hash function and looking to its binary expansion as a distinct semiprime for my 2nd rule. Will a hash function typically create a number of equivalent length? I would use this rather than the reverse if there is some (unknown to me) strange numerical relationship between a number's binary expansion and it's reverse that makes the task easier.

Thanks in advance for your comments.


Your Answer

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

Browse other questions tagged or ask your own question.