-3
$\begingroup$

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

$\endgroup$

closed as unclear what you're asking by D.W., Jan Johannsen, Emil Jeřábek supports Monica, Kaveh, David Eppstein Oct 11 '16 at 21:18

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 '16 at 0:54
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ (This paper is progress on the subject, since even Primes in P was not known in 1987.) ​ ​ $\endgroup$ – user6973 Oct 8 '16 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$ – Muhammad Usman Qureshi Oct 9 '16 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$ – Frédéric Grosshans Oct 9 '16 at 15:06

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