with(numtheory);
"e.g. ElGamal Signature:";
"1. Alice selects a large prime p with a primitive root g and a random number a as follows:";
p:=738532373;
g:=13;
a:=3551;
"2. She computes:  A=g^a mod p";
A:=g^a mod p;
"(p,g,A)=(738532373, 13, 545999632): Alice's public key";
"3. Alice creates her signature as follows:";
"3(i). She randomly selects k with gcd(k,p-1)=1 & computes k^(-1) mod (p-1)";
for k from 3170 to 3190 do if gcd(k,p-1) = 1 then print(k)fi;od;

k:=3175;
k_inv := k^(-1) mod (p-1);

"3(ii) She computes:";
r:= g^k mod p;
"3(iii) She selects a publicly listed hash function h: X-->Y";
h[x] := 412971;
s := k_inv * (h[x] - a * r) mod (p-1);
"(r,s) := (584407299, 712727322): Alice's signature for the document x.";
"Alice then sends her signed document: (r,s,x) = (584407299, 712727322, x) to Bob for authentication.";
"4. Bob authenticates based on the following criterion:";
"Criterion: If A^r * r^s = g^h(x) mod p then Bob accepts the document as authentic, otherwise he rejects it.";
A&^r * r&^s mod p;
"While publicly known: g^h(x) = 13 &^ 412921 mod p = 395822009";
g&^h[x] mod p;
"Since A^r * r^s = g^h(x) mod p, Bob accepts the signed document (r,s,x) as authentic".