121:
25:
66:
258:
The next section presents a table of all the time-costs of some of the possible operations in elliptic curves. The columns of the table are labelled by various computational operations. The rows of the table are for different models of elliptic curves. These are the operations considered:
313:
This means that 100 multiplications (M) are required to invert (I) an element; one multiplication is required to compute the square (S) of an element; no multiplication is needed to multiply an element by a parameter (Ă—param), by a constant (Ă—const), or to add two elements.
1574:
1597:) adding two points. So, this is one of the reasons why addition and doubling formulas are defined. Furthermore, this method is applicable to any group and if the group law is written multiplicatively; the double-and-add algorithm is then called
1017:
138:
38:
1163:
1158:
1105:
250:
under this addition operation. This article describes the computational costs for this group addition and certain related operations that are used in elliptic curve cryptography algorithms.
44:
581:
440:
84:
289:. The importance of doubling to speed scalar multiplication is discussed after the table. For information about other possible operations on elliptic curves see
185:
157:
164:
171:
153:
1660:
1650:
872:
887:
222:
204:
102:
52:
1665:
178:
142:
1569:{\displaystyle {\begin{aligned}&(....(((((P+P)+P)+P)+\dots )\dots +P)+P\\&\qquad =P+P+\dots +P+P\end{aligned}}.}
868:
235:
1051:
1598:
1023:
1670:
131:
1655:
557:
698:
675:
652:
301:
Under different assumptions on the multiplication, addition, inversion for the elements in some fixed
302:
247:
840:
793:
769:
745:
721:
628:
604:
534:
511:
487:
395:
372:
349:
286:
243:
285:
To see how adding (ADD) and doubling (DBL) points on elliptic curves are defined, see
1644:
817:
464:
317:
For more information about other results obtained with different assumptions, see
120:
1635:
318:
305:, the time-cost of these operations varies. In this table it is assumed that:
290:
239:
273:
mDBL – Mixed doubling: doubling of an input that has been scaled to have
267:
mADD – Mixed addition: addition of an input that has been scaled to have
1619:
1012:{\displaystyle P,\quad P=P+P,\quad P=P+P,\quad \dots ,\quad P=P+P}
114:
59:
18:
875:) it is necessary to consider the scalar multiplication
242:
encryption that is based on the mathematical theory of
80:
246:. Points on an elliptic curve can be added and form a
1161:
1054:
890:
1585:
steps, and each step consists of a doubling and (if
309:
I = 100M, S = 1M, Ă—param = 0M, add = 0M, Ă—const = 0M
1620:"Double-and-Add with Relative Jacobian Coordinates"
145:. Unsourced material may be challenged and removed.
75:
may be too technical for most readers to understand
1568:
1099:
1011:
881:. One way to do this is to compute successively:
154:"Table of costs of operations in elliptic curves"
16:Overview of method used to digitally encrypt data
871:and the elliptic curve method of factorization (
1100:{\displaystyle k=\sum _{i\leq \ell }k_{i}2^{i}}
8:
1636:http://hyperelliptic.org/EFD/g1p/index.html
319:http://hyperelliptic.org/EFD/g1p/index.html
291:http://hyperelliptic.org/EFD/g1p/index.html
53:Learn how and when to remove these messages
1547:
1522:
1488:
1466:
1444:
1414:
1389:
1340:
1303:
1266:
1162:
1160:
1091:
1081:
1065:
1053:
889:
582:Doubling-oriented Doche–Icart–Kohel curve
441:Tripling-oriented Doche–Icart–Kohel curve
223:Learn how and when to remove this message
205:Learn how and when to remove this message
103:Learn how and when to remove this message
87:, without removing the technical details.
322:
1610:
396:Short Weierstrass projective with a4=-3
373:Short Weierstrass projective with a4=-1
281:DBL+ADD – Combined double-and-add step
746:Jacobi quartic doubling-oriented XXYZZ
85:make it understandable to non-experts
7:
1578:This simple algorithm takes at most
535:Jacobi quartic doubling-oriented XYZ
418:Short Weierstrass Relative Jacobian
143:adding citations to reliable sources
14:
34:This article has multiple issues.
558:Twisted Hessian curve projective
254:Abbreviations for the operations
119:
64:
23:
1433:
969:
962:
925:
897:
130:needs additional citations for
42:or discuss these issues on the
1553:
1540:
1531:
1515:
1500:
1479:
1467:
1459:
1450:
1437:
1420:
1407:
1401:
1395:
1382:
1373:
1364:
1358:
1353:
1341:
1333:
1327:
1321:
1316:
1304:
1296:
1290:
1284:
1279:
1267:
1259:
1250:
1244:
1241:
1238:
1232:
1229:
1226:
1220:
1217:
1214:
1208:
1205:
1202:
1196:
1193:
1178:
1175:
1169:
997:
985:
976:
970:
947:
941:
932:
926:
904:
898:
605:Jacobi intersection projective
1:
1599:square-and-multiply algorithm
839:
816:
792:
768:
744:
720:
697:
674:
651:
629:Jacobi intersection extended
627:
603:
580:
556:
533:
510:
486:
463:
439:
417:
394:
371:
350:Short Weierstrass projective
348:
326:Curve shape, representation
1661:Computational number theory
1651:Elliptic curve cryptography
869:elliptic curve cryptography
236:Elliptic curve cryptography
1687:
653:Twisted Edwards projective
1624:Cryptology ePrint Archive
1618:Fay, Björn (2014-12-20).
1040:. In general, to compute
1022:But it is faster to use
867:In some applications of
699:Twisted Edwards Extended
676:Twisted Edwards Inverted
488:Hessian curve projective
1570:
1101:
1013:
863:Importance of doubling
818:Edwards curve inverted
465:Hessian curve extended
1666:Cryptographic attacks
1571:
1102:
1024:double-and-add method
1014:
794:Jacobi quartic XXYZZR
238:is a popular form of
1159:
1052:
888:
770:Jacobi quartic XXYZZ
139:improve this article
1566:
1561:
1097:
1076:
1009:
722:Edwards projective
512:Jacobi quartic XYZ
1061:
860:
859:
233:
232:
225:
215:
214:
207:
189:
113:
112:
105:
57:
1678:
1628:
1627:
1615:
1596:
1584:
1575:
1573:
1572:
1567:
1562:
1552:
1551:
1527:
1526:
1499:
1498:
1483:
1482:
1449:
1448:
1429:
1419:
1418:
1394:
1393:
1357:
1356:
1320:
1319:
1283:
1282:
1165:
1152:
1140:
1139:
1129:
1120:
1106:
1104:
1103:
1098:
1096:
1095:
1086:
1085:
1075:
1045:
1039:
1018:
1016:
1015:
1010:
880:
841:Montgomery curve
323:
228:
221:
210:
203:
199:
196:
190:
188:
147:
123:
115:
108:
101:
97:
94:
88:
68:
67:
60:
49:
27:
26:
19:
1686:
1685:
1681:
1680:
1679:
1677:
1676:
1675:
1671:Elliptic curves
1641:
1640:
1632:
1631:
1617:
1616:
1612:
1607:
1594:
1586:
1579:
1560:
1559:
1543:
1518:
1484:
1462:
1440:
1427:
1426:
1410:
1385:
1336:
1299:
1262:
1157:
1156:
1150:
1142:
1137:
1133:
1127:
1122:
1118:
1110:
1087:
1077:
1050:
1049:
1041:
1027:
1026:; for example,
886:
885:
876:
865:
299:
283:
280:
279:TPL – Tripling.
278:
272:
266:
264:
256:
244:elliptic curves
229:
218:
217:
216:
211:
200:
194:
191:
148:
146:
136:
124:
109:
98:
92:
89:
81:help improve it
78:
69:
65:
28:
24:
17:
12:
11:
5:
1684:
1682:
1674:
1673:
1668:
1663:
1658:
1653:
1643:
1642:
1639:
1638:
1630:
1629:
1609:
1608:
1606:
1603:
1590:
1565:
1558:
1555:
1550:
1546:
1542:
1539:
1536:
1533:
1530:
1525:
1521:
1517:
1514:
1511:
1508:
1505:
1502:
1497:
1494:
1491:
1487:
1481:
1478:
1475:
1472:
1469:
1465:
1461:
1458:
1455:
1452:
1447:
1443:
1439:
1436:
1432:
1430:
1428:
1425:
1422:
1417:
1413:
1409:
1406:
1403:
1400:
1397:
1392:
1388:
1384:
1381:
1378:
1375:
1372:
1369:
1366:
1363:
1360:
1355:
1352:
1349:
1346:
1343:
1339:
1335:
1332:
1329:
1326:
1323:
1318:
1315:
1312:
1309:
1306:
1302:
1298:
1295:
1292:
1289:
1286:
1281:
1278:
1275:
1272:
1269:
1265:
1261:
1258:
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1234:
1231:
1228:
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1204:
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1177:
1174:
1171:
1168:
1166:
1164:
1146:
1131:
1114:
1094:
1090:
1084:
1080:
1074:
1071:
1068:
1064:
1060:
1057:
1020:
1019:
1008:
1005:
1002:
999:
996:
993:
990:
987:
984:
981:
978:
975:
972:
968:
965:
961:
958:
955:
952:
949:
946:
943:
940:
937:
934:
931:
928:
924:
921:
918:
915:
912:
909:
906:
903:
900:
896:
893:
864:
861:
858:
857:
855:
853:
850:
848:
846:
843:
837:
836:
834:
832:
829:
826:
823:
820:
814:
813:
811:
808:
805:
802:
799:
796:
790:
789:
787:
784:
781:
778:
775:
772:
766:
765:
763:
760:
757:
754:
751:
748:
742:
741:
739:
736:
733:
730:
727:
724:
718:
717:
715:
713:
710:
707:
704:
701:
695:
694:
692:
690:
687:
684:
681:
678:
672:
671:
669:
667:
664:
661:
658:
655:
649:
648:
646:
643:
640:
637:
634:
631:
625:
624:
622:
619:
616:
613:
610:
607:
601:
600:
598:
596:
593:
590:
587:
584:
578:
577:
575:
572:
569:
566:
563:
560:
554:
553:
551:
549:
546:
543:
540:
537:
531:
530:
528:
526:
523:
520:
517:
514:
508:
507:
505:
502:
499:
496:
493:
490:
484:
483:
481:
479:
476:
473:
470:
467:
461:
460:
458:
455:
452:
449:
446:
443:
437:
436:
433:
431:
428:
425:
422:
419:
415:
414:
412:
410:
407:
404:
401:
398:
392:
391:
389:
387:
384:
381:
378:
375:
369:
368:
366:
364:
361:
358:
355:
352:
346:
345:
342:
339:
336:
333:
330:
327:
311:
310:
298:
295:
277:-coordinate 1.
271:-coordinate 1.
265:ADD – Addition
263:DBL – Doubling
261:
255:
252:
231:
230:
213:
212:
127:
125:
118:
111:
110:
72:
70:
63:
58:
32:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
1683:
1672:
1669:
1667:
1664:
1662:
1659:
1657:
1656:Finite fields
1654:
1652:
1649:
1648:
1646:
1637:
1634:
1633:
1625:
1621:
1614:
1611:
1604:
1602:
1600:
1593:
1589:
1583:
1576:
1563:
1556:
1548:
1544:
1537:
1534:
1528:
1523:
1519:
1512:
1509:
1506:
1503:
1495:
1492:
1489:
1485:
1476:
1473:
1470:
1463:
1456:
1453:
1445:
1441:
1434:
1431:
1423:
1415:
1411:
1404:
1398:
1390:
1386:
1379:
1376:
1370:
1367:
1361:
1350:
1347:
1344:
1337:
1330:
1324:
1313:
1310:
1307:
1300:
1293:
1287:
1276:
1273:
1270:
1263:
1256:
1253:
1247:
1235:
1223:
1211:
1199:
1190:
1187:
1184:
1181:
1172:
1167:
1154:
1149:
1145:
1136:
1125:
1119:∈ {0,1}
1117:
1113:
1107:
1092:
1088:
1082:
1078:
1072:
1069:
1066:
1062:
1058:
1055:
1047:
1044:
1038:
1034:
1030:
1025:
1006:
1003:
1000:
994:
991:
988:
982:
979:
973:
966:
963:
959:
956:
953:
950:
944:
938:
935:
929:
922:
919:
916:
913:
910:
907:
901:
894:
891:
884:
883:
882:
879:
874:
870:
862:
856:
854:
851:
849:
847:
844:
842:
838:
835:
833:
830:
827:
824:
821:
819:
815:
812:
809:
806:
803:
800:
797:
795:
791:
788:
785:
782:
779:
776:
773:
771:
767:
764:
761:
758:
755:
752:
749:
747:
743:
740:
737:
734:
731:
728:
725:
723:
719:
716:
714:
711:
708:
705:
702:
700:
696:
693:
691:
688:
685:
682:
679:
677:
673:
670:
668:
665:
662:
659:
656:
654:
650:
647:
644:
641:
638:
635:
632:
630:
626:
623:
620:
617:
614:
611:
608:
606:
602:
599:
597:
594:
591:
588:
585:
583:
579:
576:
573:
570:
567:
564:
561:
559:
555:
552:
550:
547:
544:
541:
538:
536:
532:
529:
527:
524:
521:
518:
515:
513:
509:
506:
503:
500:
497:
494:
491:
489:
485:
482:
480:
477:
474:
471:
468:
466:
462:
459:
456:
453:
450:
447:
444:
442:
438:
434:
432:
429:
426:
423:
420:
416:
413:
411:
408:
405:
402:
399:
397:
393:
390:
388:
385:
382:
379:
376:
374:
370:
367:
365:
362:
359:
356:
353:
351:
347:
343:
340:
337:
334:
331:
328:
325:
324:
321:
320:
315:
308:
307:
306:
304:
296:
294:
292:
288:
287:The group law
282:
276:
270:
260:
253:
251:
249:
245:
241:
237:
227:
224:
209:
206:
198:
187:
184:
180:
177:
173:
170:
166:
163:
159:
156: –
155:
151:
150:Find sources:
144:
140:
134:
133:
128:This article
126:
122:
117:
116:
107:
104:
96:
93:February 2010
86:
82:
76:
73:This article
71:
62:
61:
56:
54:
47:
46:
41:
40:
35:
30:
21:
20:
1623:
1613:
1591:
1587:
1581:
1577:
1155:
1147:
1143:
1134:
1123:
1115:
1111:
1108:
1048:
1042:
1036:
1032:
1028:
1021:
877:
866:
316:
312:
300:
284:
274:
268:
262:
257:
234:
219:
201:
192:
182:
175:
168:
161:
149:
137:Please help
132:verification
129:
99:
90:
74:
50:
43:
37:
36:Please help
33:
1645:Categories
1605:References
297:Tabulation
240:public key
165:newspapers
39:improve it
1595:≠ 0
1510:⋯
1493:−
1474:−
1377:⋯
1371:…
1348:−
1311:−
1274:−
1073:ℓ
1070:≤
1063:∑
992:−
964:…
45:talk page
1153:, then:
1046:, write
344:DBL+ADD
195:May 2014
1582:ℓ
1148:ℓ
1124:ℓ
179:scholar
79:Please
181:
174:
167:
160:
152:
1109:with
338:mDBL
335:mADD
303:field
248:group
186:JSTOR
172:books
1141:and
1121:and
1035:) +
430:(7)
427:(7)
341:TPL
332:ADD
329:DBL
158:news
1151:= 1
1130:log
1031:= (
873:ECM
825:10
810:15
801:10
786:14
777:11
762:14
753:11
738:13
729:11
683:10
663:10
660:11
645:16
639:11
636:12
621:14
615:12
612:14
592:12
589:17
574:14
568:12
565:12
545:11
542:13
522:11
519:13
504:14
498:10
495:12
475:11
472:12
457:12
451:11
448:17
435:18
424:11
421:10
406:11
403:14
400:10
383:11
380:14
377:11
360:11
357:14
354:11
141:by
83:to
1647::
1622:.
1601:.
1126:=
852:3
845:4
831:6
828:9
822:7
807:7
804:9
798:7
783:6
780:9
774:7
759:6
756:9
750:7
735:6
732:9
726:7
712:7
709:8
706:9
703:8
689:6
686:9
680:7
666:6
657:7
642:7
633:7
618:6
609:7
595:6
586:7
571:8
562:8
548:5
539:8
525:5
516:8
501:6
492:8
478:9
469:9
454:6
445:9
409:8
386:8
363:8
293:.
48:.
1626:.
1592:i
1588:k
1580:2
1564:.
1557:P
1554:]
1549:0
1545:k
1541:[
1538:+
1535:P
1532:]
1529:2
1524:1
1520:k
1516:[
1513:+
1507:+
1504:P
1501:]
1496:1
1490:l
1486:2
1480:)
1477:1
1471:l
1468:(
1464:k
1460:[
1457:+
1454:P
1451:]
1446:l
1442:2
1438:[
1435:=
1424:P
1421:]
1416:0
1412:k
1408:[
1405:+
1402:)
1399:P
1396:]
1391:1
1387:k
1383:[
1380:+
1374:)
1368:+
1365:)
1362:P
1359:]
1354:)
1351:3
1345:l
1342:(
1338:k
1334:[
1331:+
1328:)
1325:P
1322:]
1317:)
1314:2
1308:l
1305:(
1301:k
1297:[
1294:+
1291:)
1288:P
1285:]
1280:)
1277:1
1271:l
1268:(
1264:k
1260:[
1257:+
1254:P
1251:]
1248:2
1245:[
1242:(
1239:]
1236:2
1233:[
1230:(
1227:]
1224:2
1221:[
1218:(
1215:]
1212:2
1209:[
1206:(
1203:]
1200:2
1197:[
1194:(
1191:.
1188:.
1185:.
1182:.
1179:(
1176:]
1173:2
1170:[
1144:k
1138:⌋
1135:k
1132:2
1128:⌊
1116:i
1112:k
1093:i
1089:2
1083:i
1079:k
1067:i
1059:=
1056:k
1043:P
1037:P
1033:P
1029:P
1007:P
1004:+
1001:P
998:]
995:1
989:n
986:[
983:=
980:P
977:]
974:n
971:[
967:,
960:,
957:P
954:+
951:P
948:]
945:2
942:[
939:=
936:P
933:]
930:3
927:[
923:,
920:P
917:+
914:P
911:=
908:P
905:]
902:2
899:[
895:,
892:P
878:P
275:Z
269:Z
226:)
220:(
208:)
202:(
197:)
193:(
183:·
176:·
169:·
162:·
135:.
106:)
100:(
95:)
91:(
77:.
55:)
51:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
