3 ms·
Wouldn't it be fun if someone out there already knows a simple way to determine if a number is prime without factoring, but to them it is so obvious that they d
by waltbosz 1y ago
Wouldn't it be fun if someone out there already knows a simple way to determine if a number is prime without factoring, but to them it is so obvious that they didn't even consider others may be interested.
- adgjlsfhk1 1y agoSince 2002 this has been known, and it's one of the least intuitive things in modern math. (versions with probability of 1-\epsilon have existed since Miller-Rabin in 1976)
- vasvir 1y agoWell I have a really elegant proof for this but I don't have enough space in the HN reply box to write it out -- but it is trivial, I am sure you will work it out. Fermat Reincarnation.
- CRConrad 1y ago> Fermat Reincarnation. Pascal, I think.
- kevinventullo 1y agoAs far as I know, the Lucas-Lehrer test used by GIMPS does not actually factor: https://en.m.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test https://en.m.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primali...
- Someone 1y agoThat works for very few numbers. From that Wikipedia article: “In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers” That’s fine for GIMPS, which only searches for Mersenne primes, but doesn’t work in general. https://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests https://en.wikipedia.org/wiki/Primality_test#Fast_determinis... mentions several tests that do not require factorization, though.
- throwaway81523 1y agoPseudoprime test usually works, and AKS algorithm always works, both are much faster than factoring.