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

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

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

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

CC BY-SA 3.0
2011-07-27T17:47:19.027Z
2011-07-27T17:47:19.027Z
Paul Pham
<p>Could you post the original Japanese title/reference?</p>
<p>Also, you might consider just writing to the author - assuming it's the same guy he is a professor at the University of Tokyo:</p>
<p><a href="http://www.it.k.u-tokyo.ac.jp/%7Ekunihiro/" rel="noreferrer">http://www.it.k.u-tokyo.ac.jp/~kunihiro/</a></p>
<p>and almost certainly would reply.</p>
<p>Sorry to post this as an answer, it should be a comment but I don't have the rep for that yet apparently...</p>
<p>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-&gt;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!</p>
<p>Basically the conclusion (4) says:</p>
<blockquote>
<p>べき乗剰余演算を行う量子回路を提案した。提案方式は、右向きbinary methodを採用し、Montgomery Reductionを採用するという特徴を持っている。従来の方式よりも、回路の構成要素が少ないという特徴を持っている。qubitが多く必要となるという欠点は持つが、より少ない計算時間で計算ができると期待される。</p>
<p>[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 ).</p>
</blockquote>
<p>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).</p>
<p>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!)</p>

CC BY-SA 2.5
2010-11-19T15:49:30.470Z
Cripes, I thought I'd pasted this link in the original question. Apparently not: http://scholar.google.com/scholar?cluster=14809499008269761518
S Huntsman
CC BY-SA 2.5
2010-11-19T15:53:24.460Z
Added link to original question. I've seen his website, that's how I figured it was from a 2002 proceeedings.
S Huntsman
CC BY-SA 2.5
2010-11-21T03:08:26.533Z
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 
CC BY-SA 2.5
2010-11-21T03:15:59.053Z
Making certain computations reversible may require lots of extra space; this issue is discussed [here.](http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000019000004000673000001&idtype=cvips&gifs=yes&ref=no)
Peter Shor 
CC BY-SA 2.5
2010-11-21T04:20:00.237Z
@Peter Shor I didn't translate the very last paragraph, which discusses future directions for research, but the question you pose is precisely what the author wrote.  It's unclear however, whether he actually went the distance to determine this or not. Unfortunately his office isn't on the main campus, otherwise I'd mosey on over and ask him myself.
s8soj3o289
CC BY-SA 2.5
2010-11-21T12:49:34.940Z
@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 
CC BY-SA 2.5
2010-11-21T15:58:15.983Z
@blackkettle: Thanks. I write him a few days ago and hope to hear back. Your translation is most helpful.
S Huntsman
CC BY-SA 2.5
2010-12-03T17:26:13.320Z
So I still haven't heard anything, but I did find this: http://www.thescipub.com/abstract/10.3844/jcssp.2009.49.56 which seems to indicate a rather large space overhead their implementation of a reversible Montgomery multiplier.
S Huntsman
CC BY-SA 2.5
2010-11-19T11:31:57.273Z
2010-11-21T02:38:04.187Z
2020-06-17T09:38:08.363Z
s8soj3o289
<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">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">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>

CC BY-SA 2.5
2010-11-16T17:01:39.107Z
Crossposted to MO: http://mathoverflow.net/questions/46256/
S Huntsman
CC BY-SA 2.5
2010-11-16T18:11:10.280Z
You only waited an hour before cross posting, which is against our general policy on crossposting: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231 . 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
CC BY-SA 2.5
2010-11-16T18:32:06.377Z
Sorry, wasn't aware of this policy. My apologies--I promise to (re)read the FAQ. Give me a downvote.
S Huntsman
CC BY-SA 2.5
2010-11-16T19:13:34.210Z
I'll give you an upvote for asking such a natural question.
Ross Snider
CC BY-SA 2.5
2010-11-18T18:41:05.233Z
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 
CC BY-SA 3.0
2018-02-07T14:38:02.373Z
Today I saw a blog post by Ken Regan at https://rjlipton.wordpress.com/2018/02/06/doing-mod-n-via-mod-r/ that mentioned two relevant papers: https://arxiv.org/abs/1207.0511 and https://arxiv.org/abs/1706.06752
S Huntsman
CC BY-SA 4.0
2019-04-24T15:35:42.500Z
https://arxiv.org/abs/1904.07356
S Huntsman
<cr.crypto-security><quantum-computing><factoring>
Why isn't Montgomery modular exponentiation considered for use in quantum factoring?
S Huntsman
# Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

(Asked by: username_0 on 2010-11-16)

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](http://en.wikipedia.org/wiki/Montgomery_reduction#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](http://scholar.google.com/scholar?cluster=14809499008269761518) 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...

**Tags:** cr.crypto-security, quantum-computing, factoring
> **Comments:**
> **username_0**: Crossposted to MO: http://mathoverflow.net/questions/46256/  
> **username_1**: You only waited an hour before cross posting, which is against our general policy on crossposting: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231 . We might be slow to respond, but one hour seems like a short time to wait unless you are REALLY in a hurry.  
> **username_0**: Sorry, wasn't aware of this policy. My apologies--I promise to (re)read the FAQ. Give me a downvote.  
> **username_2**: I'll give you an upvote for asking such a natural question.  
> **username_3**: 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.  
> **username_0**: Today I saw a blog post by Ken Regan at https://rjlipton.wordpress.com/2018/02/06/doing-mod-n-via-mod-r/ that mentioned two relevant papers: https://arxiv.org/abs/1207.0511 and https://arxiv.org/abs/1706.06752  
> **username_0**: https://arxiv.org/abs/1904.07356  

---

## 2 answers

### Answer by username_5 on 2010-11-19. Score: 10 | Accepted answer

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/](http://www.it.k.u-tokyo.ac.jp/%7Ekunihiro/)

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!)

> **Comments:**
> **username_0**: Cripes, I thought I'd pasted this link in the original question. Apparently not: http://scholar.google.com/scholar?cluster=14809499008269761518  
> **username_0**: Added link to original question. I've seen his website, that's how I figured it was from a 2002 proceeedings.  
> **username_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.  
> **username_3**: Making certain computations reversible may require lots of extra space; this issue is discussed [here.](http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000019000004000673000001&idtype=cvips&gifs=yes&ref=no)  
> **username_5**: @Peter Shor I didn't translate the very last paragraph, which discusses future directions for research, but the question you pose is precisely what the author wrote.  It's unclear however, whether he actually went the distance to determine this or not. Unfortunately his office isn't on the main campus, otherwise I'd mosey on over and ask him myself.  
> **username_3**: @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.  
> **username_0**: @blackkettle: Thanks. I write him a few days ago and hope to hear back. Your translation is most helpful.  
> **username_0**: So I still haven't heard anything, but I did find this: http://www.thescipub.com/abstract/10.3844/jcssp.2009.49.56 which seems to indicate a rather large space overhead their implementation of a reversible Montgomery multiplier.  

---

### Answer by username_4 on 2011-07-27. Score: 3

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.


---

