Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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...

share|improve this question
1  
Crossposted to MO: mathoverflow.net/questions/46256 –  S Huntsman Nov 16 '10 at 17:01
1  
You only waited an hour before cross posting, which is against our general policy on crossposting: meta.cstheory.stackexchange.com/questions/225/… . We might be slow to respond, but one hour seems like a short time to wait unless you are REALLY in a hurry. –  Suresh Venkat Nov 16 '10 at 18:11
    
Sorry, wasn't aware of this policy. My apologies--I promise to (re)read the FAQ. Give me a downvote. –  S Huntsman Nov 16 '10 at 18:32
    
I'll give you an upvote for asking such a natural question. –  Ross Snider Nov 16 '10 at 19:13
5  
It's not clear to me whether anybody has even put in the time to determine whether there's some obstacle to speeding up quantum factorization using Montgomery exponentiation. Good question. –  Peter Shor Nov 18 '10 at 18:41
add comment

2 Answers

up vote 9 down vote accepted
+50

Could you post the original Japanese title/reference?

Also, you might consider just writing to the author - assuming it's the same guy he is a professor at the University of Tokyo:

http://www.it.k.u-tokyo.ac.jp/~kunihiro/

and almost certainly would reply.

Sorry to post this as an answer, it should be a comment but I don't have the rep for that yet apparently...

EDIT: So, I took a look at the original Japanese. As a preface, I am currently a PhD student in the EE department at U. Tokyo, originally from the U.S., and I do technical JA->EN translation as a part-time job. However, this topic area is well outside my comfort zone so please take my opinion with a grain of salt!

Basically the conclusion (4) says:

べき乗剰余演算を行う量子回路を提案した。提案方式は、右向きbinary methodを採用し、Montgomery Reductionを採用するという特徴を持っている。従来の方式よりも、回路の構成要素が少ないという特徴を持っている。qubitが多く必要となるという欠点は持つが、より少ない計算時間で計算ができると期待される。

[In this paper] We proposed a new quantum circuit for computing modular exponentiation. The proposed method utilizes an LR binary method, and is also characterized by use of the Montgomery Reduction. Compared with previous methods, the proposed method requires fewer components to construct the circuit. The proposed method does however, have the drawback of requiring a large number of qubits, but we are confident that it will be computationally efficient ( lit: require very little computation time ).

I tried searching for related follow-up papers in both English and Japanese but was unsuccessful. My guess is that the approach proved unsuccessful, or the professor got busy with something else (looks like this was around when he switched universities).

I think that your best bet at this point, assuming you want to follow up the rest of the way and get a concrete answer, is to write professor Kunihiro directly (in English!)

share|improve this answer
    
Cripes, I thought I'd pasted this link in the original question. Apparently not: scholar.google.com/scholar?cluster=14809499008269761518 –  S Huntsman Nov 19 '10 at 15:49
    
Added link to original question. I've seen his website, that's how I figured it was from a 2002 proceeedings. –  S Huntsman Nov 19 '10 at 15:53
3  
It seems to me that the same thing may have gone wrong that goes wrong with Karatsuba's fast multiplication algorithm: making it reversible seems to require using a large number of extra qubits (i.e., space or memory). A good research question is whether this is unavoidable or not. Thanks for the translation. –  Peter Shor Nov 21 '10 at 3:08
1  
Making certain computations reversible may require lots of extra space; this issue is discussed here. –  Peter Shor Nov 21 '10 at 3:15
1  
@blackkettle: determining that the space expansion is unavoidable would require new lower bound proof techniques in theoretical computer science, so it's very unlikely this will happen soon. What might happen is finding a more space-efficient way of doing Montgomery modular exponentiation. –  Peter Shor Nov 21 '10 at 12:49
show 3 more comments

I also wondered about this question, since the current approaches to modular multiplication for quantum factoring use either a trial subtraction if there is an overflow after every addition, or a division/subtraction approach at the end. Both of these seem wasteful.

I am working on a quantum architecture for performing modexp using Montgomery multiplication right now. I don't think the space overhead should be any greater than previous approaches, but I see no need to use Karatsuba multiplication currently.

Montgomery multiplication in binary is quite efficient (bit-shifting and addition). The addition of the modulus and the shifted sums depend on the least significant bit (LSB) at each step, so this seems to require before them serially, to get O(n) time.

However, you can parallelize this dependency on the LSB by using function tables and composing/narrowing them similar to carry-lookahead approaches or Kitaev's description of parallel finite automata in his book (Kitaev, Shen, Vyalyi 2002). This step almost certainly requires a lot of ancillae, but asymptotically it could be made O(log n)-depth.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.