问题描述:

Hi I was wondering if anyone can help me with the following question My attempt for part a is below.

I don't understand why my procedure isn't working, it runs but then gives no values back when evaluating the procedure for part b. I have used the print command to check if the array is finding a match which it seems to be doing, but it looks like it is just ignoring it

The protocol for baby step giant step is as follows

and the protocol for EL gamal is

My procedure is as follows:

`proc3 := proc (alpha, beta, p)`

local k, R, i, j, N, A, t;

description "baby step giant step procedure";

N := floor(sqrt(p-1))+1;

A := Array(0 .. N);

for j from 0 to N do

A[j] := `mod`(alpha^j, p)

oo;

for i from 0 to N do

t := (beta*alpha^(-N*i))modp;

for k from 0 to N do

print(t, A[k]);

if t = A*[k] then

return k+N*i;

fi;

od;

od;

end proc;

when i do

proc3(3, 64, 137)

it returns nothing so i put the print command in and now it gives

`64, 1`

64, 3

64, 9

64, 27

64, 81

64, 106

64, 44

64, 132

64, 122

64, 92

64, 2

64, 6

64, 18

34, 1

34, 3

34, 9

34, 27

34, 81

34, 106

34, 44

34, 132

34, 122

34, 92

34, 2

34, 6

34, 18

78, 1

78, 3

78, 9

78, 27

78, 81

78, 106

78, 44

78, 132

78, 122

78, 92

78, 2

78, 6

78, 18

50, 1

50, 3

50, 9

50, 27

50, 81

50, 106

50, 44

50, 132

50, 122

50, 92

50, 2

50, 6

50, 18

18, 1

18, 3

18, 9

18, 27

18, 81

18, 106

18, 44

18, 132

18, 122

18, 92

18, 2

18, 6

18, 18

1, 1

1, 3

1, 9

1, 27

1, 81

1, 106

1, 44

1, 132

1, 122

1, 92

1, 2

1, 6

1, 18

99, 1

99, 3

99, 9

99, 27

99, 81

99, 106

99, 44

99, 132

99, 122

99, 92

99, 2

99, 6

99, 18

74, 1

74, 3

74, 9

74, 27

74, 81

74, 106

74, 44

74, 132

74, 122

74, 92

74, 2

74, 6

74, 18

65, 1

65, 3

65, 9

65, 27

65, 81

65, 106

65, 44

65, 132

65, 122

65, 92

65, 2

65, 6

65, 18

133, 1

133, 3

133, 9

133, 27

133, 81

133, 106

133, 44

133, 132

133, 122

133, 92

133, 2

133, 6

133, 18

15, 1

15, 3

15, 9

15, 27

15, 81

15, 106

15, 44

15, 132

15, 122

15, 92

15, 2

15, 6

15, 18

115, 1

115, 3

115, 9

115, 27

115, 81

115, 106

115, 44

115, 132

115, 122

115, 92

115, 2

115, 6

115, 18

14, 1

14, 3

14, 9

14, 27

14, 81

14, 106

14, 44

14, 132

14, 122

14, 92

14, 2

14, 6

14, 18

as you can clearly see the match is at 18,18 but for some reason it isnt taking this into account, can anyone see what i am doing wrong? its starting to become stressful. also how can we increase the efficiency of the procedure so it can calculate x for larger values of a,b and p. for part c i know i need to use the procedure from part a.

Any help would be appreciated thanks for taking time to read this.

my procedure for part c is as follows

`Elgamal := proc (ciphy, hkt, p, a, b)`

local i, icdarray, s, q;

icdarray := Array(5 .. 388);

for i from 5 to 388 do

s := ciphy[i];

q := `mod`(1/hkt^proc3(a, b, p), p);

icdarray[i] := s*q;

end do;

return convert(icdarray, bytes);

end proc;

where proc3 is as follows

`proc3 := proc (alpha, beta, p)`

local k, R, i, j, N, A, t;

Description "baby step giant step procedure";

N := floor(sqrt(p-1))+1;

A := Array(0 .. N);

for j from 0 to N do

A[j] := `mod`(alpha&^j, p);

end do;

for i from 0 to N do

t := `mod`(beta*alpha&^(-N*i), p);

for k from 0 to N do

if t = A[k]

then return k+N*i;

end if;

end do;

end do;

end proc;

Your conditional test is `if t = A*[k] then`

where you have made a typo since you want `A[k]`

instead of that multiplication.

If you are using 2D Math input mode then a space in the input between A and [ would get parsed as implicit multiplication. If this was your case here, or if you repeatedly get caught out by that then consider switching to 1D Notation input mode (a GUI preference).