[HN Gopher] A new generation of mathematicians pushes prime numb...
___________________________________________________________________
A new generation of mathematicians pushes prime number barriers
Author : digital55
Score : 60 points
Date : 2023-10-26 17:51 UTC (3 days ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| dabeddabed wrote:
| "...automorphic forms, which have their own version of the
| Riemann hypothesis." What's the Riemann hypothesis for
| automorphic forms?
| dabeddabed wrote:
| Never mind I think it means the Ramanujan-Petersson conjecture
| testless wrote:
| To automorphic forms, you can associate an L-function. There
| are similar conjectures about the zeros of those functions than
| for the Riemann Zeta function.
|
| https://en.wikipedia.org/wiki/Grand_Riemann_hypothesis
| tromp wrote:
| > The sieve of Eratosthenes comes alive in this animation, which
| shows multiples of each prime loping along the number line.
|
| A more accurate depiction would not have a bunch of prime curves
| starting from 0, but would have each one sprouting from its prime
| just when that prime is passed over by all existing prime curves.
| euroderf wrote:
| That would start to resemble some sort of cool fractal.
| unflxw wrote:
| https://en.wikipedia.org/wiki/Ulam_spiral
| test77777 wrote:
| If you just make up a number claim it's prime and nobody disputes
| it, it's prime apparently. I don't think it's really possible to
| have a very large prime number, because unless someone has tried
| every factor it's really not prime yet, honestly that explains a
| lot about the elusiveness of the concept.
| akarve wrote:
| > If you just make up a number claim it's prime and nobody
| disputes it
|
| You can test if a number is prime in polynomial time, much
| faster than a sieve. There's no need to test every divisor to
| know whether a number is prime or not.
|
| Algos like RSA generate large primes millions of times every
| day---there's nothing to take on faith.
| creata wrote:
| Doesn't RSA typically settle for numbers that are _probably_
| prime?
| akarve wrote:
| Technically I think so, so there's a tiny bit of faith for
| RSA but absolutely none for primality in general
| https://en.wikipedia.org/wiki/AKS_primality_test
| test77777 wrote:
| I'd argue that you're just misunderstanding what makes a
| number prime. You can literally never be 100% sure a randomly
| generated number is or isn't prime, it's just the way numbers
| work.
| adgjlsfhk1 wrote:
| you absolutely can. aks is a polynomial time deterministic
| primality check.
| test77777 wrote:
| Ok then break all cryptography with that. It just proves
| my point you can SAY you can do it but in practice you
| can't.
| ndsipa_pomu wrote:
| Cryptography is about finding large prime factors of a
| large number. That's a much harder problem than just
| determining whether a specific number is prime or not.
| test77777 wrote:
| I don't understand you just say it was about finding
| factors, okay yeah that determines whether a number is
| prime. You're not telling me anything I don't know, I
| just disagree with your stance.
| adgjlsfhk1 wrote:
| primality checking is much easier that factoring. it's
| somewhat unintuitive, but there are deterministic methods
| of primality testing that don't tell you the factors.
| ndsipa_pomu wrote:
| I don't understand your stance.
|
| You seem to be claiming that the ability to determine
| whether a number is prime or not is extremely difficult
| and that it would break (some) cryptography if it were no
| so. My stance is that (some) cryptography would not be
| broken unless factorisation of large numbers into two
| large primes becomes easy.
|
| Can you clarify how you think that some cryptography is
| broken by a relatively simple test of whether a large
| number is prime or not?
| adgjlsfhk1 wrote:
| prime testing is much easier than factoring. you need to
| factor to break rsa
| Ar-Curunir wrote:
| _Some_ cryptography depends on hardness of _factoring_ ,
| not hardness of _checking primality_.
| eigenket wrote:
| AKS is an example of a deterministic algorithm which
| works out whether a number is prime or composite and runs
| in polynomial time in the number of bits in the number.
|
| https://en.wikipedia.org/wiki/AKS_primality_test
|
| I'm not sure why you would expect this to break all (or
| any) cryptographic protocols.
| bigbillheck wrote:
| How would that work?
| magneticnorth wrote:
| I think you have some confusion about RSA cryptography - it
| relies on numbers that are deliberately generated using
| very large (known) primes, so these numbers are definitely
| not "randomly generated".
|
| It takes a short time to generate such a number but a very
| long time to decompose it, but this is a different problem
| than telling whether a number is prime.
| vlovich123 wrote:
| The primes used in RSA are definitely randomly generated
| for each new key, unless I'm misunderstanding what you're
| trying to say. And afaik determining that the random
| number is prime is a mixture of "generate a random number
| using a formula that has a high probability of generating
| primes" and various probabilistic primality tests. It's
| possible AKS has been incorporated to prove the numbers
| are prime in modern implementations, not sure. But
| historically RSA traditionally (definitely before 2006)
| determined primality probabilistically.
|
| ECC doesn't require primes and so is safer in that
| respect although I've been hearing that ECC might have
| structural deficiencies that causes a swing back to RSA
| for the most secure applications.
| Ar-Curunir wrote:
| There is literally an entirely deterministic algorithm for
| checking primality, so you can be 100% sure that a
| randomly-generated number is prime:
| https://en.wikipedia.org/wiki/AKS_primality_test
| JonChesterfield wrote:
| Counterexample, roll a dice. That gives you a randomly
| generated number. You can then test whether said random
| number is prime by enumeration.
| sweezyjeezy wrote:
| The article starts by saying mathematicians want things to work
| for large numbers, but that doesn't really get to the crux of
| the issue with primes. Infinite sequences are ubiquitous in
| number theory, and in general it will be infeasible to have a
| test for inclusion in these sequences for large enough numbers.
| But often they have structure that we can use to characterise
| them very precisely - think about square numbers, it's easy to
| say what the trillionth square number is, what it's remainder
| when you divide by 13, etc.
|
| What makes primes hard, and also interesting, is that they seem
| to be extremely unstructured, we believe they behave like a
| kind of random number generator, even though they are clearly
| not random. In fact many of the theorems and conjectures
| mentioned in the article actually hinge on this. Random numbers
| are unpredictable on a small scale, but on a large scale they
| have very nice distributional properties, whereas more
| structured ones of similar growth rate will often have
| undesirable restrictions on them.
| credit_guy wrote:
| You should check the concept of "primality certificate".
|
| https://en.wikipedia.org/wiki/Primality_certificate
___________________________________________________________________
(page generated 2023-10-29 23:02 UTC)