Faster scalar multiplication over an elliptic curve by hand?

Question

For an elliptic curve $y^2=x^3+ax+b$, I have $a=1, b=1, G=(3,10)$ private key of User $B$ as $4$. To calculate his public key, I have the formula: $Pb=nb \times G = 4(3,10)$.

This makes my calculation$=4G= (3,10)+(3,10)+(3,10)+(3,10)$

I got $(7,10)$ for the first addition. Then, $(14,18)$. Final answer as $(9,3)$. Is this answer correct?

Also, I have to do this in an exam by hand. Calculating this is a bit lengthy. Is there a faster way to calculate $4G$? For example, to calculate $(5^{-1} \times 7)\pmod {23}$ in the first part of the calculation requires me to go from 1-22 to find 14 as its modular inverse and then use it as $(5 \times 14)\pmod{23}=6$? All of this takes time. Is there some way I can speed this up?

Answer 1

Calculating modular inverse certainly shouldn't be done by enumeration of possibilities. It's what you have Euclid's algorithm for.

As for general speed up; if you are computing $4P $ it's certainly more efficient to compute $2 (2P) $ than adding 4 times. This is true in general, you should be using a binary expansion of the scalar multiple and use double and add.

I'd assume using jacobite projective coordinates is probably not efficient nor is Montgomery multiplication for these sizes and when doing it by hand.

Edit The general method for doing efficient scalar multiplication on an elliptic curve in short weierstrass form (ignoring issues with inverses, projective coordinates and the like) is to perform what is usually called the double and add algorithm.

Suppose you want to compute $155$. If you try doing it by addition you end up having to perform $154$ additions. That is incredibly inefficient.

Instead what you want to do is realize that you can write $155$ as $10011011_2$ (in binary). This means $155=2^7+2^4+2^3+2^1+2^0$ so $$155P=(2^7+2^4+2^3+2^1+2^0)P=(1+2(1+2^2(1+2(1+2^3))))P=P+2(P+2^2(P+2(P+2^3P)))$$

Now to compute $155P$ you just compute $2P=Q_1$, $2Q_1=Q_2$, $2Q_2=Q_3$ now note $Q_3=2^3P$, next $P+Q_3=Q_4$, $2Q_4=Q_5$, $P+Q_5=Q_6$, $2Q_6=Q_7$, $2Q_7=Q_8$, $P+Q_8=Q_9$, $2Q_9=Q_{10}$, $P+Q_{10}=Q_{11}=155P$. Notice I only used $10$ operations as opposed to $154$.

Answer 2

If I am correct to assume that you are doing addition on $E:y^2=x^3+x+1$ over $\mathbb{F}_{23}$, then no, your calculation was not correctly done. If $G=(3,10)$, then $$2G=(7 , 12), \ 3G = (19, 5), \ 4G = (17 , 3).$$ I used Magma myself to do this:

F:=GF(23);

g:=Generator(F);

E:=EllipticCurve([0,0,0,g,g]);

G:=E![3, 10];

2*G; 3*G; 4*G;