forum.math.uoa.gr

Έχει κανείς ιδέα πως λύνεται αυτή η άσκηση στο 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.)