Evaluate the fermat''s method algorithm, Engineering Mathematics

Assignment Help:

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.


Related Discussions:- Evaluate the fermat''s method algorithm

Truss elements and fe project, A new gantry crane for a metal fabrication s...

A new gantry crane for a metal fabrication shop is to be designed. The designer has proposed the following two different configurations: A. Using only truss elements B. Using the

Estimate the time constant and maximum vertical acceleration, The vertical ...

The vertical motion of a general aviation airplane subjected to a sharp-edged wind gust is described by the equation Δw(t) = A g (1-e -t/τ ) assume A g = 30 where Δ w is in

Provide a derivation, This is a pen and paper exercise, you are expected to...

This is a pen and paper exercise, you are expected to provide a detailed derivation. Follow the procedure outlined in the lectures for construction of a simple averaging by thr

Database management system, outline the three schema database architecture ...

outline the three schema database architecture clearly explaining each level and how the user view the information

Produce a discrete time series, Produce a discrete time series y(t i ) by s...

Produce a discrete time series y(t i ) by super positioning 5 cosinusoidal components, for your own choice of the amplitudes (a j ) and frequencies (f j ). Add some Gaus

Calculate the cost of manufacturing, A manager has determined the cost C, i...

A manager has determined the cost C, in dollars, for manufacturing is C(q) =85log 10 (10+q/2) for manufacturing, where q is the number of units produced in a given day. (a

Substitution method, Answer the following set of simultaneous equations usi...

Answer the following set of simultaneous equations using elimination or substitution method. a) x-y +z= 10 b) 3x+y+2z=34 c) -5x+2y-z=-14

Dynamics, The acceleration of an oscillating particle is defined by the rel...

The acceleration of an oscillating particle is defined by the relation a = -kx Determine the value of k such that v = 15 in./s when x = 0 and x = 3 in. and v = 0, the speed of the

MEAN VALUE THEORM, APPLICATIONS OF LAGRANGE''S MEAN VALUE THEORM?

APPLICATIONS OF LAGRANGE''S MEAN VALUE THEORM?

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd