Page 1 of 1

Posted: Mon Feb 18, 2002 4:59 pm
by Even
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>

Posted: Tue Feb 19, 2002 4:44 pm
by Even
OK.. I got AC...

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

Posted: Thu Mar 21, 2002 12:32 pm
by Rossi
OK, I don't even know the name SHANK . can anyone say me what is it.

Posted: Thu Mar 21, 2002 12:37 pm
by Stefan Pochmann
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>

Posted: Tue Jan 04, 2005 8:13 am
by Experimenter
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?

Posted: Mon Feb 21, 2005 2:50 pm
by Sedefcho
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 ?

Posted: Mon Feb 21, 2005 2:59 pm
by Sedefcho
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.

Posted: Tue Feb 22, 2005 1:39 am
by Sedefcho
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

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.

Posted: Tue Feb 22, 2005 2:52 pm
by Sedefcho
Don't bother answering me.

I've found the effective way of computing what I asked for
in my previous post. Everything is OK now.