Factoring Numbers in 0(log n) Arithmetic Steps
In this paper we show that a non-trivial factor of a composite number n can be found by performing arithmetic steps in a number proportional to the number of bits in n, and thus there are extremely short straight-line factoring programs. However, this theoretical result does not imply that natural n...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148919 |
| _version_ | 1826199509407891456 |
|---|---|
| author | Shamir, Adi |
| author_facet | Shamir, Adi |
| author_sort | Shamir, Adi |
| collection | MIT |
| description | In this paper we show that a non-trivial factor of a composite number n can be found by performing arithmetic steps in a number proportional to the number of bits in n, and thus there are extremely short straight-line factoring programs. However, this theoretical result does not imply that natural numbers can be factored in polynomial time in the Turing-Machine model of complexity, since the numbers operated on can be as big as 2^cn^2, thus requiring exponentially many bit operations. |
| first_indexed | 2024-09-23T11:21:04Z |
| id | mit-1721.1/148919 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:21:04Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1489192023-03-30T03:53:52Z Factoring Numbers in 0(log n) Arithmetic Steps Shamir, Adi In this paper we show that a non-trivial factor of a composite number n can be found by performing arithmetic steps in a number proportional to the number of bits in n, and thus there are extremely short straight-line factoring programs. However, this theoretical result does not imply that natural numbers can be factored in polynomial time in the Turing-Machine model of complexity, since the numbers operated on can be as big as 2^cn^2, thus requiring exponentially many bit operations. 2023-03-29T14:09:02Z 2023-03-29T14:09:02Z 1977-11 https://hdl.handle.net/1721.1/148919 4827346 MIT-LCS-TM-091 application/pdf |
| spellingShingle | Shamir, Adi Factoring Numbers in 0(log n) Arithmetic Steps |
| title | Factoring Numbers in 0(log n) Arithmetic Steps |
| title_full | Factoring Numbers in 0(log n) Arithmetic Steps |
| title_fullStr | Factoring Numbers in 0(log n) Arithmetic Steps |
| title_full_unstemmed | Factoring Numbers in 0(log n) Arithmetic Steps |
| title_short | Factoring Numbers in 0(log n) Arithmetic Steps |
| title_sort | factoring numbers in 0 log n arithmetic steps |
| url | https://hdl.handle.net/1721.1/148919 |
| work_keys_str_mv | AT shamiradi factoringnumbersin0lognarithmeticsteps |