Timeline for Prime factorization of n+1
Current License: CC BY-SA 2.5
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 1, 2023 at 20:21 | comment | added | Taylor Hornby | The problem: "Given the factorization of n, find the factorization of n+1" is as hard as factoring in general. Suppose we had an algorithm for the n+1 problem. Then we can factor an arbitrary n using a "double-and-add" algorithm: On input n: Start with a=0, a_factors = None; For all bits b of n from MSB to LSB { if b = 1 { let a, a_factors = nplusone(a, a_factors) }; let a = a*2 and add 1 to the exponent of 2 in a_factors; } undo the last (extra) mul by 2 in a, a_factors; return a_factors; This ends with a=n, by double-and-adding, updating the prime factors at each step. | |
| Feb 4, 2020 at 15:31 | comment | added | Jeppe Stig Nielsen | The answer is no, but there is a quick way to rigorously prove if $n+1$ is prime, see e.g. <primes.utm.edu/prove/prove3_1.html>. | |
| Dec 15, 2018 at 1:55 | review | Close votes | |||
| Dec 15, 2018 at 19:18 | |||||
| Dec 15, 2018 at 1:40 | history | protected | Felipe Voloch | ||
| Feb 24, 2011 at 18:09 | answer | added | Aaron Meyerowitz | timeline score: 4 | |
| Feb 24, 2011 at 15:01 | answer | added | Dimitris Koukoulopoulos | timeline score: 14 | |
| Feb 11, 2011 at 0:44 | vote | accept | Vor | ||
| Feb 10, 2011 at 21:54 | comment | added | Michael Lugo | A trivial observation: $n+1$ and $n$ have no prime factors in common. | |
| Feb 10, 2011 at 17:15 | history | edited | Andrey Rekalo |
Edited tags.
|
|
| Feb 10, 2011 at 17:14 | answer | added | Gerhard Paseman | timeline score: 2 | |
| Feb 10, 2011 at 14:23 | comment | added | Tapio Rajala | One special case not mentioned so far: With the factorization of $n$ you can determine if $n + 1$ is prime or not, see en.wikipedia.org/wiki/Lucas_primality_test (This is significantly faster than finding the factorization if $n+1$ is not a prime.) | |
| Feb 10, 2011 at 12:40 | comment | added | Qiaochu Yuan | A lower bound on the difficulty: if it were too easy to do this, we could do it twice and either prove or disprove the twin prime conjecture. | |
| Feb 10, 2011 at 11:35 | answer | added | Johan Andersson | timeline score: 8 | |
| Feb 10, 2011 at 11:27 | answer | added | Gerry Myerson | timeline score: 22 | |
| Feb 10, 2011 at 11:07 | answer | added | user12877 | timeline score: 6 | |
| Feb 10, 2011 at 10:44 | history | asked | Vor | CC BY-SA 2.5 |