Έχει κανείς ιδέα πως λύνεται αυτή η άσκηση στο mathematica;
5. Index calculus for DLP in F^*_p
---------- Exercise 5 In this exercise you should use index calculus to solve the following DLP: g^x=h (mod p) where p=486130339139 g=1301 h=56499970361
The following simple function computes random powers g^i (mod p) and returns the first it finds that is B-smooth, where B is the b:th prime number.
GuessSmoothPowers=Function[{g,p,b}, Module[{res,Lp,st,i,gi,git,j,gie,Lgie}, Lp=Map[Prime,Range[b]];st=0; While[st==0, i=RandomInteger[{2,p-2}];gi=PowerMod[g,i,p]; git=gi;Lgie={};For[j=0,j<Length[Lp],j++,gie=IntegerExponent[git,Lp[[j+1]]];Lgie=Append[Lgie,gie];git=git/Lp[[j+1]]^gie];If[git==1,st=1;res={Lgie,i}] ]; res ]]
Try, for example: R1=GuessSmoothPowers[2,853,4]
When I did this the outcome was: {{3,2,1,0},90} which means that 2^90=2^3*3^2*5^1*7^0 mod 853.
To take the r:th element of a list R then type R[[r]]. Try for example: R1[[1]]
If A is a matrix and b a vector then LinearSolve[A,b,Modulus->p] computes one solution to the equation A*x=b mod p. Try, for example: LinearSolve[{{1,2},{1,3}},{4,7},Modulus->11] where the matrix A has rows {1,2} and {1,3}.
If r={r1,...,rk} and m={m1,...,mk} then ChineseRemainder[r,m] computes the solution to the set of equations x=ri mod mi for i=1,..,k. Try, for example: ChineseRemainder[{3,7},{7,11}]
Finally, the following function computes the smallest k such that h*g^(-k) (mod p) is B-smooth, where B is the b:th prime number.
Smoothen=Function[{g,h,p,b}, Module[{Lp,st,gh,k,ght,Lghe,j,ghe}, Lp=Map[Prime,Range[b]];st=0;gh=h; For[k=0,k<p&st==0,ght=gh;Lghe={};For[j=0,j<Length[Lp],j++,ghe=IntegerExponent[ght,Lp[[j+1]]];Lghe=Append[Lghe,ghe];ght=ght/Lp[[j+1]]^ghe];If[ght==1,st=1,gh=Mod[gh*PowerMod[g,-1,p],p];k++]]; Print["k=",k];FactorInteger[gh]]]
(a) What is the theoretically suggested value for B that should make the hunt with GuessSmoothPowers the most efficient? Time how long it takes to find a "smooth power" for this value of B.
(b) Solve the DLP using index calculus. (You might want to use a smaller B than the theoretical one suggested in (a) to decrease the number of times you need to use the function GuessSmoothPowers.)
|