Join Log in
Score:2
Sam avatar Crypto

Verification through prime modulus

cr flag
Sam

Asking this question here since it has a flavor similar to some cryptographic protocols. How likely are two integers which are smaller than some threshold, mod by some prime number to have the same result? For example, what is the probability that $n_1 \mod p = n_2 \mod p$ if p is randomly picked from the first $N$ primes, and $n_1$ and $n_2$ are some integers smaller than say $2^N$.

127
2 + 1
Amit avatar
ci flag
Amit
Perhaps someone will find it fit to give you a precise answer, but until then you may want to take a look at: https://en.wikipedia.org/wiki/Prime_number_theorem My intuition is that you can apply it directly to solve your problem.
0
Reply
Score:2
kodlu avatar Crypto
sa flag
kodlu

Edit: In the light of @fgrieu's comment, I am assuming that we are given two distinct integers for simplicity, since the answer is only intended to be approximate. So my "bad event" is that two distinct integers collide after reduction modulo $m.$

An approximate answer which can easily be made more precise. It's convenient to change some variables. All logs are to base $e.$

Given two uniformly distributed integers in $[1,m]$ they collide after reduction modulo the prime $p$ with probability $1/p$. Actually if the prime is larger they will not collide but our case is predominantly the opposite since we can take $m=\lfloor 2^N\rfloor$ for your $N,$ and essentially recover your problem.

For the primes in the interval $I_i=(L_i,R_i]=(m/e^{i+1},m/e^i]\cap \mathbb{N}$ where $i\geq 0,$ this probability is upper bounded by $e^{i+1}/m$ by assuming the prime is selected from the left end of the interval.

These intervals partition $\{1,\ldots,m\}$ if we let $i$ range in $\{0,1,\ldots \lfloor \log m\rfloor\}.$ For the largest $i$ (leftmost interval) we can take the left end to be the integer $1,$ but use the estimate to be given below with no problems.

By the prime number theorem there are approximately $$ K_i=\frac{R_i}{\log R_i}-\frac{L_i}{\log L_i}\sim \frac{1}{e^i}\frac{m}{\log m}\left(1-\frac{1}{e}\right) :=\frac{(e-1)m}{\log m}\frac{1}{e^{i+1}} $$ primes in this interval.

Now we can estimate the overall probability via $$ P_{collision}=\sum_{i=0}^{\lceil \log m \rceil} \mathbb{P}\left[ p \in K_i\right]\frac{1}{p}\approx \sum_{i=0}^{\lceil \log m \rceil} \frac{\frac{(e-1)m}{\log m}\frac{1}{e^{i+1}}}{ \frac{m}{\log m} }\frac{1}{p} \leq \sum_{i=0}^{\lceil \log m \rceil}\frac{(e-1)}{e^{i+1}} \frac{e^i}{m} $$ which becomes $$ P_{collision} \leq \frac{(e-1)}{m} \sum_{i=0}^{\lceil \log m \rceil} e^{-1} \sim \frac{e-1}{e}\frac{\log m}{m}. $$ Note that we can make this collision probability small enough by increasing $m.$ You wanted to consider the first $N$ primes, which means $m\approx N \log N.$

Also this makes sense since we could just choose primes from the rightmost interval $K_0=(m/e,m],$ which is a fixed fraction of the whole interval $[1,m]$ and get essentially the same performance (note that the smaller primes are less discriminating) and we are already covering a $1-\frac{1}{e}$ fraction of the total interval.

+ 5
fgrieu avatar
ng flag
fgrieu
I'm getting the probability quickly converges to $1/p$, by excess. Are our results compatible?
0
Reply
kodlu avatar
sa flag
kodlu
I believe so, I am using $1/p$ as an estimate for a fixed $p$ but then actually considering choosing that $p$ randomly from some interval, so your $1/p$ verifies my estimate.
1
Reply
fgrieu avatar
ng flag
fgrieu
There are issues with _"Given two uniformly distributed integers in $[1,m]$ they collide after reduction modulo the prime $p$ with probability $1/p$. Actually if the prime is larger they will not collide."_ 1) if $p>m$ then the probability of collision is $1/m>1/p>0$. 2) if $m\bmod p\ne 0$ the probability of collision is larger than $1/p$. E.g. for $m=4$, $p=3$ the probability is $6/16=3/8>1/3$. My take at this probability is$$\bigl((m\bmod p)\lceil m/p\rceil^2+(p-(m\bmod p))\lfloor m/p\rfloor^2\bigr)/m^2\in\bigl[\lfloor m/p\rfloor/m,\lceil m/p\rceil/m\bigr]$$
1
Reply
kodlu avatar
sa flag
kodlu
@fgrieu see my explanation in the edit. your expression is correct, and for large $m$ and relatively large primes, my estimate should be quite accurate.
1
Reply
Sam avatar
cr flag
Sam
@fgrieu if $p > m$ then $n_1 \mod p = n_1$ and $n_2 \mod p = n_2$ so the probability of collision should be $0$?
0
Reply
Score:2
fgrieu avatar Crypto
ng flag
fgrieu

