mdw@git.distorted.org.uk Git - catacomb/blob - utils/curve25519.pock

   1 ;;; -*-conf-windows-*-
   2 ;;;
   3 ;;; Primality proofs for Curve25519.
   4
   5 sievebits 32
   6
   7 small 127 = 127
   8 small 2281 = 2281
   9 small 3911 = 3911
  10 small 4153 = 4153
  11 small 8053 = 8053
  12 small 28859 = 28859
  13 small 430751 = 430751
  14 small 531581 = 531581
  15 small 1224481 = 1224481
  16 small 8574133 = 8574133
  17 small 2773320623 = 2773320623
  18
  19 ;;;--------------------------------------------------------------------------
  20 ;;; Check the coordinate field order, 2^255 - 19, using Pocklington.
  21
  22 pock $p.0 = 2, 13, [2773320623]
  23 pock $p.1 = 2, 881391, [127, 8574133]
  24 pock $p.2 = 2, 272545200, [$p.0, $p.1]
  25 pock $p.3 = 2, 8876292, [4153, 430751]
  26 pock $p.4 = 2, 15454641059763671901, [$p.2, $p.3]
  27 pock 2p255m19 = 2, 390882, [$p.4]
  28 check 2p255m19, 255, 57896044618658097711785492504343953926634992332820282019728792003956564819949
  29
  30 ;;;--------------------------------------------------------------------------
  31 ;;; Check the large prime dividing the primary curve order.
  32 ;;;
  33 ;;; If this is l, then the curve order is 8 l.
  34
  35 pock $l.0 = 2, 966, [531581, 1224481]
  36 pock $l.1 = 2, 1763, [$l.0]
  37 pock $l.2 = 2, 19401055, [$l.1]
  38 pock $l.3 = 2, 57415875541459, [$l.2]
  39 pock $l.4 = 2, 7, [$l.3]
  40 pock l25519 = 2, 13081953933241429764863578700404002, [$l.4]
  41 check l25519, 253, 7237005577332262213973186563042994240857116359379907606001950938285454250989
  42
  43 ;;;--------------------------------------------------------------------------
  44 ;;; Check the large prime dividing the quadratic twist curve order.
  45 ;;;
  46 ;;; If this is l', then the twist's order is 4 l'.
  47
  48 pock $ll.0 = 2, 39277, [2281, 28859]
  49 pock $ll.1 = 2, 2181507, [$ll.0]
  50 pock $ll.2 = 2, 16086, [3911, 8053]
  51 pock $ll.3 = 2, 4458627402, [$ll.1, $ll.2]
  52 pock $ll.4 =  2, 256850, [$ll.3]
  53 pock $ll.5 = 2, 130890, [$ll.4]
  54 pock ll25519 = 2, 263995577955218862480758, [$ll.5]
  55 check ll25519, 253, 14474011154664524427946373126085988481603263447650325797860494125407373907997
  56
  57 ;;;--------------------------------------------------------------------------
  58 ;;; Prove primality of the coordinate field again, using ECPP.
  59 ;;;
  60 ;;; Two proofs, for the primary curve and its twist.
  61
  62 ecpp 2p255m19.1 = 57896044618658097711785492504343953926634992332820282019728792003956564819949, -102314837768112, 398341948620716521344, 5840268, 8547346653146300712246123037639701684230346772043151331330916737595562181421, [l25519]
  63 check 2p255m19.1, 255, 57896044618658097711785492504343953926634992332820282019728792003956564819949
  64
  65 ecpp 2p255m19.2 = 57896044618658097711785492504343953926634992332820282019728792003956564819949, -6548149617159168, -203951077693806858928128, 8, 27383066511106528251246245619606060380838675100485973882307388960169781073998, [ll25519]
  66 check 2p255m19.2, 255, 57896044618658097711785492504343953926634992332820282019728792003956564819949
  67
  68 ;;;----- That's all, folks --------------------------------------------------