Discrete Logarithm Algorithm

[Jan Medina]

Hi everybody.

I want to know what algorithm are implemented for calculate log() and discrete log(). and what are the differences?

[John Cremona]

log() is a function you would apply to numbers, say real or complex:

sage: a = RealField(100)(2)
sage: a.log()
0.69314718055994530941723212146

while discrete_log() is something to do in a finite cyclic group. For example:

sage: F = FiniteField(101)
sage: a = F(2)
sage: b = a^67
sage: discrete_log(b,a)
67

John

> --
> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.

[Jan Medina]

But the log() function works on a finite field too. So its not correct if a i use the log on finite fields?

I wan to calculate log(\theta+i,\theta) for i in a finte field and theta a primtive element

You received this message because you are subscribed to a topic in the Google Groups "sage-support" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-support/mbx4_5AN208/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sage-support...@googlegroups.com.

[John Cremona]

On 4 May 2014 13:20, Jan Medina <janme...@gmail.com> wrote:
> But the log() function works on a finite field too. So its not correct if a
> i use the log on finite fields?

OK -- you did not explain at all what is was that you were doing, na d
I could not guess!

>
> I wan to calculate log(\theta+i,\theta) for i in a finte field and theta a
> primtive element
>

You can see the documentation of this function like this:

sage: F=GF(101)
sage: a=F(3)

sage: a.log?

and even the code using a.log??, which reveals that in prime fields it
calls the pari library while in the general case it uses the
discrete_log function which is a completely generic implementation
(using either baby-step-giant-step or rho), hence fine for
small-medium fields but no good for large ones.

e.g.

sage: F=GF(101^3,'a')
sage: theta = F.primitive_element()
sage: [log(theta+i,theta) for i in range(10)]
[1, 596770, 963004, 681797, 310936, 434845, 968831, 682947, 790282, 125599]

John

[Simon King]

Hi Jan, hi John,

On 2014-05-04, John Cremona <john.c...@gmail.com> wrote:
> On 4 May 2014 13:20, Jan Medina <janme...@gmail.com> wrote:
>> I wan to calculate log(\theta+i,\theta) for i in a finte field and theta a
>> primtive element
>>
>
> You can see the documentation of this function like this:
>
> sage: F=GF(101)
> sage: a=F(3)
>
> sage: a.log?
>
> and even the code using a.log??

I somehow have the impression that part of the problem is that John
thinks in terms of methods ( a.log() ), while Jan is thinking in terms
of functions ( log(a) ).

Anyway, the documentation of the *function* "log" can be seen with
sage: log?
and the source code with
sage: log??

And it seems to be the case that ultimately the function call log(a)
will end up with the method call a.log(). So, answering Jan's question:
Yes, if alpha is is an element of a finite field with primitive element
theta, then log(alpha,theta) is essentially the same as directly calling
alpha.log(theta), and this the discrete logarithm.

Best regards,
Simon

[Jan Medina]

Hi John, hi Simon.

For example i want to construct the Bose.Chowla sequence with parameters p=839 y h=17, my question is what way its better to construct this sequence?.

I want to know this because i'm researching on the Chor Rivest system. Thus I need a good algorithm to solve the DLP.

[John Cremona]

On 4 May 2014 16:02, Jan Medina <janme...@gmail.com> wrote:
> Hi John, hi Simon.
>
> For example i want to construct the Bose.Chowla sequence with parameters
> p=839 y h=17, my question is what way its better to construct this
> sequence?.
>

I have no idea, sorry.

> I want to know this because i'm researching on the Chor Rivest system. Thus
> I need a good algorithm to solve the DLP.

You are very welcome to implement better algorithms than Sage has
already and contribute them!

John

> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an

[Jan Medina]

Hi John

John the discrete_log is the bsgs?  in SAGE is not implemeted the Pohlig Helman algorithm?

[John Cremona]

On 4 May 2014 18:53, Jan Medina <janme...@gmail.com> wrote:
> Hi John
>
> John the discrete_log is the bsgs? in SAGE is not implemeted the Pohlig
> Helman algorithm?

One of the great things about Sage is that you have access to the
source code, so you can answer such questions yourself:

sage: search_src("Pohlig")
groups/generic.py:693: ALGORITHM: Pohlig-Hellman and Baby step giant step.

A long time ago (2008?) I implemented the bsgs, but since then there
have been improvements. One of these was that someone added
Pohlig-Helman. You can see exactly what is done in the file
src/sage/groups/generic.py

John