❚ This post is related to a paper of mine, that will get published around the end of October this year in the
Journal of Groups, Complexity and Cryptography (GCC). Some people may think, when they read the headline of this post, this must be a post about Shor's quantum factoring/dlog algorithm, because it is well known that dlogs and factoring can not be solved in polynomial number of arithmetic steps otherwise.
But this is not true.
This sounds very unintuitive, because in cryptography we nearly always work with finite fields, where the bit length is restricted by the size of the modulus and the complexity of an algorithm is hence often measured as the number of arithmetic steps.
But of course you can do this, if you increase the available space. It is not obvious how to do it, but Adi Shamir [1] already showed in 1979 how this could be done, it you allow integers in memory/registers that are of exponential size.
