1
$\begingroup$

my e=131 and p=18181

to find by d I must solve the linear diophantine equation 131*d=1 mod 18180 LDE to solve: 131d+18180y=1

after solving this I get d=-1249 and y=9 the problem is if I take my cipher text C which is say 9805 and try to decipher it with d=-1249 i get a massive error because d has to be positive to use it for deciphering. How can I find a d or make this d positive so I can use it for deciphering?

I think I got the answer, I need to write my solution for d,y in the form which gives all solutions and plug in a number and find a positive d that works

  • 1
    Dear Raynos, we do not delete questions which have answers (and much less upvoted anbd accepted answers!) unless there is a *very* good reason.2012-02-27

2 Answers 2

1

Let $(x_0,y_0)$ be a particular solution of the linear Diophantine equation $131x+ 18180y=1.$ Then all integer solutions are given by $x=x_0+18180t,\qquad y=y_0-131t,$ where $t$ ranges over the integers.

In your problem, the variable I called $x$ is called $d$. You want the "multiplier" of $d$ to be positive. Take, for example, $t=1$.

Remark: In general, suppose that you have found a solution in $(x_0,y_0)$ in integers, not necessarily positive, of the equation $ax+by=k$. Let $d$ be the greatest common divisor of $a$ and $b$, and let a=da', b=db'. Then all integer solutions of $ax+by=k$ are given by x=x_0+b't, y=y_0-a't, where $t$ ranges over the integers. Thus if you have found one solution, all the solutions are fairly straightforward to describe.

1

Remember that you are not solving an equation but a congruence, so when you write the answer $d=-1249$ what you really meant to write was $d\equiv -1249\pmod{18180}$. Do you know how to get a positive $d$ satisfying that congruence?

  • 1
    yes for this case an easy solution is to do 18180-1249 to get my d2012-02-27