MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is the preferred method. Modular exponentiation is also prominently featured in the quantum factoring algorithm, and it is expensive there as well.

So: why isn't Montgomery modular exponentiation apparently present in current detailed subroutines for quantum factoring?

The only thing I can imagine is that there's a high qubit overhead for some non-obvious reason.

Running montgomery quantum "modular exponentiation" through Google Scholar yields no useful results. I am aware of work by Van Meter and others on quantum addition and modular exponentiation, but examining their references (I have yet to read this work) shows no indication that Montgomery methods are considered there.

The single reference I have found that appears to discuss this is in Japanese, which lamentably I cannot read, though apparently it is from a 2002 conference proceedings. A machine translation yields nuggets appended below that indicate there might be something useful. However, I can't find any indication that this has been followed up, which makes me think that the idea has been a) considered and then b) discarded.

Quantum circuit in performing arithmetic Noboru Kunihiro

...In this study, but requires relatively large qubit, we propose a modular exponentiation circuit quantum computation time is short. Montgomery Reduction [8] and right binary method [9] Combined, they constitute a circuit Ru. Reduction Montgomery is, m randomly chosen as a natural number, mod 2m by the operation, perform the remainder operation If, mod n operations in eliminating. This will lead to reduction of computation time...

Application of 3.2 Montgomery Reduction Montgomery Reduction [8] is formulated as follows...This algorithm can return the correct values can be easily confirmed. M R (Y) he asks for a law 2m Polynomials with 2m points are important and only requires division by. In addition, Montgomery Reduction in, there are different calculation methods....In general, Reduction Montgomery is not one-to-one function...

...The proposed method uses a right binary method, Montgomery Reducton has a feature that is adopted. Than the conventional method, characterized by a small component of the circuit Have. qubit fault that is required to have a lot of expectations can be computed in less computational time Be. The future, Montgomery Reduction and control circuitry specifically NOT described by the qubit really needed Evaluate the number is expected to evaluate the computation time. In addition, each taking advantage of research findings, more than modular exponentiation Non-arithmetic (Euclid mutual division, etc.) also with respect to the planned configuration of an efficient quantum circuit.

...[8] PL Montgomery, "Modular Multiplication Without Trial Division," Mathematics of Computation, 44, 170, pp. 519-521, 1985...

[This is a crosspost from cstheory: it doesn't seem to be getting much attention there.]

share|cite|improve this question
Good question. I don't know whether anybody has put in the time to decide whether Montgomery Reduction speeds up exponentiation when done reversibly. Some algorithms (like Karatsuba) end up being hard to make reversible since they seem to require lots of additional space. – Peter Shor Nov 18 '10 at 19:58
Just to inform people, the cstheory posting ( has now been given an interesting answer – Peter Shor Nov 21 '10 at 3:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.