4
$\begingroup$

I have my Network Security finals. In elgamal cryptosystem, I am often encountering these equations like this

3 = (10^XA) mod 19

now everywhere I am finding only method to solve it, where I start at 0 and keep changing value for XA until the equation satisfies.

Is there any better method to solve using pen and paper + calculator?

Improve this question
$\endgroup$
2
  • $\begingroup$ Start to construct a table? otherwise you look for breaking dlog, that took sqrt time and hard to do with paper and pencil. $\endgroup$
    – kelalaka
    May 5 at 11:13
  • $\begingroup$ What is the maximum value of $p$ you are expecting? $\endgroup$
    – madhurkant
    May 5 at 13:12

2 Answers 2

Reset to default
3
$\begingroup$

You could try Baby-Step Giant-Step:

  1. First calculate $10^b$ for $b=0\dots 4$: $1, 10, 10\cdot 10 = 5, 10\cdot 5 = 12, 10\cdot 12 = 6$, and
  2. store them in a table manner ($\alpha_i = 10^i \bmod 19$).
  3. Then invert your target value $3^{-1} = 13$ and multiply $10^4 = 6$ until you get one of the values $10^b$ calculated in the first step: $13, 6\cdot 13 = 2, 6\cdot 2 = 12$, and
  4. use that $10^3 = 3^{-1}\cdot 10^{2\cdot 4}$ implies $3 = 10^{8-3} = 10^5$.

For the first step you have to calculate about $\sqrt{19}$ multiplications (I stopped at $b=4$ to show you the full algorithm), then you need an inversion (on wikipedia they invert 6 instead, so invert what's easier for you), and finally you need again at most $\sqrt{19}$ multiplications.

Improve this answer
$\endgroup$
5
  • $\begingroup$ How can the inversion can be done easily? The fastest for a computer doesn't mean that is suitable for paper and pencil. I would rather go for the list of small sizes like 19. $\endgroup$
    – kelalaka
    May 7 at 9:31
  • $\begingroup$ @kelalaka: Trial and error. I saw that $18=19-1$ is a multiple of $3$, so $3*6 = -1$ implies $3^{-1} = -6 = 13$. For small numbers you can try to "guess" the inverse, which is surely not optimal. Worst case you can find the inverse by calculating all multiples of $3$ by always adding $3$ modulo $19$ until you hit $1$ (or $-1$). 18 modular additions are much less work than 18 modular multiplications for the worst case. Also using extended Euclid doesn't take long, especially if you additionally don't mind using smaller negative numbers in between. $\endgroup$
    – j.p.
    May 7 at 20:47
  • $\begingroup$ Finding the inverses requires ExtGCD calculation only for half of the elements, takes a long time on paper, requires division and it is easy to make mistakes. Also, one needs to get used to the BsGs algorithm. I would go with the direct approach since it is simple. $\endgroup$
    – kelalaka
    May 8 at 7:34
  • $\begingroup$ @kelalaka: For two digit decimal numbers you should be able to find the modular inverse even without paper and pen: Take for example the worst case $55^{-1}$ modulo $89$ (Fibonacci numbers require the most steps): $55$ equals $-34$, and $3*34 = 102$ is $13$ modulo $89$, so $-3\cdot 55 = 13$ modulo $89$. Now $13\cdot 7 = 91$ modulo $89$, so $-21\cdot 55 = 2$, which implies ($2\cdot 44 = -1$ modulo $89$) that the inverse of $55$ modulo $89$ equals $21\cdot 44 = 924 = 34$. For me personally that's less work than some modular multiplications modulo $89$. $\endgroup$
    – j.p.
    May 8 at 21:49
  • $\begingroup$ I appreciate your cleverness, however, this is not about cleverness. When I consider pen and pencil work, I think it is simple to follow and easy to write, let me correct if it not the case. Also, you should include the how to find the inverse $\endgroup$
    – kelalaka
    May 9 at 13:54
0
$\begingroup$

Use brute force plus common sense. It is likely that the question has been specially chosen for this.

With this modulus, multiplying an even number by 10 halves it. Multiplying an odd number by 10 halves it (rounding down) and adds 10.

Given this, you can do it on your fingers with no pencil or paper.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You mean $$2k ( 19 - 9) \equiv -18k \equiv k \pmod{19}$$ and $$(2k+1) \cdot ( 19-9) \equiv k + 10 \pmod{19}$$. Keep in mind that, this is only specific to $19$, not a general case. $\endgroup$
    – kelalaka
    May 9 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.