> Third, notice that the only remaining multiplication is a multiplication by 4. Because 15 is one less than a power of 2, multiplying by 2 modulo 15 can be implemented using a circular shift. A multiplication by 4 is just two multiplications by 2, so it can also be implemented by a circular shift. This is a very rare property for a modular multiplication to have, and here it reduces what should be an expensive operation into a pair of conditional swaps.
> Aside: multiplication by 16 mod 21 is the inverse of multiplying by 4 mod 21, and the circuits are reversible, so multiplying by 16 uses the same number of Toffolis as multiplying by 4.
I couldn't really find anything explaining the significance of this. The only info I found said that "4 mod 21 = 4" (but I don't know if it was AI slop or not).
Is "multiplying by 4 mod 21" something distinct to quantum computing?
So how many gates are we talking to factor some "cryptographically useful" number? Is there some pathway that makes quantum computers useful this century?
What does this mean about the size (and thus feasibility) of a circuit required to factor a cryptographically interesting number, say, to be generous, RSA1024?
It’s worth noting that the reason we are deploying PQ crypto is not that we are 100% convinced QC is coming soon. It may or may not depending on how development goes.
The goal of cryptography is to make something as close to theoretically unbreakable as possible. That means even theoretical vulnerabilities are taken seriously.
For ECC and RSA and related algorithms we have a theoretical and physically plausible pathway toward a practical machine that could break them. That means many cryptographers consider them theoretically broken even if such a machine does not exist and may not exist for a long time. The math works even if we can’t build it yet.
So it’s considered prudent to go ahead and upgrade now while no QC exists. That way if some major advance does arrive we are ready.
Nobody’s talking seriously about replacing SHA2, AES, ChaCha, etc because there is no physically plausible theoretically valid path to a machine that can break these in, say, less than many millions of years. AFAIK there is no proof that such a path does not exist but nobody has found one, hence they are considered unbroken.
Note that cryptography is not the only or even the most useful application of QC. Things like physical stimulation of quantum systems, protein folding, machine learning, etc. could be more useful. Like digital computers there’s probably a ton of uses we don’t know about because we need to tinker with the machine to figure them out.
Quantum mechanics is "true" insofar as it's useful for some purpose. Until then it's a theory and the jury is still out.
Randomness is something which I feel is a pretty weird phenomenon. I am definitely one of those 'God doesn't play with dice' types.
Randomness is also something that we call things when actually it's random from a subjective perspective. If we knew more about a system the randomness just falls away. E.g. if we knew the exact physical properties of a dice roll we could probably predict it better than random.
What if it's the case that quantum mechanics is similar. I.e. that what we think of as randomness isn't really randomness but only appears that way to the best of what we can observe. If this is the case, and if our algorithms rely on some sort of genuine randomness inherent in the universe, then doesn't that suggest there's a problem? Perhaps part of the errors we see in quantum mechanics arise from just something fundamental to the universe being different to our model.
I don't think this is that far fetched given the large holes that our current understanding of physics have as to predicting the universe. It just seems that in the realm of quantum mechanics this isn't the case, apparently because experiments have verified things. However, I think there really is something in the proof being in the pudding (provide a practical use case).
I wonder when quantum computers will be able to target post-quantum RSA [1]. Normal RSA operations (key generation, encryption, decryption) have an asymptotic advantage over Shor's algorithm, so it is not unreasonable to just use large enough keys. The advantage is similar to Merkle's puzzles [2], with the added bonus that the attacker also needs to run their attack on a quantum computer.
A while ago I generated a gigabit RSA public key. It is available at [3]. From what I remember, the format is: 4-byte little-endian key size in bytes, then little-endian key, then little-endian inverse of key mod 256**bytes. The public exponent is 3.
Because they haven't actually factored any other smaller number yet.
If your program has a compilation process that requires you to already know the answer to the problem you're trying to solve, then what they did was not factorization, but "print 3" with extra steps.
The article, if examined by a non-specialist like me, seems to contain an answer to this concern at the end:
> There are papers that claim to have factored 21 with a quantum computer. For example, here’s one from 2021 [1]. But, as far as I know, all such experiments are guilty of using optimizations that imply the code generating the circuit had access to information equivalent to knowing the factors.
The article claims that 15 was done without precompilation (in the 2015 experiment but not the 2001 experiment), but only because 15 is a very unique number (after decomposition, only the last multiplication has to be performed because all the previous multiplications involve multiplying by 1).
That said, we are REALLY far off from having a useful quantum computer. Jensen was probably being conservative when he said 20-30 years away, hence the immediate pressure he received form the investor community to reverse his statement followed by the flood of ridiculous press releases from the usual companies claiming to be 2-3 years away.
deriving arithmetic from lambda calculus is not "arithmetic with extra steps"... not sure what I mean by that, but seems like that implies there is arithmetic without extra steps, then you just print the answer
I wonder if the circuit could be modularized into a quantum ALU. Where many of the otherwise identical components in the original layout, couldn't just be arranged as operations time, over a reduced number of distinct components.
Most digital algorithms would explode in terms of hardware needed, for increasing N, if we didn't distribute that computation in time, as well as across elements.
Is this the same idea as using universal Turing machines (CPUs that can execute software) rather than conventional fixed-function Turing machines (ASICs/FPGAs)?
unfortunately this is kind of fundamentally impossible. the whole power of quantum computation is that big quantum computers can do computation on a massive state space "for free". that benefit only exists if you have enough qbits to hold the state space.
In most quantum computer designs, gates are signals generated on demand at runtime rather than material deposited at fabrication time. In this regime, the concept of an ALU makes no sense. Instead of just sending pulses doing the exact gates you know need, why would you instead expand that short sequence into long sequences that emulate potentially applying every arithmetic operation to every input and then mux out the result you already knew you needed. It's a lot of extra work for the same final result.
A quantum ALU would also be substantially harder to design, because of the need to maintain reversibility. For example, every operation would have to run as slow as the slowest operation (or else the timing side channel would measure which operation occurred).
Does this mean in a general sense there are numbers that are harder to factor, or is it due to constraints? That some keys will be much harder to crack? If so, how can we know beforehand?
29 comments
[ 3.7 ms ] story [ 52.2 ms ] thread> Aside: multiplication by 16 mod 21 is the inverse of multiplying by 4 mod 21, and the circuits are reversible, so multiplying by 16 uses the same number of Toffolis as multiplying by 4.
I couldn't really find anything explaining the significance of this. The only info I found said that "4 mod 21 = 4" (but I don't know if it was AI slop or not).
Is "multiplying by 4 mod 21" something distinct to quantum computing?
Digital computers were much easier than that. Make it smaller, make a larger number of it, and you're set.
Quantum computers complexity goes up with ~ n^2 (or possibly ~ e^n) where n is the number of qbits
At the same time, things like d-wave might be the most 'quantum' we might get in the practical sense
The goal of cryptography is to make something as close to theoretically unbreakable as possible. That means even theoretical vulnerabilities are taken seriously.
For ECC and RSA and related algorithms we have a theoretical and physically plausible pathway toward a practical machine that could break them. That means many cryptographers consider them theoretically broken even if such a machine does not exist and may not exist for a long time. The math works even if we can’t build it yet.
So it’s considered prudent to go ahead and upgrade now while no QC exists. That way if some major advance does arrive we are ready.
Nobody’s talking seriously about replacing SHA2, AES, ChaCha, etc because there is no physically plausible theoretically valid path to a machine that can break these in, say, less than many millions of years. AFAIK there is no proof that such a path does not exist but nobody has found one, hence they are considered unbroken.
Note that cryptography is not the only or even the most useful application of QC. Things like physical stimulation of quantum systems, protein folding, machine learning, etc. could be more useful. Like digital computers there’s probably a ton of uses we don’t know about because we need to tinker with the machine to figure them out.
I don't get this part
If author already produced "115x", how can optimizations make it worse?
https://eprint.iacr.org/2025/1237.pdf
Randomness is something which I feel is a pretty weird phenomenon. I am definitely one of those 'God doesn't play with dice' types.
Randomness is also something that we call things when actually it's random from a subjective perspective. If we knew more about a system the randomness just falls away. E.g. if we knew the exact physical properties of a dice roll we could probably predict it better than random.
What if it's the case that quantum mechanics is similar. I.e. that what we think of as randomness isn't really randomness but only appears that way to the best of what we can observe. If this is the case, and if our algorithms rely on some sort of genuine randomness inherent in the universe, then doesn't that suggest there's a problem? Perhaps part of the errors we see in quantum mechanics arise from just something fundamental to the universe being different to our model.
I don't think this is that far fetched given the large holes that our current understanding of physics have as to predicting the universe. It just seems that in the realm of quantum mechanics this isn't the case, apparently because experiments have verified things. However, I think there really is something in the proof being in the pudding (provide a practical use case).
You are probably talking about the Copenhagen interpretation, involving superposition.
Personally, I don't think this is the final theory.
Any theory using calculus, cannot be considered discrete, so is therefore not quantized, and not possibly "physical".
Gerard 't Hooft has more to say on this if you want to hear something from a nobel laureate on the subject.
They tried. But because they know exactly the question, they cannot give a precise answer. /s
A while ago I generated a gigabit RSA public key. It is available at [3]. From what I remember, the format is: 4-byte little-endian key size in bytes, then little-endian key, then little-endian inverse of key mod 256**bytes. The public exponent is 3.
[1] https://eprint.iacr.org/2017/351.pdf
[2] https://dl.acm.org/doi/pdf/10.1145/359460.359473
[3] https://hristo.venev.name/pqrsa.pub
If your program has a compilation process that requires you to already know the answer to the problem you're trying to solve, then what they did was not factorization, but "print 3" with extra steps.
> There are papers that claim to have factored 21 with a quantum computer. For example, here’s one from 2021 [1]. But, as far as I know, all such experiments are guilty of using optimizations that imply the code generating the circuit had access to information equivalent to knowing the factors.
[1] https://arxiv.org/abs/2103.13855
That said, we are REALLY far off from having a useful quantum computer. Jensen was probably being conservative when he said 20-30 years away, hence the immediate pressure he received form the investor community to reverse his statement followed by the flood of ridiculous press releases from the usual companies claiming to be 2-3 years away.
He said that factoring and cryptography applications are red herrings. It's not what most people in the field are working on.
The practical application lies in simulating processes where quantum effects are actually directly relevant, such as quantum chemistry: https://en.wikipedia.org/wiki/Quantum_chemistry
Most digital algorithms would explode in terms of hardware needed, for increasing N, if we didn't distribute that computation in time, as well as across elements.
A quantum ALU would also be substantially harder to design, because of the need to maintain reversibility. For example, every operation would have to run as slow as the slowest operation (or else the timing side channel would measure which operation occurred).