ගණන් හදන්න උදව්වක් දෙන්න
කවුරුහරි මේ ගණන් ටික හදන විදිය දන්නවද? ලොකු උදව්වක් කරලා දෙන්න පුළුවන් නම්.
Consider an expression of the form
0 ≡ a x2 + b x + c ( mod n ).
1. Show that the x’s of the following form are all solutions of the above system: .
. x ≡ (−b ± √ b2 – 4ac ) (2a)−1 ( mod n )
when gcd(2a,n) = 1 and (b2 – 4ac) is a Quadratic Residue modulo n. (Here √q is an integer square root of a quadratic residue q modulo n.)
2. Give all the necessary and sufficient conditions for existence of solutions to the above system and for any tuple of parameters (a,b,c,n) specify how many solutions exist ?
Probability Calculate a best upper bound on the probability that we mistakenly output a composite number instead of a prime after the following events have occurred:
1. pick a random m-bit integer n such that gcd(n,210)=1
11. The procedure Miller-Rabin_prime(n,k) returns ‘prime’
Assume that the prime number theorem is exact.
(Pi
log n) /n =1
2) If I want a random 4096 bits prime p, what k should be used in MillerRabin_prime (p,k) to guarantee probability at most 1/250 of outputting a composite number?
කවුරුහරි මේ ගණන් ටික හදන විදිය දන්නවද? ලොකු උදව්වක් කරලා දෙන්න පුළුවන් නම්.
Consider an expression of the form
0 ≡ a x2 + b x + c ( mod n ).
1. Show that the x’s of the following form are all solutions of the above system: .
. x ≡ (−b ± √ b2 – 4ac ) (2a)−1 ( mod n )
when gcd(2a,n) = 1 and (b2 – 4ac) is a Quadratic Residue modulo n. (Here √q is an integer square root of a quadratic residue q modulo n.)
2. Give all the necessary and sufficient conditions for existence of solutions to the above system and for any tuple of parameters (a,b,c,n) specify how many solutions exist ?
Probability Calculate a best upper bound on the probability that we mistakenly output a composite number instead of a prime after the following events have occurred:
1. pick a random m-bit integer n such that gcd(n,210)=1
11. The procedure Miller-Rabin_prime(n,k) returns ‘prime’
Assume that the prime number theorem is exact.
(Pi
log n) /n =12) If I want a random 4096 bits prime p, what k should be used in MillerRabin_prime (p,k) to guarantee probability at most 1/250 of outputting a composite number?
Last edited:
