a Estimate how many 768bit prime numbers are there b Generat

a) Estimate how many 768-bit prime numbers are there?
b) Generate 10 distinct 768-bit prime numbers and measure their generation time.

Solution

a) Estimate how many 768-bit prime numbers are there?

ANSWER

The RSA-768 composite integer n can be factored by finding integer solutions x, y of the congruence of squares x 2 y 2 mod n, and by hoping that n is factored by writing it as a product gcd(x y, n) · gcd(x + y, n).

For a random such pair the probability is at least 1 2 that a non-trivial factor of n is found in this way.

The Morrison-Brillhart approach solves the equation x 2 y 2 mod n by combining congruences of smooth squares.

Now, Explain this in the present section A non-zero integer u is b-smooth if the prime factors of |u| are at most b.

Each b-smooth integer u corresponds to the ((b) + 1)-dimensional integer vector v(u) of exponents of the primes b in its factorization, where (b) is the number of primes b and the “+1” accounts for inclusion of the exponent of 1.

The factor base consists of the primes at most equal to the smoothness bound. Let n be a composite integer, b a smoothness bound, and t a positive integer.

Suppose that (b) + 1 + t different integers v have been found such that the least absolute remainders r(v) = v 2 mod n are b-smooth. Because the corresponding ((b) + 1)-dimensional vectors v(r(v)) are linearly dependent, at least t independent subsets S of the v’s can be found using linear algebra .

such that, for each of these subsets, P vS v(r(v)) is an all-even vector.

Each subset S then leads to a solution x = Q vS v and y = pQ vS r(v) to x 2 y 2 mod n and thus, Finally,t chances of at least 1 2 to factor n.

If v’s as above are generated by picking random integers and hoping that the least absolute remainder modulo n of their square is smooth, the search for the proper v’s depends on the smoothness probability of integers of the same order of magnitude as n. to combine essentially the same high smoothness probability with a fast sieving-based method to recognize the smooth numbers .Factoring methods of this sort that rely on smoothness of residues of order n (1) can be shown to be stuck at expected runtimes of the form e (c+o(1))(ln n) 1/2 (ln ln n) 1/2 , for positive constants c and asymptotically for n . This is achieved by looking at more contrived congruences that involve smoothness of numbers of order n o(1), for n , be combined into a congruence of squares x 2 y 2 mod n. As a result, the number field factors a composite integer n in heuristic expected time e ((64/9)1/3+o(1))(ln n) 1/3 (ln ln n) 2/3 , asymptotically for n . It is currently the algorithm of choice to factor numbers without special properties, such as those on the RSA Challenge , we concentrate on the number RSA-768, a 768-bit RSA modulus with 232-digit decimal representation. so,final decimal representation is

123018668453011775513049495838496272077285356959533479219732245215172640050726 365751874520219978646938995647494277406384592519255732630345373154826850791702 6122142913461670429214311602221240479274737794080665351419597459856902143413.