## 10225 - Discrete Logging

Moderator: Board moderators

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
I use Shank's Algorithm...

Though I got the right sample output...

But I still WA...

Please tell me where should I notice...or give me some sample input...THANK YOU~~~

<font size=-1>[ This Message was edited by: Even on 2002-02-18 16:03 ]</font>

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
OK.. I got AC...

the output should be minimun... that's all...

Rossi
New poster
Posts: 20
Joined: Thu Mar 21, 2002 2:00 am
OK, I don't even know the name SHANK . can anyone say me what is it.

Stefan Pochmann
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 2002-03-21 11:42 ]</font>

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
but for Shank's algorithm p doesn't have to be prime, right? what is the point then of p and all those hints about Ferma's theorem?
it would be great if you replied this post. really.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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 ?

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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^(P-1) }.

Sequence A has P members.
We know ( from Fermat's theorem ):
B^(P-1) = 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- ( P-1) ).

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- ( P-1) ) = B ^ K / mod P /
( K >= P, P-prime, 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.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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 ^ (P-1-S) ) 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 ^ (P-1-S) ).

How do you deal with that ?

The inverse is crearly : ( A ^ (P-1-S) ) % P but as P could be
very large we can not just do :

Code: Select all

``````Q=1;
for (int i=1; i<=(P-1-S); i++)
{
Q = Q * A;
Q = Q  %  P;
}
// at that moment here -> Q is the inverse of A ^ S
// Q == ( A ^ (P-1-S) ) % P here !!!

``````
When we have P = approximately = 2 000 000
the execution of the above cycle just takes too much time.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria