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

```
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.

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.