most recent 30 from http://mathoverflow.net 2013-05-25T04:16:33Z http://mathoverflow.net/feeds/question/46256 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46256/why-isnt-montgomery-modular-exponentiation-considered-for-use-in-quantum-factori Steve Huntsman 2010-11-16T16:44:41Z 2010-11-19T16:00:07Z

<p>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 <a href="http://en.wikipedia.org/wiki/Montgomery_reduction#Modular_exponentiation" rel="nofollow">Montgomery modular exponentiation</a> is the preferred method. Modular exponentiation is also prominently featured in the quantum factoring algorithm, and it is expensive there as well. </p> <p><strong>So: why isn't Montgomery modular exponentiation apparently present in current detailed subroutines for quantum factoring?</strong></p> <p>The only thing I can imagine is that there's a high qubit overhead for some non-obvious reason.</p> <p>Running <em>montgomery quantum "modular exponentiation"</em> 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.</p> <p>The single <a href="http://scholar.google.com/scholar?cluster=14809499008269761518" rel="nofollow">reference</a> 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.</p> <blockquote> <p>Quantum circuit in performing arithmetic Noboru Kunihiro</p> <p>...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...</p> <p>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...</p> <p>...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.</p> <p>...[8] PL Montgomery, "Modular Multiplication Without Trial Division," Mathematics of Computation, 44, 170, pp. 519-521, 1985...</p> </blockquote> <p>[This is a <a href="http://cstheory.stackexchange.com/questions/3053/" rel="nofollow">crosspost from cstheory</a>: it doesn't seem to be getting much attention there.]</p>