Evaluate the fermat''s method algorithm, Engineering Mathematics

1. (i) How many digits does the number 101000 have when written to base 7 ?

(ii) Use the prime number theorem to estimate the proportion of prime numbers among the positive integers up to and including those with 1000 decimal digits.

(iii) Show that arbitrarily long sequences of consecutive composite numbers exist. (Hint: Consider the sequence of integers starting at n! + 2)

2. Use Fermat's method to factorise the number n = 11111 using a speed-up based on two moduli, as follows. First, develop a speed-up scheme for the modulus m1 = 3, then develop a similar scheme independently for the modulus m2 = 8, then combine the two schemes into a single scheme. Finally, execute the algorithm using the combined scheme.

3. Make four applications of the Miller{Rabin test to the number n = 137.

For a proper application of the test, the four bases a used should be chosen independently, but for ease of calculation, use any four distinct 1-digit numbers, excluding 0 and 1, chosen from the digits in your student ID. (If your ID doesn't have enough digits to do this, pick the remaining digits arbitrarily.)

Present the results of all the modular exponentiations implied by the test, and state precisely why each base used is or is not a Miller{Rabin witness for n.

Draw whatever conclusion about the primality or compositeness of n the test permits (making the invalid assumption, however, that your bases were chosen independently).

4. Consider the quadratic congruence ax2 +bx+c ≡ 0 (mod p), where p is a prime and a, b and c are integers with p/a.

(i) Determine which quadratic congruences have solutions when p = 2. Note that in this case a = 1 and b and c have to be 0 or 1.

(ii) For the case where p is an odd prime let d = b2 - 4ac and show that the given congruence is equivalent to solving y2 ≡ d (mod p), where y = 2ax + b. Hence show that for d ≡ 0 (mod p) there is exactly one least residue solution for x, for d a quadratic residue there are two least residue solutions for x and for d a quadratic nonresidue there are no solutions for x.

(iii) Illustrate these results by considering x2 + x + 1 ≡0 (mod 7), x2 + 5x + 1 ≡ 0 (mod 7) and x2 + 3x + 1 ≡ 0 (mod 7).

5. Use the ElGamal Cryptosystem with prime p = 2591, primitive root a = 7 and c = 591.

(i) Verify that the private key is b = 99.

(ii) Choose a 3-digit number k by selecting any 3 consecutive digits from your student ID, provided that the first digit is not 0. Then use k to encode the message

x = 457.

(iii) Decode the result from (ii) to give back x.

You will probably need to use a computer to do the calculations and you should attach a copy of the output.

Posted Date: 3/15/2013 6:19:35 AM | Location : United States







Related Discussions:- Evaluate the fermat''s method algorithm, Assignment Help, Ask Question on Evaluate the fermat''s method algorithm, Get Answer, Expert's Help, Evaluate the fermat''s method algorithm Discussions

Write discussion on Evaluate the fermat''s method algorithm
Your posts are moderated
Related Questions
(i) Test for the existence of regression (the F-test). Carefully de ne the null and alternative hypothesis, and explain the result of any R output you obtain. (ii) Which of the

As an engineering student, the ministry of energy and minerals has tasked you to help them model equation(s) that can estimate the amount of crude oil in a reservoir. The governmen

The table summarizes results from a clinical trial (based on data from Pfizer, Inc). Use a 0.05 significance level to test the claim that experiencing nausea is independent of whet

analyn bought a dining set.She paid 2500 as a downpayment and promised to pay 800 @ the end of each month for year.What s the cash eqivalent of the set if the interest rate is 10%

The following are 8 data points that shows the relationship between the number of fishermen and the amount of fish they can catch a day. (Let the number of fishermen be X and the a

First systems were described as systems that had one method of storing energy.  Second order systems; wait for it.... have two methods of storing energy.  Using a similar mechanica

I. The inventory of  records of BeBop Distributing reflected the following for October 2012: Date                      Transaction                              Units

''A three phase cage induction motor running at full load draws a stator current of 60A at a power factor of 0.8 lagging from a 415v, 50hz supply. Under the following conditions th


Valid objective function for a LPP with x,y,z as decision variables