10225 - Discrete Logging

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even » Mon Feb 18, 2002 4:59 pm

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

Post by Even » Tue Feb 19, 2002 4:44 pm

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
Location: Bangladesh

Post by Rossi » Thu Mar 21, 2002 12:32 pm

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:

Post by Stefan Pochmann » Thu Mar 21, 2002 12:37 pm

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

Post by Experimenter » Tue Jan 04, 2005 8:13 am

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.

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

Post by Sedefcho » Mon Feb 21, 2005 2:50 pm

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 ?

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

Post by Sedefcho » Mon Feb 21, 2005 2:59 pm

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.

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

Post by Sedefcho » Tue Feb 22, 2005 1:39 am

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.

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

Post by Sedefcho » Tue Feb 22, 2005 2:52 pm

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.

Post Reply

Return to “Volume 102 (10200-10299)”