Timeline for Why can’t you use cyclotomic polynomials to factor big numbers really quickly?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 19, 2018 at 20:41 | answer | added | Ehrhart | timeline score: 7 | |
| Feb 15, 2018 at 15:59 | comment | added | Jan-Christoph Schlage-Puchta | but is usually bigger than $0.2$. The problem with your argument is that as $d$ runs over the divisors of $k$, most of the time you check whether $n$ is divisible by a prime which is much larger than $n$ itself, and only occasionally you go back and obtain information about smaller primes. | |
| Feb 15, 2018 at 15:56 | comment | added | Jan-Christoph Schlage-Puchta | Suppose that you want to find the prime factor $p$. Let $q$ be the largest prime factor of $p-1$. The multiplicative order of $x\pmod{p}$ is $(p-1)/d$ , where $d$ is a divisor of $n$, which is usually quite small, in particular the largest prime factor of $(p-1)/d$ will practically always be $q$ as well. If $k$ is the product of the first primes, then you have to take $k$ to be as large as the product of all primes up to $q$. Conjecturally the largest prime factor of $p-1$ is distributed according to the Dickman function, thus $k$ has to be as large as $e^{p^c}$, where $c$ depends on $p$, | |
| Feb 13, 2018 at 1:41 | history | edited | Robin Houston | CC BY-SA 3.0 |
acknowledge David’s answer and explain the non-uniformity
|
| Feb 13, 2018 at 1:34 | vote | accept | Robin Houston | ||
| Feb 13, 2018 at 1:34 | answer | added | David E Speyer | timeline score: 32 | |
| Feb 13, 2018 at 0:40 | comment | added | Robin Houston | @FelipeVoloch Or perhaps I should ask more specifically: how big would it have to be, and why? | |
| Feb 13, 2018 at 0:30 | comment | added | Robin Houston | @FelipeVoloch I think this is precisely my question: why would $k$ have to be really, really big? Naively the number of “hits” should grow exponentially in the number of prime factors of $k$. | |
| Feb 13, 2018 at 0:27 | comment | added | Felipe Voloch | To have a good chance to factor all numbers this way, $k$ would have to be really, really big and the computations would get out of hand. But, this is not very different from Pollard's $p-1$ algorithm which factors some number of a special form. | |
| Feb 13, 2018 at 0:05 | history | asked | Robin Houston | CC BY-SA 3.0 |