9
$\begingroup$

In the paper from Adi Shamir [1] from 1979 he shows, that factoring can be done in a polynomial number of arithmetic steps. This fact was restated, and thus came to my attention, in the recent paper of Borwein and Hobart [2] in the context of straight line programs (SLP).

Since I was rather surprised to read this, I have the following question: Are there any other cryptographic problems or maybe also other relevant problems, that can be solved in a polynomial number of steps with a SLP and that are currently not known to be solvable efficiently on a "normal" classical computer?

[1] Adi Shamir, Factoring Numbers in $O(\log n)$ arithmetic steps. Information Processing Letters 8 (1979) S. 28–31

[2] Peter Borwein, Joe Hobart, The Extraordinary Power of Division in Straight Line Programs, The American Mathematical Monthly Vol. 119, No. 7 (August‒September 2012), pp. 584-592

Improve this question
$\endgroup$
4
  • $\begingroup$ What does "solvable in polynomial number of arithmetic steps" mean? The best factoring algorithms currently available take subexponential time (but super-polynomial). I can't find Shamir's paper anywhere. $\endgroup$
    – mikeazo
    May 14, 2013 at 13:25
  • $\begingroup$ I'd suggest posting this on Crypto.SE since you haven't gotten much response here. $\endgroup$
    – mikeazo
    May 14, 2013 at 16:39
  • $\begingroup$ There is a related blog entry by Lipton: rjlipton.wordpress.com/2012/10/16/… This computation model is kind of cheating, because you are allowing computations with arbitrary long precision. I am not aware of other crypto related problems that have been addressed in this model. But the model is so powerful that it could be worth trying. $\endgroup$
    – minar
    Jul 6, 2013 at 21:16
  • $\begingroup$ @minar the cheating problem is not with aribtrary precision. the cheating here is with floor and ceil operations. $\endgroup$
    – Turbo
    Jul 25, 2013 at 7:15

1 Answer 1

Reset to default
-2
$\begingroup$

I did not read the paper as well but the abstract seems to say that an exponenial number of bit operations are required.

Chebyshev's work on congruences and its reformulation in the AKS algorithm show that prime generation is in P. Therefore trial division yields non-trivial factors. In that case, for some number N, you can expect a density of primes of 1/ln(N).

Furthermore, you can have a look at Turing's 1937 PhD thesis on the subject.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Hi Phil. Welcome to cstheory. You have been posting answers to many questions in a short time which is not usual here. Posts which are really comments and not answers to the question should not be posted as answers. You may want to look around and check other questions and how things work here before posting more answers. $\endgroup$
    – Kaveh
    Jul 25, 2013 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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