My prime number skills only go up to 47 because that's how high Number Munchers went.
Is This Prime?
51–60 of 139 posts
Re: Is This Prime?
#52Is there a reason we're obsessed with primes beyond aesthetics? Why does this set of numbers garner all the headlines as opposed to some other arbitrary integer sequence like the Recamán numbers [0] ? If tomorrow someone discovered a closed-form equation for the nth prime, how would mathematics/the world change? [0] https://en.wikipedia.org/wiki/Recamán%27s_sequence
There are two main operations for whole numbers: addition and multiplication. A basic question is what are the "atoms". With respect to addition, the atom is 1, since every number can be written as a sum of 1's, and 1 isn't itself a nontrivial sum. With respect to multiplication, the atoms are the primes, where primes aren't nontrivial products.
A cool thing about breaking a number into multiplicative atoms (the "prime decomposition") is that to multiply two numbers, you can just add up however many copies there are of each atom. Primes turn multiplication into addition in this way. In other words, each prime defines a sort of logarithm that measures the amount of that prime in a number, and knowing the "coordinate" in prime space is enough to determine the original number.
Then one might wonder what is the relationship between primes and addition. When you add two numbers, the prime decomposition of the result seems to be dramatically different from the decompositions of the summands. But there are patterns, like how the sum of even numbers is even. The abc conjecture[1] has to do with one of these patterns.
The relative order of the primes also is saying something about the relationship between addition and multiplication, since addition underlies how you compare two numbers. There are old results about the density of the primes as if they were following a random distribution.
I'm not sure if there's any deep structure that Recamán's sequence has anything to do with. All that seems to be interesting about it is that it evades our capabilities of determining whether every number eventually appears. The Collatz conjecture is similar in this way, though it is further complicated by the fact that it mixes the structures of multiplication and addition.
[1] https://en.wikipedia.org/wiki/Abc_conjecture
Going deeper, in algebraic geometry, what you do is take various number systems (called "rings" -- the integers are an example of a ring) and pretend each element is a function that measures some scalar quantity about an associated space. It's a bold and wild idea. There is a process by which you can figure out what the points of this associated space are, and, at least for the integers, there is one point for each prime. If you think about an integer n as a function defined on this space, then the evaluation of n at the point p ends up being equal to n mod p. All I'm trying to say by bringing this up is that primes are not just aesthetic, they have deep significance, with many analogs in other kinds of mathematics.
Re: Is This Prime?
#53I’ve always wondered: how feasible is it to implement an “isprime” function, via lookup table? If such methods are used, is cryptography getting weaker and weaker in practice as more large primes are discovered?
No, at the cryptographic scale of prime numbers the lookup table would need to be far too big in terms of both time to generate and storage required. For smaller numbers see various prime sieves (Atkin, Eratosthenes)
Time to generate I get, but you could always augment the table over time and fall back to standard methods otherwise (and store the result).
Storage I have a harder time wrapping my head around. Aren’t primes quite sparse at cryptographic magnitudes? And are the primes used for (say) 256-bit encryption about the same magnitude, narrowing the dimension of storage required?
Re: Is This Prime?
#54This reminds me of my favorite in-person magic trick to do. First, memorize all the two-digit primes. 25 numbers isn't that hard to memorize. Then, tell someone "Oh, I can instantly tell whether a number is prime or not. Give me a number, I'll tell you whether it's prime." If they tell you a number between 1 and 100, use your memorized list. Otherwise, it's a game of cold reading; if they just generated a random stri…
Also, most composites are divisible by 2, 3 or 5, all of which are very easy to check (for 3 just sum up the digits and if the result is divisible by 3, the original number is divisible by 3). 49, 77, and 91 are the only composites under 100 that is not divisible by one of those 3 numbers, making memorizing 25 numbers not even necessary. 49 and 77 are obviously composite to me making 91 the only number I bothered memorizing.
Re: Is This Prime?
#55Here is a "theorem" I learned: every number up to 100 which looks prime, is prime, except 91. Does anyone recall its name?
49 looks prime to me. Another commentator says it doesn't count because it's a square number, but square numbers don't really have a particular "look" to me in the same way that 2-digit numbers ending in 5 or with digits summing to a multiple of 3 do.
Your maths teacher didn't force you to memorize squares then.
Re: Is This Prime?
#56Earlier quoted context omitted.
No, at the cryptographic scale of prime numbers the lookup table would need to be far too big in terms of both time to generate and storage required. For smaller numbers see various prime sieves (Atkin, Eratosthenes)
Time to generate I get, but you could always augment the table over time and fall back to standard methods otherwise (and store the result). Storage I have a harder time wrapping my head around. Aren’t primes quite sparse at cryptographic magnitudes? And are the primes used for (say) 256-bit encryption about the same magnitude, narrowing the dimension of storage required?
The primes are quite dense. There are roughly n/log(n) primes below n. Meaning 1 in 256 numbers with 256 bits are prime. That's 2^(248) primes.
For RSA one typically use 2048 or 4096 bit primes.
Re: Is This Prime?
#57Earlier quoted context omitted.
No, at the cryptographic scale of prime numbers the lookup table would need to be far too big in terms of both time to generate and storage required. For smaller numbers see various prime sieves (Atkin, Eratosthenes)
Time to generate I get, but you could always augment the table over time and fall back to standard methods otherwise (and store the result). Storage I have a harder time wrapping my head around. Aren’t primes quite sparse at cryptographic magnitudes? And are the primes used for (say) 256-bit encryption about the same magnitude, narrowing the dimension of storage required?
If your question is purely "is the value prime" the Fermat primaility test is very fast, probably about as fast as a hash table lookup on a table that large. Running Baillie–PSW to eliminate false positives isn't a huge deal either as it will only need to run if Fermat passes. It's not a horrible idea on its face and may indeed be a little faster, at the cost of lots of memory. I don't know of a use case where it would be worth it.
Re: Is This Prime?
#58Earlier quoted context omitted.
49 looks prime to me. Another commentator says it doesn't count because it's a square number, but square numbers don't really have a particular "look" to me in the same way that 2-digit numbers ending in 5 or with digits summing to a multiple of 3 do.
Your maths teacher didn't force you to memorize squares then.
I did memorize the sequence and still have it memorized, but I have to enumerate them. They don't have a "look" to them.
Re: Is This Prime?
#59Earlier quoted context omitted.
No, at the cryptographic scale of prime numbers the lookup table would need to be far too big in terms of both time to generate and storage required. For smaller numbers see various prime sieves (Atkin, Eratosthenes)
Time to generate I get, but you could always augment the table over time and fall back to standard methods otherwise (and store the result). Storage I have a harder time wrapping my head around. Aren’t primes quite sparse at cryptographic magnitudes? And are the primes used for (say) 256-bit encryption about the same magnitude, narrowing the dimension of storage required?
[deleted]
Re: Is This Prime?
#60Here is a "theorem" I learned: every number up to 100 which looks prime, is prime, except 91. Does anyone recall its name?
Don’t know the name of the “theorem”, but I know the rhyme:
91 is not a prime
that one trips me every time.