# (Cryptographic) problems solvable in a polynomial number of arithmetic steps

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

• 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 May 14 '13 at 13:25
• I'd suggest posting this on Crypto.SE since you haven't gotten much response here. – mikeazo May 14 '13 at 16:39
• 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. – minar Jul 6 '13 at 21:16
• @minar the cheating problem is not with aribtrary precision. the cheating here is with floor and ceil operations. – T.... Jul 25 '13 at 7:15