Ask Your Question

# Solving an equation with modulo

I am trying to solve for k where p to the power of k is congruent to 1 modulo l. I have the following code:

p = 2^255-19;

l = 57896044618658097711785492504343953926634992332820282019728792003956564819949;

var('k')

sorted(solve_mod(p^k == 1, l))

but I get this really long error message when I try to run it. How do I solve this equation without getting errors?

I was trying to find the embedding degree for this elliptic curve:

sage: E = EllipticCurve(GF(p),[0,486662,0,1,0])

edit retag close merge delete

## 1 Answer

Sort by » oldest newest most voted

In your particular case, your equation is a bit weird since:

sage: p == l
True


In particular, $p = 0 \mbox{ mod } l$, so there is no hope to find any nonzero $k$ such that $p^k=1 \mbox{ mod } l$.

In the more general case, the problem you are trying to solve is called the discrete logarithm. If you had some other numbers, you could have done the following:

sage: a = Mod(1,l)
sage: b = Mod(p,l)
sage: discrete_log(a,b)


As explained before, in this particular example where $p=l$ you get ValueError: No discrete log of 1 found to base 0, which seems normal.

more

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2016-09-29 12:54:22 +0200

Seen: 1,378 times

Last updated: Sep 29 '16