Ask Your Question
1

Solving an equation with modulo

asked 2016-09-29 05:54:22 -0600

Alice gravatar image

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 flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2016-09-29 09:43:04 -0600

tmonteil gravatar image

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.

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2016-09-29 05:54:22 -0600

Seen: 43 times

Last updated: Sep 29 '16