Timeline for Why is integer factoring hard while determining whether an integer is prime easy?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 7, 2022 at 21:45 | history | edited | davolfman | CC BY-SA 4.0 |
Most of my points were incorrect, editted to recover the ones that aren't
|
| Dec 7, 2022 at 20:48 | comment | added | John Coleman | @davolfman It isn't just the time that rules out a naive sieve for testing if a large number is prime. There also wouldn't be enough memory. | |
| Dec 7, 2022 at 19:30 | comment | added | JoshuaZ | @davolfman A naive sieve takes around $sqrt(N)$ time to factor $N$. Nut the point is that modern systems aren't doing naive sieving. We have a lot of other algorithms, including the general number field sieve, which is only a sieve in a very broad sense en.wikipedia.org/wiki/General_number_field_sieve Notice also that the run time for it is an $L_n$-type, which is not either of the cost types you have above. Most importantly, methods like it do not just check all the prime divisors up to a specific point, so they would not benefit from faster or even constant time prime checking. | |
| Dec 7, 2022 at 18:16 | comment | added | davolfman | @JoshuaZ Interesting. I know 512bit keys aren't trusted but aren't really quick to factor yet. And a 10^80 number is about 270 bits by rule-of-thumb. So N made from 2 of those should be under a minute by my logic here. I guess that means the sieves cost proportional to polynomial time of the value of N instead of the length of N as I thought? | |
| Dec 7, 2022 at 1:02 | comment | added | JoshuaZ | @davolfman If you mean Eratosthenes sieve, that's very inefficient in general, and doesn't even benefit that much from fast primality checking. Let's say you could check if a number of any size was prime in a picosecond. Then to use naive sieving to sieve a number with only around 10^72 or so digits would take more time than the universe has been around for, and a number around 10^300 would take more time than the functional heat death of the universe. But I can get even just Wolfram Alpha to factor a number around 10^80 in a few seconds, so we're doing something different. | |
| Dec 7, 2022 at 0:50 | comment | added | davolfman | @JoshuaZ so I've confused sieving n for sieving p or q? I think it might still only average some fixed multiple though if neither p nor q are particularly small. Given the polynomial order of the problem. Like, if the sieve was order N^2 then the cost to factor a number 2N long would only be 4 times as much. | |
| Dec 7, 2022 at 0:38 | comment | added | JoshuaZ | This is incorrect. First, primality checking need not be probabilistic for the range used in practical RSA keys. For example, APR can handle primes for RSA keys in the range used. We often use probabilistic tests in practice, since you can run Miller-Rabin or whatever your preferred test to make the error percentage tiny. Your last claim is also wrong. Testing that p or q is prime, is not the same difficulty as far as we can tell of finding p and q given n=pq. If one could show that it would be a massive breakthrough and certainly not "by definition." | |
| Dec 7, 2022 at 0:36 | comment | added | Andreas Blass | The question concerns the deterministic primality testing algorithm, not probabilistic ones. | |
| S Dec 7, 2022 at 0:28 | review | First answers | |||
| Dec 7, 2022 at 1:01 | |||||
| S Dec 7, 2022 at 0:28 | history | answered | davolfman | CC BY-SA 4.0 |