For all strictly positive integers $m$ and $p$, there are $m^2$ integer pairs $(n_1,n_2)$ with $0\le n_1<m$ and $0\le n_2<m$. For a given such $n_1$, there is either $\lceil m/p\rceil$ or (when that's different) $\lfloor m/p\rfloor$ such $n_2$ with $n_1\bmod p=n_2\bmod p$. Thus the probability that $n_1\bmod p=n_2\bmod p$ for uniform distribution of such $(n_1,n_2)$ is within the real interval $\bigl[\lfloor m/p\rfloor/m,\lceil m/p\rceil/m\bigr]$.

The desired probability is for $p$ the $N^\text{th}$ prime, that is $N=\pi(p)$, and $m=2^N$. The Prime Number Theorem tells $N\sim p/\ln p$, thus $2^N/p$ goes to infinity as $N$ grows. Thus with $m=2^N$, both sides of the interval $\bigl[\lfloor m/p\rfloor/m,\lceil m/p\rceil/m\bigr]$ for the desired probability are asymptotically equivalent to $1/p$.

Thus the desired probability is asymptotically equivalent to $1/p$ as $N$ or $p$ goes to infinity.

The exact formula for the probability, with $m=2^N$ and $N=\pi(p)$, is: $$\bigl((m\bmod p)\lceil m/p\rceil^2+(p-(m\bmod p))\lfloor m/p\rfloor^2\bigr)/m^2$$ That probability is exactly $1/p$ for $p=2$, and is slightly above $1/p$ for all other $p$: by at most 12.5% (for $p=3$), by less than a millionth for $p>42$, converging exponentially.

+ 5
fgrieu avatar
ng flag
fgrieu
@Sam: The question asks _"How likely are two integers ($n_1$ and $n_2$) which are smaller than some threshold ($m$), mod by some prime number ($p$) to have the same result?"_. Consistent with that, my answer takes into account the probability that $n_1=n_2$ before the reduction. kodlu's answer now makes it clear that it computes the probability that the reduction modulo $p$ _causes_ a collision _that did not exist without reduction_; that is, it's added _"How likely are two __distinct__ integers…"_. Indeed that later probability is $0$ when $p\ge m$. There's no much change for $m=2^{\pi(p)}$.
0
Reply
Sam avatar
cr flag
Sam
In wikipedia it says 'The prime number theorem is equivalent to the statement that the nth prime number $p_n$ satisfies $p_n \sim n\log(n)$, where $p_n$ is the value of the nth prime, rather than the number of prime (i.e., the $N$ we used here)
0
Reply
fgrieu avatar
ng flag
fgrieu
@Sam: Indeed there was an error in my answer, fixed now. Thanks for pointing it! I'm (now) using the part of [Wikipedia's statement](https://en.wikipedia.org/w/index.php?title=Prime_number_theorem&oldid=1136079904#Statement) reading $\pi(x)\sim x/\log x$, replacing $x$ with $p$ and $\pi(p)$ with $N$ per the context of the question, and $\log$ with $\ln$ to avoid possible confusion.
0
Reply
Sam avatar
cr flag
Sam
One more question: I'm not so sure why $m=2^N$ implies $[⌊m/p⌋/m,⌈m/p⌉/m] $ converges to $\frac{1}{p}$. From the looks of it $[⌊m/p⌋/m,⌈m/p⌉/m] $ is going to be $\frac{1}{p}$ regardless?
0
Reply
fgrieu avatar
ng flag
fgrieu
@Sam: My proof needs to show that $m/p$ goes to infinity as $p$ goes to infinity to prove that $⌊m/p⌋/p$ and $⌈m/p⌉/m$ are asymptotically equivalent to $1/p$ as $p$ goes to infinity. Towards this we need some relation between $m$ and $p$, which in the question is given by $m=2^N$ and $N=\pi(p)$. It's not enough that $m$ goes to infinity as $p$ goes to infinity: if we had $m=(3p+1)/2$ my argument falls apart and the probability is asymptotically equivalent to $5/(3p)$.
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.