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
-
4$\begingroup$ 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. $\endgroup$– D.W.Oct 7, 2016 at 0:54
1 Answer
Both!
You may want to read the answers to this related question, and the 1987 paper of Heather Woll, Reductions among number theoretic problems, Information and Computation 72 (1987) 167-179 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.
-
1$\begingroup$ (This paper is progress on the subject, since even Primes in P was not known in 1987.) $\endgroup$– user6973Oct 8, 2016 at 4:16
-
$\begingroup$ 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? $\endgroup$ Oct 9, 2016 at 14:51
-
$\begingroup$ 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) $\endgroup$ Oct 9, 2016 at 15:06