Recent news reported about the discovery of a "Prime Conspiracy" which can be read about .   In summary, researchers have discovered that the last digit of prime numbers have a greater predictability than random. The cited example is that primes ending in 9, have a 65% chance of the next prime ending in 1. I am curious if any thought has been generated around the impact this might have to cryptography, namely popular encryption methods like RSA?
122701
reports:  Two mathematicians have uncovered a simple, previously unnoticed property of prime numbers [...]. Prime numbers, it seems, have decided preferences about the final digits of the primes that immediately follow them. Among the first billion prime numbers, for instance, a prime ending in 9 is almost 65 percent more likely to be followed by a prime ending in 1 than another prime ending in 9.  Do these insights make breaking keys based on primes more mathematically plausible in a shorter amount of time?
105086
The private key is any random 256 bit (but smaller than prime p) number or must be prime or other condition? For selected $x$ can be found $y$ - decompressing key: #! /usr/bin/env python3 import binascii import math p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F def decompress_pubkey(pk):     x = int.from_bytes(pk[1:33], byteorder='big')     y_sq = (pow(x, 3, p) + 7) % p     y = pow(y_sq, (p + 1) // 4, p)     if y % 2 != pk[0] % 2:         y = p - y     y = y.to_bytes(32, byteorder='big')     return b'\x04' + pk[1:33] + y  print(binascii.hexlify(decompress_pubkey(binascii.unhexlify('0229b3e0919adc41a316aad4f41444d9bf3a9b639550f2aa735676ffff25ba3898'))).decode()) print(binascii.hexlify(decompress_pubkey(binascii.unhexlify('02f15446771c5c585dd25d8d62df5195b77799aa8eac2f2196c54b73ca05f72f27'))).decode()) print(binascii.hexlify(decompress_pubkey(binascii.unhexlify('0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798'))).decode())  Only last x,y pair fulfill (x3+7-y2) % p is zero. Two previous pairs are wrong?
56984
I am a software engineer but try to keep up with maths as I really enjoyed the subject at school. I just saw a great TED talk:   The talk states that the current largest known prime is $2^{57885161}-1$  This got me thinking - how does one actually prove whether a number this large is prime or not?  Is it just done by brute force via a computer algorithm or are there any well known mathematical techniques for doing so?  I would be really grateful for any pointers as I am eager to learn about these techniques (if they exist).
85848
Prime numbers are numbers with no factors other than one and itself.  Factors of a number are always lower or equal to than a given number; so, the larger the number is, the larger the pool of "possible factors" that number might have.  So the larger the number, it seems like the less likely the number is to be a prime.  Surely there must be a number where, simply, every number above it has some other factors.  A "critical point" where every number larger than it simply will always have some factors other than one and itself.  Has there been any research as to finding this critical point, or has it been proven not to exist?  That for any $n$ there is always guaranteed to be a number higher than $n$ that has no factors other than one and itself?
5019
What is the best approach to calculating the largest prime factor of a number?  I'm thinking the most efficient would be the following:   Find lowest prime number that divides cleanly Check if result of division is prime If not, find next lowest Go to 2.   I'm basing this assumption on it being easier to calculate the small prime factors. Is this about right? What other approaches should I look into?  Edit: I've now realised that my approach is futile if there are more than 2 prime factors in play, since step 2 fails when the result is a product of two other primes, therefore a recursive algorithm is needed.  Edit again: And now I've realised that this does still work, because the last found prime number has to be the highest one, therefore any further testing of the non-prime result from step 2 would result in a smaller prime.
91983
I don't have the background for dealing with Riemann hypothesis but is well known that covers the prime distribution below a specified number.  In order to solve the RSA problem you have to factor the semiprime or calculate the totient itself, that's hard as factoring the modulus.  Question is, could Riemann hypothesis be used to calculate how many coprimes are below the modulus by counting the primes below $n$ and also counting how many products of those primes are below $n$, except those involving $p$ and $q$?  If the previous is negative, can someone clarify why some people say that Riemann hypothesis could "break" RSA?  Thanks for your patience and comprehension.
45734
$p_1, p_2$ are distinct prime numbers  I have just observed this pattern when solving  problem. Is there a simple way to prove/disprove it ?
71065
I see a lot of Q/A where persons are trying to generate a specific key pair using static data such as a password. Now say we use a known PRNG (dangerous assumption), seeded with a the data as a static seed, would this always generate the same key pair?  I presume it would generate the same key pair if you would use the exact same generation method - the application would be deterministic. I would however expect differences between implementations. The random data could be used differently, the sizes of p and q could differ and there may be subtle differences when choosing the prime numbers themselves.
3348
I was wondering how many possible private/public keys exist? If a million people – for whatever reason – would try to generate 5 keys each in the same minute (on the same date and time) is there a high chance of collision? I believe GUID would suffer from that problem as many bits are reversed for date/time (and GUID version) and isn't meant to be used in that way.  Would RSA suffer from collisions if many keys were to be generated in the same moment? Is the amount of possible keys known? I know RSA is based on prime numbers and small numbers are to be rejected. I’m sure values above a certain amount of digits/bits are rejected because software may not be able to support those large values?  So: How many RSA keys before a collision? And if you would try to make many at the same time, would that give you a high chance of collision?
13882
It is possible to find an efficient algorithm for constructing a provably hard to factor number $N$, together with a witness that shows that it is indeed hard to factor. EDIT, since it was not clear: I also want to be sure that even the person that constructed the number cannot factor it.  Of course, a random large enough integer is going to be hard to factor with high probability, but we might be unlucky.  There are also multi-party protocols for shared generation of RSA moduli (such as ), but I would like a non interactive technique.  Motivation: This was suggested by Poncho's answer to
22883
I was reading today that someone found $\pi$ to the ten trillionth digit.  Whenever I read that $\pi$ has been calculated to more digits, I ask myself whether this is useful.  I know that there are conjectures out there about distributions of numbers in $\pi$ and such.  So, I supposed knowing more digits helps us test conjectures.  But, are there more reasons that we would want to know the digits?  Anything really cool I'm ignoring or forgetting?
103915
I read an essay about prime numbers. In it the author suggests that a natural first question to ask is,      What is the probability of a random natural number being prime?   but proceeds to dismiss it as "not making sense". I wonder what's wrong with the question. Is its meaninglessness related to the fact that there is an infinite number of naturals?
83084
I'm interested in some sort of "compendium" on lattice-based crypto. There are a bunch of maths behind FALCON and other stuff. A lot of articles are devoted to lattice crypto, but not of them are of paramount importance. The other problem is that there are papers that are obviously influential, but they are hard to understand "from scratch".  To start with something I may notice some of them:  GPV framework:    "How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Constructions".   Cryptanalysis:    "Learning  a  Parallelepiped:  Cryptanalysis  of  GGH and NTRU Signatures"   Basic courses :   winter school on lattice-based crypto () Regev course on lattices in CS () Vinod's course ()   Surveys:   "Lattice-based Cryptography" part from the book "Post-Quantum Cryptography". "A Decade of Lattice Cryptography", Peikert.   Unfortunately, I didn't find anything on discrete Gaussian distributions and properties of continuous Gaussians (why is it "not far from" uniform over any "small" parallelopiped), how to generate them; on smoothing parameter and its "intuitive" meaning. Also, reductions from average to worst-case are somewhat tricky and uneasy to understand form Ajtai papers. And there is a direction of research on ideal lattices, which somehow related to integer rings of number fields ($\mathbb{Z}_K$), this is completely obscure.
12059
I understand the use of pseudo-random number generators. I am not getting mixed up between these and "real" random number generators.  However, I don't understand for what a real random number generator is used. If it is not deterministic, how can it be used in an algorithm?
101847
I have been reading about . I was wondering if this attack is feasible while signing with RSA and, if yes, how?    Also, how this kind of attack is applied with DH?   Talking about timing attacks in general, in which way AES is affected and how to solve it? (I mean, with RSA the "problem" is at multiplication level, while for AES where is the problem that makes the cipher implementation key or data dependent?)
29694
Say I want a random 1024-bit prime $p$.  The obviously-correct way to do this is select a random 1024-bit number and test its primality with the usual well-known tests.  But suppose instead that I do this:   select random odd 1024-bit number $n$ if $n$ is prime, return $n$ $n \leftarrow n+2$ goto 2   (This approach allows faster selection of primes via sieving.)  Since primes are not uniformly distributed on the number line, it would seem that this algorithm prefers primes that lie after long runs of composites.  Take a piece of the number line around $2^{1024}$ with x denoting a prime:     ---x-x----------------------------x------------------------x---x   Clearly our algorithm above is much more likely to find the 3rd prime above than to find the 2nd one.  Question: Is this a problem?
79314
Suppose that there is a prime number. Now I want to approximate the next prime number. (It does not have to be exact.) What would be the time-efficient way to do this?  Edit: what happens if we limit the case to the prime number of the form $4k+1$ where k is a natural number?   Edit: it's fine to replace approximate prime number with finding any prime number that is bigger than the given prime number in a time-efficient way.