1. [3 pt](Why the ⇢ method works) In lecture, we have mentioned the following theorem, which ensures the validity of the rho method:
Theorem LetSbeasetofrelements. Givenamapf:S!S,and an element x0 2 S, let xj+1 = f(xj) for j = 0,1,2,…. Let be a positive real number, and let l 2 N s.t. l > p2 r, then the proportion of pair (f, x0) for which x0, x1, …, xl are distinct, where f run over all maps from S to S and x0 runs over all elements of S, is less than e
Hint You will need to use some combinatorics, as we discussed this week. You might also want to use that
log(1 x)< x, 8x2(0,1)
Code Help
2. [2 pt](How the ⇢ method works) Perform the ⇢ method to factorise n = pq.
(a) f(x)=x2 +1, x0 =2, n=91
(b) f(x)=x3 +x+1, x0 =1, n=2701
Programming Help, Add QQ: 749389476
3. [3 pt](Fermat’s Method of Factorisation) In this exercise, we intro- duce another useful method of factorisation for n = pq, namely the Fer- mat’s method. This method is particualrly useful when the gap between p and q is not too large.
(a) [1 pt] Let n be a positive integer. Define a function f between
• factorisationsofnintheformn=ab,wherea b>0,and
• representations of n in the form n = t2 s2, where s, t are non-
negative integers.
The function f is given by:
f a+b a b (a,b) ! (t,s),f(a,b) = ( 2 , 2 )
Prove that f is a bijection.
(b) [1 pt] Note that if n = ab with a, b being close to each other, then
s = a b is small, Now show that 2
pn t pn + s.
(c) [1 pt] Now we can use the following algorithm: We try t = pn + 1, pn + 2, pn + 3,… until t2 n is a perfect square (which is s2). Then once we obtained t, we solve s = pt2 n to get s. Finally we use s, t to compute a, b. Use this method to factorise n = 200819.
Computer Science Tutoring