CA I - Exercise sheet 09

Exercise 1: (RSA - Bad choice of primes)

1.

Consider  (((⌈(Sqrt[n])⌉+k))^2)-n  for r k=0,1,2,…and check for each k, if the obtained number is a squarre. If it is the case, solve then the obtained system of equations.

2.

Fermat[n_]:=Module[{i,p,sqr},
p=Ceiling[Sqrt[n]];
i=0;
While[Not[IntegerQ[sqr=Sqrt[(p+i)^2-n]]] && i≤10000,i++];
If[i≤ 10000,
sol=Solve[{sqr==(a-b)/2,i==(a+b)/2},{a,b}];
{p+a,p+b}/.sol[[1]],
"No factorization is found!"]
]

Fermat[4143977748966434243307454492626122211734875100576213552709682305695820526691442409]

Fermat[Prime[1000000] Prime[1050000]]

FactorInteger[Prime[1000000] Prime[1050000]]//MatrixForm

Exercise 2: (Modular Logarithm)

(a)

x≡(Subscript[log, a])b  mod p  ⟺  (a^x)≡b  mod p  ⟺  (a^(q·n+r))≡b  mod p  ⟺  (a^r)≡b·(a^(-q·n))  mod p

(b)

Clear[ModLog3];
ModLog3[a_,b_,p_]:=Module[{n=Floor[Sqrt[p]],x=b,M,u,q},
M=Table[PowerMod[a,r,p],{r,0,n-1}];
u=PowerMod[a,-n,p];
For [q=0,q<n,q++,
If[MemberQ[M,x],
r=Flatten[Position[M,x]][[1]]-1;
Return[Mod[q n+r,p]]
];
x=Mod[x u,p];
];
"There exist no modular algorithm"
]

(i)

ModLog3[2,5,7]

(ii)

ModLog3[5,8,13]

(iii)

ModLog3[16643,3376,104729]

Timing[ModLog3[46508,82344,6416953]]

The Babystep-Giantstep-algorithm needs to compute in the worst case   2(Sqrt[p])  powers.