Let Bob’s public lock be (n, p) where n = q 1 q 2 . Assume p is a 400 digit prim

Question

Let Bob’s public lock be (n, p) where n = q1q2. Assume p is a 400 digit prime and q1, q2 are 200 digit primes. In this question Alice is sending a message M to Bob, where 0 < M < n. Let Mˆ be her encrypted message.

A message M is often deemed to be “insecure” if gcd(M,n) > 1. Suppose we want to comfort ourselves that such messages are rare. Let us assume that messages M are equally likely to be sent. That is, each M {2,3,...,n 1}

is equally likely to be a message being sent to Bob. Derive an upper bound on the probability that gcd(M, n) > 1.

Explanation / Answer

Let us Consider a example

let q1=5 and q2=7. n=q1q2=35.
M belongs to the set {2,3,...,34} which has 33 elements (=n-2).

The numbers for which gcd(M,n)>1 are 5,10,15,20,25,30 and 7,14,21,28.
Thus there are 10 (=q1+q2-2) numbers for which gcd(M,n)>1.
Thus the probability that gcd(M,n)>1 is (q1+q2-2)/(n-2).

For the actual example where q1 and q2 are 200 digit numbers:
q1<10^200 and q2<10^200
n>10^398
An upper bound on the probability that gcd(M; n) > 1is 2x10^200/10^398 = 2/10^198.

One can actually get an even lower upper bound U. Since n=q1q2,
U=(q1+q2-2)/(n-2)=(q1+q2-2)/(q1q2-2)
Without lost of generality assume q1<q2 and divide top and bottom by q2:
U=(q1/q2+1-2/q2)/(q1-2/q2)
q1>10^199+1
(q1 can't be 10^199 because it is prime and q1 can't be 10^199+1 because that number is divisible by 11.)
Thus q1/q2+1-2/q2 is less than 2.
q1-2/q2 is greater than 10^199
U<2/10^199

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.