Editing Talk:1957: 2018 CVE List

Jump to: navigation, search
Ambox notice.png Please sign your posts with ~~~~

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 41: Line 41:
 
::::Oh yes, I missed that log(n) is less than n. Nevermind then. [[User:Fabian42|Fabian42]] ([[User talk:Fabian42|talk]]) 13:50, 19 February 2018 (UTC)
 
::::Oh yes, I missed that log(n) is less than n. Nevermind then. [[User:Fabian42|Fabian42]] ([[User talk:Fabian42|talk]]) 13:50, 19 February 2018 (UTC)
 
:On the other hand, consider the following phrases that describe a process using the end result of the process as their direct object: "cook scrambled eggs", "bake a cake", "chop firewood", "encode an MP3", and "factor primes". One would "factor primes" out of the semiprime associated with an RSA key. --[[User:Tepples|Tepples]] ([[User talk:Tepples|talk]]) 15:58, 19 February 2018 (UTC)
 
:On the other hand, consider the following phrases that describe a process using the end result of the process as their direct object: "cook scrambled eggs", "bake a cake", "chop firewood", "encode an MP3", and "factor primes". One would "factor primes" out of the semiprime associated with an RSA key. --[[User:Tepples|Tepples]] ([[User talk:Tepples|talk]]) 15:58, 19 February 2018 (UTC)
: There are a bunch of things going on:
 
:  * NumPy currently has no primality or factoring functions.  SymPy does.  We assume the hypothetical CVE happened because someone added it.
 
:  * Factoring a prime is a bit nonsensical.  We factor into primes or perform a primality test.  Perhaps a reference to the humorously mis-spoken Bill Gates quote: "The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers." -Bill Gates, The Road Ahead, pg. 265.  We know what he meant (and he likely does too) but it's technically just wrong.
 
:  * The best known factoring methods are sub-exponential, not polynomial as $O(\log n)$ indicates.  The current explanation test here is factually wrong (but gets the concept across) -- it isn't $O(2^n)$.
 
:  * Deterministic 64-bit primality testing is $O(\log^2 n)$ using BPSW or deterministic Miller-Rabin.  This worse than $O(\log n)$.
 
:  * Heuristic or probabilistic testing for larger inputs is also $O(\log^2 n)$.  The best deterministic method for larger inputs is ECPP at $O(\log^4 n)$, which is faster than AKS's $O(\log^6 n)$ in addition to much smaller constants.
 
: Ignoring or being amused at the "factoring primes" comment, we see the complexity is actually in the correct form (most internet forum contributers mix up "n" vs. "size of n", for example).  If it were factoring composites, then $O(log^k n)$ for any constant 'k' would be funny as it says nobody noticed they added a polynomial time factoring algorithm.  If it is primality testing then it's funny as-is since this is faster than any known method (basically saying you could do a primality test on any size input with a constant number of multiplies).
 
: [[User:DAJ NT|DAJ NT]] ([[User talk:DAJ NT|talk]]) 19:29, 22 February 2018 (UTC)
 
  
 
Can I edit some spelling errors? There seems to be some spelling errors here and there.Boeing-787lover 10:19, 19 February 2018 (UTC)
 
Can I edit some spelling errors? There seems to be some spelling errors here and there.Boeing-787lover 10:19, 19 February 2018 (UTC)

Please note that all contributions to explain xkcd may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see explain xkcd:Copyrights for details). Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel | Editing help (opens in new window)

Templates used on this page: