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

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

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

CC BY-SA 3.0
2013-07-25T18:57:43.837Z
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.
Kaveh
CC BY-SA 3.0
2013-07-25T02:50:41.683Z
2013-07-25T02:50:41.683Z
Phil
<p>In the paper from Adi Shamir [1] from 1979 he shows, that factoring can be done in a polynomial number of <em>arithmetic steps</em>. 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). </p>

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

<p>[1] Adi Shamir, <a href="http://dx.doi.org/10.1016/0020-0190(79)90087-5" rel="nofollow">Factoring Numbers in $O(\log n)$ arithmetic steps</a>. Information Processing Letters 8 (1979) S. 28–31</p>

<p>[2] Peter Borwein, Joe Hobart, <a href="http://dx.doi.org/10.4169/amer.math.monthly.119.07.584" rel="nofollow">The Extraordinary Power of Division in Straight Line Programs</a>, 
The American Mathematical Monthly Vol. 119, No. 7 (August‒September 2012), pp. 584-592</p>

CC BY-SA 3.0
2013-05-14T13:25:58.370Z
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.
mikeazo
CC BY-SA 3.0
2013-05-14T16:39:03.430Z
I'd suggest posting this on [Crypto.SE](http://crypto.stackexchange.com) since you haven't gotten much response here.
mikeazo
CC BY-SA 3.0
2013-07-06T21:16:18.220Z
There is a related blog entry by Lipton: https://rjlipton.wordpress.com/2012/10/16/one-mans-floor-is-another-mans-ceiling/ 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.
minar
CC BY-SA 3.0
2013-07-25T07:15:00.663Z
@minar the cheating problem is not with aribtrary precision. the cheating here is with floor and ceil operations.
Turbo
<cc.complexity-theory><cr.crypto-security><algebraic-complexity>
(Cryptographic) problems solvable in a polynomial number of arithmetic steps
Etsch
# (Cryptographic) problems solvable in a polynomial number of arithmetic steps

(Asked by: username_0 on 2013-01-27)

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](http://dx.doi.org/10.1016/0020-0190(79)90087-5). Information Processing Letters 8 (1979) S. 28–31

[2] Peter Borwein, Joe Hobart, [The Extraordinary Power of Division in Straight Line Programs](http://dx.doi.org/10.4169/amer.math.monthly.119.07.584),
The American Mathematical Monthly Vol. 119, No. 7 (August‒September 2012), pp. 584-592

**Tags:** cc.complexity-theory, cr.crypto-security, algebraic-complexity

> **Comments:**
> **username_1**: 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.  
> **username_1**: I'd suggest posting this on [Crypto.SE](http://crypto.stackexchange.com) since you haven't gotten much response here.  
> **username_2**: There is a related blog entry by Lipton: https://rjlipton.wordpress.com/2012/10/16/one-mans-floor-is-another-mans-ceiling/ 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.  
> **username_3**: @username_2 the cheating problem is not with aribtrary precision. the cheating here is with floor and ceil operations.  

---

## 1 answers

### Answer by username_4 on 2013-07-25. Score: -2

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.

> **Comments:**
> **username_5**: Hi username_4. 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.  

---

