```
#define RZ return z
#define B 34
#define F4j i j=5;for(;j--;)
#define FIX(j,r,k) q=z[j]>>r, z[j]-=q<
```b)-(a**>55*k&((k<2)*M-1))
#define MUL(m,E)\
zz[0]=m(0,0)E(1,4)E(2,3)E(3,2)E(4,1),\
zz[1]=m(0,1)m(1,0)E(2,4)E(3,3)E(4,2),\
zz[2]=m(0,2)m(1,1)m(2,0)E(3,4)E(4,3),\
zz[3]=m(0,3)m(1,2)m(2,1)m(3,0)E(4,4),\
zz[4]=m(0,4)m(1,3)m(2,2)m(3,1)m(4,0);\
z[0]=R(0,0)-R(4,1)*20-R(3,2)*20,\
z[1]=R(1,0)+R(0,1)-R(4,2)*20,\
z[2]=R(2,0)+R(1,1)+R(0,2),\
z[3]=R(3,0)+R(2,1)+R(1,2),\
z[4]=R(4,0)+R(3,1)+R(2,2);\
z[1]+=z[0]>>55; z[0]&=M-1;
typedef long long i;typedef i*f,F[5];typedef __int128 ii,FF[5];
i M=((i)1)<<55;F O={0},I={1};
f fix(f z){i j=0,q;
for(;j<5*2;j++) FIX(j%5,(j%5<4?55:53),(j%5<4?1:-5));
z[0]+=(q=z[0]<0)*5; z[4]+=q<<53; RZ;}
i cmp(f x,f y){i z=(fix(x),fix(y),0); F4j z+=!z*CMP(x[j],y[j]); RZ;}
f add(f z,f x,f y){F4j z[j]=x[j]+y[j]; RZ;}
f sub(f z,f x,f y){F4j z[j]=x[j]-y[j]; RZ;}
f mal(f z,i s,f y){F4j z[j]=y[j]*s; RZ;}
f mul(f z,f x,f y){FF zz; MUL(+XY,-20*XY); {F4j zz[j]=0;} RZ;}
f squ(f z,f x){mul(z,x,x); RZ;}
i inv(f z){F t;i j=272; for(mul(z,z,squ(t,z));j--;) squ(t,t);
return mul(z,t,z), (sub(t,t,t)), cmp(O,z);}
i leg(f y){F t;i j=270; for(squ(t,squ(y,y));j--;) squ(t,t);
return j=cmp(I,mul(y,y,t)), (sub(y,y,y),sub(t,t,t)), !j;}
**```
This pseudocode makes uses of some extra C-like pseudocode features:
- #define is used to create macros, which expand within the source
code (as in C pre-processing).
- type ii is 128-bit integer
- multiplying a type i by a type ii variable yields a type ii
variable. If both inputs can fit into a type i variable, then
the result has no overflow or reduction: it is exact as a product
of integers.
Brown 2y^2=x^3+x over 8^91+5 [Page 33]
Internet-Draft 2019-10-03
- type ff is array of five type ii values. It is used to represent
a field in a radix expansion, except the limbs (digits) can be
128-bits instead of 64-bits. The variable zz has type ff and is
used to intermediately store the product of two field element
variables x and y (of type f).
- function mod takes an ff variable and produce f variable
representing the same field element. A pseudocode example may be
defined further below.
TO DO: Add some notes (answer these questions):
- How small the limbs of the inputs to function mul and squ must be
to ensure no overflow occurs?
- How small are the limbs of the output of functions mul and squ?
TO DO: add notes answering these questions:
- How small must be the input limbs to avoid overflow?
- How small are the output limbs (to know how to safely use of
output in further calculations).
Note: The partial reduction technique used in the multiplication
pseudocode is sometimes known as lazy reduction. It aims to do
just enough calculation to avoid overflow errors, and thus it may be
regarded as attempt at optimization.
To be completed.
The input variable is x and the output variable is b. The declared
types and functions are as follows:
- type c: curve representative, length-34 array of non-negative
8-bit integers ("characters"),
- type f: field element, a length-5 array of 64-bit integers
(negatives allowed), representing a field element as an integer in
base 2^55,
- type i: 64-bit integers (e.g. entries of f),
- function mal: multiply a field element by a small integer (result
stored in 1st argument),
- function fix: fully reduce an integer modulo 8^91+5,
Brown 2y^2=x^3+x over 8^91+5 [Page 34]
Internet-Draft 2019-10-03
- function cmp: compare two field element (after fixing), returning
-1, 0 or 1.
Note: The two for-loops in the pseudocode are just radix
conversion, from base 2^55 to base 2^8. Because both bases are
powers of two, this amount to moving bits around. The entries of
array b are compute modulo 256. The second loop copies the bits
that the first loop misses (the bottom bits of each entry of f).
Note: Encoding is lossy, several different (x,y) may encode to the
same byte string b. Usually, if (x,y) generated as a part of
Diffie--Hellman key exchange, this lossiness has no effect.
Note: Encoding should not be confused with encryption. Encoding
is merely a conversion or representation process, whose inverse is
called decoding.
- the expression (i)b[j] means that 8-bit integer b[j] is converted
to a 64-bit integer (so is no longer treated modulo 256). (In C,
this is operation is called casting.)
Note: the decode function 'feed' only has 1 for-loop, which is the
approximate inverse of the first of the 2 for-loops in the encode
function 'bite'. The reason the 'bite' needs the 2nd for-loop is
due to the lossy conversion from integers to bytes, whereas in the
other direction the conversion is not lossy. The second loop
recovers the lost information.
C.1.2. Montgomery ladder scalar multiplication
The pseudocode below, the second part of the file pseudo.c,
implements Montgomery's well-known ladder algorithm for elliptic
curve scalar point multiplication, as it applies to the curve
2y^2=x^3+x.
Again, the pseudocode is a continuation of the pseudocode for field
arithmetic, and all previous definitions are assumed.
Brown 2y^2=x^3+x over 8^91+5 [Page 35]
Internet-Draft 2019-10-03
``````
#define X z[0]
#define Z z[1]
typedef void _;typedef volatile unsigned char *c,C[B];
typedef F*e,E[2];typedef E*v,V[2];
f feed(f x,c z){i j=((mal(x,0,x)),B);
for(;j--;) x[j/7]+=((i)z[j])<<((8*j)%55); return fix(x);}
c bite(c z,f x){F t;i j=((fix(mal(x,cmp(mal(t,-1,x),x),x))), B),k=5;
for(;j--;) z[j]=x[j/7]>>((8*j)%55); {(sub(t,t,t));}
for(;--k;) z[7*k-1]+=x[k]<<(8-k); {(sub(x,x,x));} RZ;}
i lift(e z,f x,i t){F y;return mal(X,1,x),mal(Z,1,I),t||
leg(mal(y,2,add(y,x,mul(y,x,squ(y,x)))));}
i drop(f x,e z){return
inv(Z)&&mul(x,X,Z)&&(sub(X,X,X)&&sub(Z,Z,Z));}
_ let(e z,e y){i j=2;for(;j--;)mal(z[j],1,y[j]);}
_ smv(v z,v y){i j=4;for(;j--;)add(((e)z)[j],((e)z)[j],((e)y)[j]);}
v mav(v z,i a){i j=4;for(;j--;)mal(((e)z)[j],a,((e)z)[j]);RZ;}
_ due(e z){F a,b,c,d;
mal(X,2,mul(X,squ(a,add(a,X,Z)),squ(b,sub(b,X,Z))));
mul(Z,add(c,a,b),sub(d,a,b));}
_ ade(e z,e u,f w){F a,b,c,d;f ad=a,bc=b;
mul(ad,add(a,u[0],u[1]),sub(d,X,Z)),
mul(bc,sub(b,u[0],u[1]),add(c,X,Z));
squ(X,add(X,ad,bc)),mul(Z,w,squ(Z,sub(Z,ad,bc)));}
_ duv(v a,e z){ade(a[1],a[0],z[0]);due(a[0]);}
v adv(v z,i b){V t;
let(t[0],z[1]),let(t[1],z[0]);smv(mav(z,!b),mav(t,b));mav(t,0);RZ;}
e mule(e z,c d){V a;E o={{1}};i
b=0,c,n=(let(a[0],o),let(a[1],z),8*B);
for(;n--;) c=1&d[n/8]>>n%8,duv(adv(a,c!=b),z),b=c;
let(z,*adv(a,b)); (due(*mav(a,0))); RZ;}
C G={23,1};
i mulch(c db,c d,c b){F x;E p; return
lift(p,feed(x,b),(db==d||b==G))&&drop(x,mule(p,d))&&bite(db,x);}
``````
The pseudocode function mulch -- which multiplies byte string
(character) representations of point b by the byte string
representation of integer d -- omits public key validation of the
input point b if the base of scalar multiplication is the chosen
fixed base, or if the input integer d and output point db have the
same location.
The reason for the latter omission of public key validation is the
integer d is overwritten presumably the caller of mulch intended to
use d only once, so that d is likely to be an ephemeral secret,
largely obviating the need to validate b.
Brown 2y^2=x^3+x over 8^91+5 [Page 36]
Internet-Draft 2019-10-03
In other words, the caller of mulch can control whether public key
validation is done by choosing the locations of db, b, b
appropriately. (An alternative would be for mulch to include a flag
to indicate whether b needs to be validated. Instead, the
pseudocode tries to make mulch do the sensible choice for
Diffie--Hellman if the caller forgets whether public key validation
is necessary.)
The pseudocode files tv.c, dhe.c and pkv.c, define in the sections
below, demonstrate the use of mulch, and its features regarding
public key validation.
In case, mulch returns a Boolean-valued integer indicating whether b
was valid. If validation was requested by the interface, and b is
invalid, then mulch return false (0), and the memory location db
should remain unaltered.
Note: the pseudocode makes types c and C volatile, with the aim
that the C compiler will preserve attempts to zeroize values of
this type. Such zeroization steps in the pseudocode do add
clutter to the code, but have usually been delimited by
parentheses or braces to indicate their implementation-specific
purpose.
C.1.3. Bernstein's 2-dimensional Montgomery ladder
Bernstein's 2-dimensional ladder is a variant of Montgomery's ladder
that computes aP+bQ, for any two points P and Q, more quickly than
computing aP and bQ separately.
Curve 2y^2=x^3+x has an efficient endomorphism, which allows a point
Q = [i+1]P to compute efficiently. Gallant, Lambert and Vanstone
introduced a method (now called the GLV method), to compute dP more
efficiently, given such an efficient endomorphism. They write d = a
+ eb where e is the integer multiplier corresponding to the
efficient endomorphism, and a and b are integers smaller than d.
(For example, 17 bytes each instead of 34 bytes.)
The GLV method can be combined with Bernstein's 2D ladder algorithm
to be applied to compute dP = (a+be)P = aP + beP = aP + bQ, where
e=i+1.
This algorithm is not implemented by any pseudocode in the version
the draft. (Previous versions had it.)
See [B1] for further explanation and example pseudocode.
Brown 2y^2=x^3+x over 8^91+5 [Page 37]
Internet-Draft 2019-10-03
I have estimate a ~10% speedup of this method compared to the plain
Montgomery ladder. However, the code is more complicated, and
potentially more vulnerable to implementation-based attacks.
C.1.4. GLV in Edwards coordinates (Hisil--Carter--Dawson--Wong)
To be completed.
It is also possible to convert to Edwards coordinates, and then use
the Hisil--Carter--Dawson--Wong (HCDW) elliptic curve arithmetic.
The HCDW arithmetic can be combined with the GLV techniques to
obtain a scalar multiplication potentially more efficient than
Bernstein's 2-dimensional Montgomery. The downside is that it may
require key-dependent array look-ups, which can be a security risk.
I have implemented this, finding ~20% speed-up over my
implementation of the Montgomery ladder. However, this speed-up may
disappear upon further optimization (e.g. assembly), or further
security hardening (safe table lookup code).
C.2 Pseudocode for test vectors
The following pseudocode, describing the contents of a file tv.c,
includes the previously defined file pseudo.c, and stdio.h, and then
generates some test vectors.
``````
#include
```
#include "pseudo.c"
#define M mulch
void hx(c x){i j=B;for(;j--;)printf("%02x",x[j]);printf("\n");}
int main (void){i j=1e5/2,wait=/*your mileage may vary*/7000;
C x="TEST 2y^2=x^3+x/GF(8^91+5)",y="yet another test",z;
M(z,x,G); hx(x),hx(G),hx(z);
fprintf(stderr,"%30s(wait=~%ds, ymmv)","",j/wait);
for(;j--;)if(fprintf(stderr,"\r%7d\r",j),!(M(z,x,z)&&M(x,z,G)))
j=0*printf("Mulch fail rate ~%f :(\n",(2*j)/1e5);//else//debug
hx(x),hx(z);
M(y,y,G);M(y,y,y);
for(M(z,G,G),j=900;j--;)M(z,x,z);for(j=900;j--;)M(z,y,z);hx(z);
for(M(z,G,G),j=900;j--;)M(z,y,z);for(j=900;j--;)M(z,x,z);hx(z);}
```
To be completed: Explain this properly, if possible.
The test vectors should output this:
Brown 2y^2=x^3+x over 8^91+5 [Page 38]
Internet-Draft 2019-10-03
000000000000000029352b31395e382846472f782b335e783d325e79322054534554
00000000000000000000000000000000000000000000000000000000000000000117
c8c0f2f404a9fabc91c939d8ea1b9e258d82e21a427b549f05c832cf8d48296ffad7
5f336f56f86de3d52b0eab85e527f2ac7b9d77605c0d5018f5faa4243fd462b1badd
fc023b3f03b469dca32446db80d9b388d753cc77aa4c3ee7e2bb86e99e7bed38f509
8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221
8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221
C.3. Pseudocode for a command-line demo of Diffie--Hellman
The following code, representing a file dhe.c, is a bilingual: being
valid C and bash script.
As a bash script, it will compile the C code as dhe, then run it
twice, once as Alice and once as Bob, piping the ephemeral public
keys, and writing the resulting Diffie--Hellman agreed secret keys
into pipes. The agreed secret keys are fed into SHA-256 to
demonstrate their equality, but also to show the typical way to use
DH agree keys (to hash them rather than use them directly).
This pseudocode assumes a Linux-like system.
``````
#include "pseudo.c" /* dhe.c (also a bash script)
: demos ephemeral DH, also creates, clobbers files dhba dha dhb
: -- Dan Brown, BlackBerry, '19 */
#include
```
_ get(c p,_*f){if(f)while(!fread((_*)p,B,1,f));}
_ put(c p,_*f){if(f)fwrite((_*)p,B,1,f),fflush(f); bite(p,O);}
int main (_){C s="/dev/urandom",p="EPHEMERAL s => OK if p INVALID";
get(s,fopen((_*)s,"r")), mulch(p,s,G), put(p,stdout);
get(p,stdin), mulch(s,s,p), put(s,stderr);} /*'
[ dhe.c -nt dhe ] && gcc -O3 dhe.c -o dhe && echo "$(/dev/null || ([ ! -p dhba ] && :> dhba)
./dhe dha | ./dhe >dhba 2>dhb &
sha256sum dha & sha256sum dhb # these should be equal
(for f in dh{a,b,ba} ; do [ -f $f ] && \rm -f $f; done)# '*/
```
C.4 Pseudocode for public-key validation and twist insecurity
The following pseudocode, describing a file pkv.c, demonstrates the
public-key validation features of mulch from pseudo.c, by
deliberately supplying invalid points to mulch. It also
demonstrates how to turn PKV on and off using the mulch interface.
Brown 2y^2=x^3+x over 8^91+5 [Page 39]
Internet-Draft 2019-10-03
It also demonstrates the need for PKV despite using the Montgomery
by finding points of low order on the twist of the curve, and
showing that such points can leak bits of the secret multiplier.
It further demonstrates the order of the curve, and complex
multiplication by i, and the fact the 34-byte representation of
points is unaffected by multiplication by i.
``````
#include
```
#include "pseudo.c"
#define M mulch // works with +/- x, so P ~ -P ~ iP ~ -iP
void hx(c x){i j=B;for(;j--;)printf("%02x",x[j]);printf("\n");}
int main (void){i j;// sanity check, PKV, twist insecurity demo
C y="TEST 2y^2=x^3+x/GF(8^91+5)",z="zzzzzzzzzzzzzzzzzzzz",
q = "\xa9\x38\x04\xb8\xa7\xb8\x32\xb9\x69\x85\x41\xe9\x2a"
"\xd1\xce\x4a\x7a\x1c\xc7\x71\x1c\xc7\x71\x1c\xc7\x71\x1c"
"\xc7\x71\x1c\xc7\x71\x1c\x07", // q=order(G)
i = "\x36\x5a\xa5\x56\xd6\x4f\xb9\xc4\xd7\x48\x74\x76\xa0"
"\xc4\xcb\x4e\xa5\x18\xaf\xf6\x8f\x74\x48\x4e\xce\x1e\x64"
"\x63\xfc\x0a\x26\x0c\x1b\x04", // i^2=-1 mod q
w5= "\xb4\x69\xf6\x72\x2a\xd0\x58\xc8\x40\xe5\xb6\x7a\xfc"
"\x3b\xc4\xca\xeb\x65\x66\x66\x66\x66\x66\x66\x66\x66\x66"
"\x66\x66\x66\x66\x66\x66\x66"; // w5=(2p+2-72q)/5
for(j=0;j<=3;j++)M(z,(C){j},G),hx(z); // {0,1,2,3}G, but reject 0G
M(z,q,G),hx(z); // reject qG; but qG=O, under hood:
{F x;E p;lift(p,feed(x,G),1);mule(p,q);hx(bite(z,p[1]));}
for(j=0;j<0*25;j++){F x;E p;lift(p,feed(x,(C){j,1}),1);mule(p,q);
printf("%3d ",j),hx(bite(z,p[1]));}// see j=23 for choice of G
for(j=3;j--;)q[0]-=1,M(z,q,G),hx(z);// (q-{1,2,3})G ~ {1,2,3}G
M(z,i,G),hx(z); i[0]+=1,M(z,i,G),M(z,i,z),hx(z);// iG~G,(i+1)^2G~2G
M(w5,w5,(C){5}),hx(w5);// twist, ord(w5)=5, M(z,z,p) skipped PKV(p)
M(G,(C){1},w5),hx(G);// reject w5 (G unch.); but w5 leaks z mod 5:
for(j=10;j--;)M(z,y,G),z[0]+=j,M(z,z,w5),hx(z);}
```
C.5. Elligator i
To be deleted (or completed).
This pseudocode would show how to implement to the Elligator i map
from byte strings to points. This is INCOMPATIBLE with pseudocode
above.
Pseudocode (to be verified):
Brown 2y^2=x^3+x over 8^91+5 [Page 40]
Internet-Draft 2019-10-03
``````
typedef f xy[2] ;
#define X p[0]
#define Y p[1]
lift(xy p, f r) {
f t ; i b ;
fix(r);
squ(t,r); // r^2
mul(t,I,t); // ir^2
sub(t,(f){1},t); // 1-ir^2
inv(t,t); // 1/(1-ir^2)
mal(t,3,t); // 3/(1-ir^2)
mul(t,I,t); // 3i/(1-ir^2)
sub(X,I,t); // i-3i/(1-ir^2)
b = get_y(t,X);
mal(t,1-b,I); // (1-b)i
add(X,X,t); // EITHER x OR x + i
get_y(Y,X);
mal(Y,2*b-1,Y); // (-1)^(1-b)""
fix(X); fix(Y);
}
drop(f r, xy p)
{
f t ; i b,h ;
fix(X); fix(Y);
get_y(t,X);
b=eq(t,Y);
mal(t,1-b,I);
sub(t,X,t); // EITHER x or x-i
sub(t,I,t); // i-x
inv(t,t); // 1/(i-x)
mal(t,3,t); // 3/(i-x)
add(t,I,t); // i+ 3/(i-x)
mal(t,-1,t); // -i-3/(i-x)) = (1-3i/(i-x))/i
b = root(r,t) ;
fix(r);
h = (r[4]<(1LL<<52)) ;
mal(r,2*h-1,r);
fix(r);
}
Brown 2y^2=x^3+x over 8^91+5 [Page 41]
Internet-Draft 2019-10-03
elligator(xy p,c b) {f r; feed(r,b); lift(p,r);}
crocodile(c b,xy p) {f r; drop(r,p); bite(b,r);}
``````
D. Primality proofs and certificates
Recent work of Albrecht and others [AMPS] has shown the combination
of adversarially chosen prime and improper probabilistic primality
tests can result in attacks.
The adversarial primes are generally result of an exhaustive search,
and therefore contain an amount of information corresponding to the
length of their search, putting a predictable lower bound on their
Kolmogorov complexity.
The two primes involved for 2y^2=x^3+x/GF(8^91+5) should perhaps
already resist [AMPS] because of compact representation of these
primes:
p = 8^91+5
q = #(2y^2=x^3+x/GF(8^91+5))/72
The [AMPS] can also be resisted by:
- properly implementing probabilistic primality test, or
- implementing provable primality tests.
Provable primality tests can be very slow, but can be separated into
two steps: a slow certificate generation, and a fast certificate
verification. The certificate is a set of data, representing an
intermediate step in the provable primality test, after which the
completion of the test is quite efficient.
Pratt primality certificate generation for any prime p, involves
factorizing p-1, which can be very slow, and then recursively
generating a Pratt primality certificate for each prime factor of
p-1. Essentially, each prime has a unique Pratt primality
certificate.
Pratt primality certificate verification of (p-1), involves search
for g such that 1 = (g^(p-1) mod p) and 1 < (g^((p-1)/q) mod p) for
each q dividing p-1, and then recursively verifying each Pratt
primality certificate for each prime factor q of p-1.
Brown 2y^2=x^3+x over 8^91+5 [Page 42]
Internet-Draft 2019-10-03
In this document, we specify a Pratt primality certificate as a
sequence of (candidate) primes each being 1 plus a product of
previous primes in the list, with certificate stating this product.
Although Pratt primality certificate verification is quite
efficient, an ECC implementation can opt to trust 8^91+5 by virtue
of verifying the certificate once, perhaps before deployment or
compile time.
D.1. Pratt certificate for the field size 8^91+5
Define 52 positive integers, a,b,c,...,z,A,...,Z as follows:
a=2 b=1+a c=1+aa d=1+ab e=1+ac f=1+aab g=1+aaaa h=1+abb i=1+ae
j=1+aaac k=1+abd l=1+aaf m=1+abf n=1+aacc o=1+abg p=1+al q=1+aaag
r=1+abcc s=1+abbbb t=1+aak u=1+abbbc v=1+ack w=1+aas x=1+aabbi
y=1+aco z=1+abu A=1+at B=1+aaaadh C=1+acu D=1+aaav E=1+aeff F=1+aA
G=1+aB H=1+aD I=1+acx J=1+aaacej K=1+abqr L=1+aabJ M=1+aaaaaabdt
N=1+abdpw O=1+aaaabmC P=1+aabeK Q=1+abcfgE R=1+abP S=1+aaaaaaabcM
T=1+aIO U=1+aaaaaduGS V=1+aaaabbnuHT W=1+abffLNQR X=1+afFW
Y=1+aaaaauX Z=1+aabzUVY.
Note: variable concatenation is used to indicate multiplication.
For example, f = 1+aab = 1+2*2*(1+2) = 13.
Note: One must verify that Z=8^91+5.
Note: The Pratt primality certificate involves finding a generator
g for each the prime (after the initial prime). It is possible to
list these in the certificate, which can speed up verification by
a small factor.
(2,b), (2,c), (3,d), (2,e), (2,f), (3,g), (2,h), (5,i), (6,j),
(3,k), (2,l), (3,m), (2,n), (5,o), (2,p), (3,q), (6,r), (2,s),
(2,t), (6,u), (7,v), (2,w), (2,x), (14,y),(3,z), (5,A), (3,B),
(7,C), (3,D), (7,E), (5,F), (2,G), (2,H), (2,I), (3,J), (2,K),
(2,L),(10,M), (5,N), (10,O),(2,P), (10,Q),(6,R), (7,S), (5,T),
(3,U), (5,V), (2,W), (2,X), (3,Y), (7,Z).
Brown 2y^2=x^3+x over 8^91+5 [Page 43]
Internet-Draft 2019-10-03
Note: The decimal values for a,b,c,...,Y are given by: a=2, b=3,
c=5, d=7, e=11, f=13, g=17, h=19, i=23, j=41, k=43, l=53, m=79,
n=101, o=103, p=107, q=137, r=151, s=163, t=173, u=271, v=431,
w=653, x=829, y=1031, z=1627, A=2063, B=2129, C=2711, D=3449,
E=3719, F=4127, G=4259, H=6899, I=8291, J=18041, K=124123,
L=216493, M=232513, N=2934583, O=10280113, P=16384237, Q=24656971,
R=98305423, S=446424961, T=170464833767, U=115417966565804897,
V=4635260015873357770993, W=1561512307516024940642967698779,
X=167553393621084508180871720014384259,
Y=1453023029482044854944519555964740294049.
D.2. Pratt certificate for subgroup order
Define 56 variables a,b,...,z,A,B,...,Z,!,@,#,$, with new
values:
a=2 b=1+a c=1+a2 d=1+ab e=1+ac f=1+a2b g=1+a4 h=1+ab2 i=1+ae
j=1+a2d k=1+a3c l=1+abd m=1+a2f n=1+acd o=1+a3b2 p=1+ak q=1+a5b
r=1+a2c2 s=1+am t=1+ab2d u=1+abi v=1+ap w=1+a2l x=1+abce y=1+a5e
z=1+a2t A=1+a3bc2 B=1+a7c C=1+agh D=1+a2bn E=1+a7b2 F=1+abck
G=1+a5bf H=1+aB I=1+aceg J=1+a3bc3 K=1+abA L=1+abD M=1+abcx N=1+acG
O=1+aqs P=1+aqy Q=1+abrv R=1+ad2eK S=1+a3bCL T=1+a2bewM U=1+aijsJ
V=1+auEP W=1+agIR X=1+a2bV Y=1+a2cW Z=1+ab3oHOT !=1+a3SUX @=1+abNY!
#=1+a4kzF@ $=1+a3QZ#
Note: numeral after variable names represent powers. For example,
f = 1 + a2b = 1 + 2^2 * 3 = 13.
The last variable, $, is the order of the base point, and the order
of the curve is 72$.
Note: Punctuation used for variable names !,@,#,$, would not scale
for larger primes. For larger primes, a similar format might work
by using a prefix-free set of multi-letter variable names.
E.g. replace, Z,!,@,#,$ by Za,Zb,Zc,Zd,Ze:
Acknowledgments
Thanks to John Goyo and various other BlackBerry employees for past
technical review, to Gaelle Martin-Cocher for encouraging submission
of this I-D. Thanks to David Jacobson for sending Pratt primality
certificates.
Brown 2y^2=x^3+x over 8^91+5 [Page 44]
Internet-Draft 2019-10-03
Author's Address
Dan Brown
4701 Tahoe Blvd.
BlackBerry, 5th Floor
Mississauga, ON
Canada
danibrown@blackberry.com
Brown 2y^2=x^3+x over 8^91+5 [Page 45]
```