10225  Discrete Logging
Moderator: Board moderators

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
He means the "Baby step giant step" algorithm of Shanks. It computes the discrete logarithm, exactly what this problem asks for. It think it's in the book of Cormen etc. Should also be easy to find in Google. Basically it's some sort of bidirectional search where you save time, but pay space. That's a useful principle, btw.
<font size=1>[ This Message was edited by: Stefan Pochmann on 20020321 11:42 ]</font>
<font size=1>[ This Message was edited by: Stefan Pochmann on 20020321 11:42 ]</font>

 Learning poster
 Posts: 76
 Joined: Thu Mar 13, 2003 5:12 am
 Location: Russia
I have managed to find just a small article ( pdf )
which describes Shank's algorithm for
solving x^2 = N ( mod P ). Solving means finding X.
In that algorithm P is not necessarily prime,
as far as I understand.
Well, our task in this problem is slightly different. We need to
compule the smallest K>=0, such that B ^ K = N ( mod P ).
Here P ( prime ), B and N are given.
Can someone point to some Web resources
where a good description of Shank's algorithm
could be found ?
which describes Shank's algorithm for
solving x^2 = N ( mod P ). Solving means finding X.
In that algorithm P is not necessarily prime,
as far as I understand.
Well, our task in this problem is slightly different. We need to
compule the smallest K>=0, such that B ^ K = N ( mod P ).
Here P ( prime ), B and N are given.
Can someone point to some Web resources
where a good description of Shank's algorithm
could be found ?
Experimenter, as far as my modest knowledge of arithmetics
allows me to understand, the hints they give about Fermat's
theorem are related to the following.
1) B < P means GCD ( B, P ) = 1
2) Let's have a look at the sequence
S = { B^K  k=0,1,2,3... }
and in more detail let's look at its first P elements:
which form the sequence:
A = { 1, B, B^2... , B^(P1) }.
Sequence A has P members.
We know ( from Fermat's theorem ):
B^(P1) = 1 / mod P /
So last element of A has residue same as
first element of A ( mod P ).
So if we look at B^K ( for K = P, P+1, P+2 and so on ) we will see
that these numbers have same residues ( mod P ) as
B ^ ( K ( P1) ).
So, if we are only interested in calculations modulo P, we don't
need to bother about the elements belonging to S \ A.
All we need to know is the sequence A and its residues modulo P.
This is ( just to state it once again ), because:
B ^ ( K ( P1) ) = B ^ K / mod P /
( K >= P, Pprime, B<P )
Then all the residues the elements of the
sequence S = { B^K  k = 0,1,2,... } could possibly
have modulo P, are amongts the residues of A modulo P.
So if we generate these P residues ( the residues of sequence A )
we can find the least K ( if any ) for which we have
B ^ K = N ( mod P ).
If none of the elements of A has a residue N ( mod P ) then
there's no solution ( we should print "no solution" in terms
of problem 10225 ).
This is actually the naive ( most obvous ) algotihm, which
comes to my mind for this problem.
It works fine. The only problem is that it will be too slow,
taking into account the limits, which we have for P.
P could be as large as approximately 2^31  1.
And that is too much for this algorithm.
allows me to understand, the hints they give about Fermat's
theorem are related to the following.
1) B < P means GCD ( B, P ) = 1
2) Let's have a look at the sequence
S = { B^K  k=0,1,2,3... }
and in more detail let's look at its first P elements:
which form the sequence:
A = { 1, B, B^2... , B^(P1) }.
Sequence A has P members.
We know ( from Fermat's theorem ):
B^(P1) = 1 / mod P /
So last element of A has residue same as
first element of A ( mod P ).
So if we look at B^K ( for K = P, P+1, P+2 and so on ) we will see
that these numbers have same residues ( mod P ) as
B ^ ( K ( P1) ).
So, if we are only interested in calculations modulo P, we don't
need to bother about the elements belonging to S \ A.
All we need to know is the sequence A and its residues modulo P.
This is ( just to state it once again ), because:
B ^ ( K ( P1) ) = B ^ K / mod P /
( K >= P, Pprime, B<P )
Then all the residues the elements of the
sequence S = { B^K  k = 0,1,2,... } could possibly
have modulo P, are amongts the residues of A modulo P.
So if we generate these P residues ( the residues of sequence A )
we can find the least K ( if any ) for which we have
B ^ K = N ( mod P ).
If none of the elements of A has a residue N ( mod P ) then
there's no solution ( we should print "no solution" in terms
of problem 10225 ).
This is actually the naive ( most obvous ) algotihm, which
comes to my mind for this problem.
It works fine. The only problem is that it will be too slow,
taking into account the limits, which we have for P.
P could be as large as approximately 2^31  1.
And that is too much for this algorithm.
I also use Shanks's algorithm now.
Though I have a significant problem. In this algorithm we
must be able to effectively calculate the inverse of A^S modulo P.
That number is:
( A ^ (P1S) ) mod P
Here P>=2 is prime and A < P.
So, once again, we must be able to effectively calculate the inverse of
A ^ S , modulo P. Which is ( A ^ (P1S) ).
How do you deal with that ?
The inverse is crearly : ( A ^ (P1S) ) % P but as P could be
very large we can not just do :
When we have P = approximately = 2 000 000
the execution of the above cycle just takes too much time.
Though I have a significant problem. In this algorithm we
must be able to effectively calculate the inverse of A^S modulo P.
That number is:
( A ^ (P1S) ) mod P
Here P>=2 is prime and A < P.
So, once again, we must be able to effectively calculate the inverse of
A ^ S , modulo P. Which is ( A ^ (P1S) ).
How do you deal with that ?
The inverse is crearly : ( A ^ (P1S) ) % P but as P could be
very large we can not just do :
Code: Select all
Q=1;
for (int i=1; i<=(P1S); i++)
{
Q = Q * A;
Q = Q % P;
}
// at that moment here > Q is the inverse of A ^ S
// Q == ( A ^ (P1S) ) % P here !!!
the execution of the above cycle just takes too much time.