As mentioned in this StackOverflow CodeGolf question, prime numbers can be redefined:

One of my favorite definitions of the prime numbers goes as follows:

  • 2 is the smallest prime.
  • Numbers larger than 2 are prime if they are not divisible by a smaller prime.

However this definition seems arbitrary, why 2? Why not some other number? Well lets try some other numbers will define n-prime such that

  • n is the smallest n-prime.
  • Numbers larger than n are n-prime if they are not divisible by a smaller n-prime.

based on this notion, and we find a union of "real primes" and this fictional subset:

  • Are there any cryptographic algorithms, stenography approaches that can be adapted to use an n-prime?

  • If I look at the case of n-prime == 2, I assume that there are computation and size efficiencies vs other values for n-prime. What other benefits does n-prime == 2 offer?

  • Similarly how the primes 3 and 65537 provide cryptographic benefits as RSA exponents, are there other worthwhile values for n-prime?

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Dec 17 '17 at 13:53

Sorry, but I think this definition of “n-prime” number is just nonsense.

Mathematicians defined prime numbers the way they did, because it provides a set of numbers with interesting mathematical properties. A simple example is that any positive integer is the product of prime numbers.

With that definition of “n-prime” numbers, 4 would be 3-prime and 8 would not (since it is divisible by 4). Then 8 is not a product of 3-prime numbers.

For cryptography, prime numbers are often used because $\mathbb Z/p\mathbb Z$ is a finite field. But that’s only true for “real” prime numbers, not for “n-prime” numbers that are not prime numbers.

By the way, I hate that definition of prime number that you quoted, because it gives the feeling that there’s something special with 2, while there is not.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.