<p>Both! </p>

<p>You may want to read the answers to <a href="https://cstheory.stackexchange.com/q/25512/2368">this related question</a>, and the 1987 paper of Heather Woll, <a href="http://www.sciencedirect.com/science/article/pii/0890540187900307" rel="nofollow noreferrer">Reductions among number theoretic problems, Information and Computation 72 (1987) 167-179</a> cited in Jeffrey Shallit’s answer. This paper looks at the reduction between many problems in number theory, including primality, factorization, order-finding, discrete logarithm. This paper is pretty old, and I guess¹ progress has been made on the subject over the last three decades.</p>

<p>In particular shows that order-finding deterministically reduces to factorization, and that factorization probabilistically reduces to order-finding (through the trick used by Shor’s algorithm). So the answer to you question is indeed : both.</p>

<p>¹: <em>Warning: I am not a number theorist.</em></p>

CC BY-SA 3.0
2016-10-09T14:51:54.437Z
Thanks for your reply. I have read these articles. This is a primality test. Aren't factoring algorithms less efficient as of today compared to primality tets?
Muhammad Usman Qureshi
CC BY-SA 3.0
2016-10-09T15:06:09.003Z
You asked many questions on many related number theory problems. The 1987 paper I mentioned gives information about many of them, including order finding and factorisation ( the main question according to your title). @RickyDemer mentioned one major progress since 1987, which is primality testing. So yes, there are today efficient primality testing algorithm (very efficient probabilistic ones, and polynomial deterministic ones). For factorisation, no efficient algorithm is known (until we manage to build a quantum computer)
Frédéric Grosshans
CC BY-SA 3.0
2016-10-07T13:03:10.310Z
2016-10-07T15:33:42.563Z
2017-04-13T12:32:28.167Z
Frédéric Grosshans
<p>initially i was not at all equipped in theoretical computer science and knew only basics of number of theory.<br>
I started working from scratch on the age old problem of primality testing which led me to the order finding problem. then I moved on to something which later turned out to be the discrete logarithm and finally I was able to reduce these problems to the factorisation problem.<br>
finally when I started surveying the literature I got a bit confused.<br>
both these problems in already published articles were stemming from integer factorisation as in the famous shor`s paper. but I got it in the reverse order so firstly I wanted to inquire which problem is considered the basic one? or are they inter linked?<br>
To be more specific<br>
finding the order of 10 mod n, and finding n which solves (10^x) =1 (i.e x belongs to Zn we have to find this n) are the two problems. And factorisation of n can be done with the help of either of these.<br>
In my work this order is used to factorise n with the help of repunits</p>

CC BY-SA 3.0
2016-10-07T00:54:24.443Z
I find it hard to tell exactly what you're asking.  If you want to know whether problem X reduces to problem Y, please specify both problems precisely, then show your thoughts, what research you've done, and what you've tried.  In this case, the exact formulation affects the answer: order finding in what group?  discrete log in what group?  what's fixed and what's part of the input?  etc.  Also, only one question per question, please.  Your last paragraph (about repunits) seems unrelated and should be asked separately.  Note that this isn't a forum: please see our [tour] to learn more.
D.W.
<quantum-computing><cr.crypto-security><factoring><comp-number-theory>
The factoring problem reduces to order finding or is it the other way around?
Muhammad Usman Qureshi
# The factoring problem reduces to order finding or is it the other way around?

(Asked by: username_0 on 2016-10-06)

initially i was not at all equipped in theoretical computer science and knew only basics of number of theory.  
I started working from scratch on the age old problem of primality testing which led me to the order finding problem. then I moved on to something which later turned out to be the discrete logarithm and finally I was able to reduce these problems to the factorisation problem.  
finally when I started surveying the literature I got a bit confused.  
both these problems in already published articles were stemming from integer factorisation as in the famous shor`s paper. but I got it in the reverse order so firstly I wanted to inquire which problem is considered the basic one? or are they inter linked?  
To be more specific  
finding the order of 10 mod n, and finding n which solves (10^x) =1 (i.e x belongs to Zn we have to find this n) are the two problems. And factorisation of n can be done with the help of either of these.  
In my work this order is used to factorise n with the help of repunits

**Tags:** quantum-computing, cr.crypto-security, factoring, comp-number-theory

> **Comments:**
> **username_1**: I find it hard to tell exactly what you're asking.  If you want to know whether problem X reduces to problem Y, please specify both problems precisely, then show your thoughts, what research you've done, and what you've tried.  In this case, the exact formulation affects the answer: order finding in what group?  discrete log in what group?  what's fixed and what's part of the input?  etc.  Also, only one question per question, please.  Your last paragraph (about repunits) seems unrelated and should be asked separately.  Note that this isn't a forum: please see our [tour] to learn more.  

---

## 1 answers

### Answer by username_2 on 2016-10-07. Score: 5

Both!

You may want to read the answers to [this related question](https://cstheory.stackexchange.com/q/25512/2368), and the 1987 paper of Heather Woll, [Reductions among number theoretic problems, Information and Computation 72 (1987) 167-179](http://www.sciencedirect.com/science/article/pii/0890540187900307) cited in Jeffrey Shallit’s answer. This paper looks at the reduction between many problems in number theory, including primality, factorization, order-finding, discrete logarithm. This paper is pretty old, and I guess¹ progress has been made on the subject over the last three decades.

In particular shows that order-finding deterministically reduces to factorization, and that factorization probabilistically reduces to order-finding (through the trick used by Shor’s algorithm). So the answer to you question is indeed : both.

¹: *Warning: I am not a number theorist.*

> **Comments:**
> **username_0**: Thanks for your reply. I have read these articles. This is a primality test. Aren't factoring algorithms less efficient as of today compared to primality tets?  
> **username_2**: You asked many questions on many related number theory problems. The 1987 paper I mentioned gives information about many of them, including order finding and factorisation ( the main question according to your title). @RickyDemer mentioned one major progress since 1987, which is primality testing. So yes, there are today efficient primality testing algorithm (very efficient probabilistic ones, and polynomial deterministic ones). For factorisation, no efficient algorithm is known (until we manage to build a quantum computer)  

---

