```
bite(c b,f x) {
i j=34,k=5; f t;
mal(t,-1,x);
mal(x,cmp(t,x),x);
fix(x);
for(;j--;) b[j]=x[j/7]>>((8*j)%55);
for(;--k;) b[7*k-1]+=x[k]<<(8-k);
}
``````
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,
- 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.
Brown 2y^2=x^3+x over 8^91+5 [Page 21]
Internet-Draft 2018-10-04
Note: Encoding should not be confused with encryption. Encoding
is merely a conversion or representation process, whose inverse is
called decoding.
C.2. Byte decoding
Pseudocode for decoding is:
``````
feed(f x,c b) {
i j=34;
mal(x,0,x);
for(;j--;) x[j/7]+=((i)b[j])<<((8*j)%55);
fix(x);
}
``````
with similar conventions as used in the pseudocode function bite
(defined in the section on encoding), and some extra conventions:
- 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.3. Fermat inversion
Projective coordinates help avoid costly inversion steps during
scalar multiplication.
Projective coordinates are not suitable as the final representation
of an elliptic curve point, for two reasons.
- Projective coordinates for a point are generally not unique: each
point can be represented in projective coordinates in multiple
different ways. So, projective coordinates are unsuitable for
finalizing a shared secret, because the two parties computing the
shared secret point may end up with different projective
coordinates.
Brown 2y^2=x^3+x over 8^91+5 [Page 22]
Internet-Draft 2018-10-04
- Projective coordinates have been shown to leak information about
the scalar multiplier [PSM], which could be the private
key. It would be unacceptable for a public key to leak
information about the private key. In digital signatures, even a
few leaked bits can be fatal, over a few signatures
[Bleichenbacher].
Therefore, the final computation of an elliptic curve point, after
scalar multiplication, should translate the point to a unique
representation, such as the affine coordinates described in this
report.
For example, when using a Montgomery ladder, scalar multiplication
yields a representation (X:Z) of the point in projective
coordinates. Its x-coordinate is then x=X/Z, which can be computed
by computing the 1/Z and then multiplying by X.
The safest, most prudent way to compute 1/Z is to use a side-channel
resistant method, in particular at least, a constant-time method.
This reduces the risk of leaking information about Z, which might in
turn leak information about X or the scalar multiplier. Fermat
inversion, computation of Z^(p-2) mod p, is one method to compute
the inverse in constant time (if the inverse exists).
Pseudocode for Fermat inversion is:
``````
i inv(f y,f x) {
i j=272;f z;
squ(z,x);
mul(y,x,z);
for(;j--;) squ(z,z);
mul(y,z,y);
return !!cmp(y,(f){});
}
``````
Other inversion techniques, such as the binary extended GCD, may be
faster, but generally run in variable-time.
When field elements are sometimes secret keys, using a variable-time
algorithm risk leaking these secrets, and defeating security.
C.4. Branchless Legendre symbol computation
Pseudocode for branchlessly computing if a field element x has a
square root:
Brown 2y^2=x^3+x over 8^91+5 [Page 23]
Internet-Draft 2018-10-04
``````
i has_root(f x) {
i j=270;f y,z;
squ(y,x);squ(z,y);
for(;j--;)squ(z,z);
mul(y,y,z);
return 0==cmp(y,(f){1});
}
``````
Note: Legendre symbol is usually most appropriately applied to
public keys, which mostly obviates the need for side-channel
resistance. In this case, the implementer can use quadratic
reciprocity for greater speed.
C.5. Field multiplication and squaring
To be completed.
Note (on security): Field multiplication can be achieved most
quickly by using hardware integer multiplication circuits. It is
critical that those circuits have no bugs or backdoors.
Furthermore, those circuits typically can only multiple integers
smaller than the field elements. Larger inputs to the circuits
will cause overflows. It is critical to avoid these overflows,
not just to avoid interoperability failures, but also to avoid
attacks where the attackers supplies inputs likely induce
overflows [bug attacks], [IT]. The following pseudocode
should therefore be considered only for illustrative purposes.
The implementer is responsible for ensuring that inputs cannot
cause overflows or bugs.
The pseudocode below for multiplying and squaring: uses unrolled
loops for efficiency, uses refactoring for source code compression,
relies on a compiler optimizer to detect common sub-expressions (in
squaring).
Brown 2y^2=x^3+x over 8^91+5 [Page 24]
Internet-Draft 2018-10-04
``````
#define TRI(m,_)\
zz[0]=m(0,0)_(1,4)_(2,3)_(3,2)_(4,1);\
zz[1]=m(0,1)_(1,0)_(2,4)_(3,3)_(4,2);\
zz[2]=m(0,2)_(1,1)_(2,0)_(3,4)_(4,3);\
zz[3]=m(0,3)_(1,2)_(2,1)_(3,0)_(4,4);\
zz[4]=m(0,4)_(1,3)_(2,2)_(3,1)_(4,0);
#define CYC(M) ff zz; TRI(+M,-20*M); mod(z,zz);
#define MUL(j,k) x[j]*(ii)y[k]
#define SQR(j,k) x[j]*(ii)x[k]
#define SQU(j,k) SQR(j>k?j:k,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.
- 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?
C.6. Field element partial reduction
To be completed.
Brown 2y^2=x^3+x over 8^91+5 [Page 25]
Internet-Draft 2018-10-04
The function mod used by pseudocode function mul and squ above is
defined below.
```
#define QUO(x)(x>>55)
#define MOD(x)(x&((((i)1)<<5)-1))
#define Q(j) QUO(QUO(zz[j]))
#define P(j) MOD(QUO(zz[j]))
#define R(j) MOD(zz[j])
mod(f z,ff zz){
z[0]=R(0)-P(4)*20-Q(3)*20;
z[1]=R(1)-P(0)-Q(4)*20;
z[2]=R(2)-P(1)-Q(0);
z[3]=R(3)-P(2)-Q(1);
z[4]=R(4)-P(3)-Q(2);
z[1]+=QUO(z[0]);
z[0]=MOD(z[0]);
}
``````
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).
C.7. Field element final reduction
To be completed.
The partial reduction technique is sometimes known as lazy
reduction. It is an optimization technique. It aims to do only
enough calculation to avoid overflow errors.
For interoperability, field elements need to be fully reduced,
because partial reduction means the elements still have multiple
different representations.
Pseudocode that aims for final reduction is the following:
Brown 2y^2=x^3+x over 8^91+5 [Page 26]
Internet-Draft 2018-10-04
``````
#define FIX(j,r,k) {q=x[j]>>r;\
x[j]-=q<
```>53;
}
```
C.8. Scalar point multiplication
Work in progress.
A recommended method of scalar point multiplication is the
Montgomery ladder. However, the curve 2y^2=x^3+x has an efficient
endomorphism. So, this can be used to speed-up scalar point
multiplication, as suggested by Gallant, Lambert and Vanstone.
Combining both GLV and Montgomery is also possible, such as
suggested as by Bernstein.
Note: The following pseudocode is not entirely consistent with
previous pseudocode examples.
Note and Warning: The following pseudocode uses secret indices to
access (small) arrays. This has a risk of cache-timing attacks.
Brown 2y^2=x^3+x over 8^91+5 [Page 27]
Internet-Draft 2018-10-04
``````
typedef f p[2];
typedef struct rung {i x0; i x1; i y; i z;} k[137];
monty_2d (f ps,k sk,f px) {
i j,h; f z; p w[3],x[3],y[2]={{{},{1}}},z[2];
fix(px);mal(y[0][0],1,px);
endomorphism_1_plus_i(z[0],px);
endo_i(y[1],y[0]); endo_i(z[1],z[0]);
copy(x[1],y[0]); copy(x[2],z[0]);
double_xz(x[0],y[0]);
for(j=0;j<137;j+=){
double_xz(w[0], x[sk[j].x0 /* cache attack here? */ ]);
diff_add (w[1],x[1],x[sk[j].x1],y[sk[j].y]);
diff_add (2[2],x[2],x[0], z[sk[j].z]);
for(h=0;h<3;h++) {copy(x[h],w[h]);}
}
inv(ps,x[1][1]);
mul(ps,x[1][0],ps);
fix(ps);
}
``````
Note: The pseudocode uses some other functions not defined here,
but whose meaning can be inferred by ECC experts.
Note: The pseudocode uses a specialized format for the scalar.
Normal scalars would have to be re-coded into this format, and
re-coding has non-negligible run-time. Perhaps in
Diffie--Hellman, re-coding is not necessary if one can ensure that
uniformly selection of coded scalars is not a security risk.
TO DO:
- Define the functions used by monty_2d.
- Prove that these function avoid overflow.
- Define functions to re-code scalars for monty_2d.
C.9. Diffie--Hellman pseudocode
To be completed.
This pseudocode would show how to use to scalar multiplication,
combined with point validation, and so on.
C.10. Elligator i
To be completed.
Brown 2y^2=x^3+x over 8^91+5 [Page 28]
Internet-Draft 2018-10-04
This pseudocode would show how to implement to the Elligator i map
from byte strings to points.
Pseudocode (to be verified):
``````
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 29]
Internet-Draft 2018-10-04
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
In most cases, probablistic primality tests, if conducted properly,
can ensure more than adequate security. But recent work of Albrecht
and others [AMPS] has shown the combination of adversarially chosen
prime and improper probabilistic primality tests can result in
attacks.
Three countermeasures to the attacks in [AMPS] are (1) using proper
probabilistic prime tests, (2) using provable prime tests, and (3)
using nothing-up-my-sleeve primes which seem immune to the [AMPS]
attack.
It seems that field size 8^91+5 should already resist [AMPS] based
on the third countermeasure (its especially compact representation).
This document cannot really accomplish the first countermeasure,
because the first countermeasure requires fresh randomness for each
test. This document can help with the second countermeasure by
providing primality certificate.
A primality certificate is essentially a rapidly verifiable proof of
primality. More precisely, it involves some rigorous logic and and
some calculations. The calculations, although too tedious to be
done by hand, have a cost that is polynomial time, and usually
amounting only to some number of modular expontiations, with the
number comparable to the bit length of the prime being tested.
Typically, generation of the primality certificate is much more
costly than verifying it: generation is not polynomial-time. For
example, Pratt certificates require the factorization of p-1, which
is typically expensive for large primes. Nevertheless, for the
prime 8^91+5, software exists that can generate a Pratt certificate
in minutes on a personal computer. Yet other kinds of primality
certificates (those using elliptic curves) can be generated even
more quickly, except their verification requires an elliptic curve
implementation, and uses less elementary rigor in their proofs.
For these reasons, a primality certificate for primes of size 8^91+5
is nearly redundant. Nonetheless, it does not hurt to provide the
proofs within this curve, if only for completeness.
D.1 Pratt certificate for the field size 8^91+5
Brown 2y^2=x^3+x over 8^91+5 [Page 30]
Internet-Draft 2018-10-04
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 concatentation is used to indicate multiplication.
For example, f = 1+aab = 1+2*2*(1+2) = 13. This brevity was only
possible by a fluke: only 52 integers were needed, obviating the
need for multi-letter variable names.
Note: the information above can suffice as a Pratt certificate for
the primality of Z, but only if the following further sequence of
computations are done. (The information suffices because it
deducibly implies the sequence of computations.)
Writing % for modular reduction (with lower precedence than
exponention ^), verify that following 51 modular exponentiations all
result in value 1:
2^(b-1)%b, 2^(c-1)%c, 3^(d-1)%d, 2^(e-1)%e, 2^(f-1)%f, 3^(g-1)%g,
2^(h-1)%h, 5^(i-1)%i, 6^(j-1)%j, 3^(k-1)%k, 2^(l-1)%l, 3^(m-1)%m,
2^(n-1)%n, 5^(o-1)%o, 2^(p-1)%p, 3^(q-1)%q, 6^(r-1)%r, 2^(s-1)%s,
2^(t-1)%t, 6^(u-1)%u, 7^(v-1)%v, 2^(w-1)%w, 2^(x-1)%x, 14^(y-1)%y,
3^(z-1)%z, 5^(A-1)%A, 3^(B-1)%B, 7^(C-1)%C, 3^(D-1)%D, 7^(E-1)%E,
5^(F-1)%F, 2^(G-1)%G, 2^(H-1)%H, 2^(I-1)%I, 3^(J-1)%J, 2^(K-1)%K,
2^(L-1)%L, 10^(M-1)%M, 5^(N-1)%N, 10^(O-1)%O, 2^(P-1)%P,
10^(Q-1)%Q, 6^(R-1)%R, 7^(S-1)%S, 5^(T-1)%T, 3^(U-1)%U, 5^(V-1)%V,
2^(W-1)%W, 2^(X-1)%X, 3^(Y-1)%Y, 7^(Z-1)%Z.
This shows that b,c,...,Z are Fermat pseudoprimes to the Fermat
bases indicated (for example, Z is a Fermat pseudoprime to Fermat
base 7).
Note: Each Fermat base above was chosen as the minimal possible
value. These bases can be deduced from b,c,...,Z by searching
bases 2,3,4,... until a Fermat is found. The results of these
search are included above for convenience.
Verify that a is prime (because it is just two).
Brown 2y^2=x^3+x over 8^91+5 [Page 31]
Internet-Draft 2018-10-04
Lehmer's theorem provides the Lehmer test that a Fermat pseudoprime
is prime: if the Fermat base raised to each integer power of the
form (pseudoprime-1)/(a prime factor) is not congruent to 1 modulo
the pseudoprime. Consequently, to prove b,c,d,...,Z are prime, it
suffices to do all the necessary Lehmer tests, which means to verify
that all of following 154 modular exponentiations result in a value
different from 1.
2^((b-1)/a)%b, 2^((c-1)/a)%c, 3^((d-1)/a)%d, 3^((d-1)/b)%d,
2^((e-1)/a)%e, 2^((e-1)/c)%e, 3^((f-1)/a)%f, 3^((f-1)/b)%f,
3^((g-1)/a)%g, 2^((h-1)/a)%h, 2^((h-1)/b)%h, 5^((i-1)/a)%i,
5^((i-1)/e)%i, 6^((j-1)/a)%j, 6^((j-1)/c)%j, 3^((k-1)/a)%k,
2^((l-1)/a)%l, 2^((l-1)/f)%l, 3^((m-1)/a)%m, 3^((m-1)/b)%m,
3^((m-1)/f)%m, 2^((n-1)/a)%n, 2^((n-1)/c)%n, 5^((o-1)/a)%o,
5^((o-1)/b)%o, 5^((o-1)/f)%o, 2^((p-1)/a)%p, 2^((p-1)/l)%p,
3^((q-1)/a)%q, 3^((q-1)/g)%q, 6^((r-1)/a)%r, 6^((r-1)/a)%r,
2^((s-1)/a)%s, 2^((s-1)/b)%s, 2^((t-1)/a)%t, 2^((t-1)/k)%t,
6^((u-1)/a)%u, 6^((u-1)/b)%u, 6^((u-1)/c)%u, 7^((v-1)/a)%v,
7^((v-1)/c)%v, 7^((v-1)/k)%v, 2^((w-1)/a)%w, 2^((w-1)/s)%w,
2^((x-1)/a)%x, 2^((x-1)/b)%x, 2^((x-1)/i)%x, 14^((y-1)/a)%y,
14^((y-1)/c)%y, 14^((y-1)/o)%y, 3^((z-1)/a)%z, 3^((z-1)/b)%z,
3^((z-1)/u)%z, 5^((A-1)/a)%A, 5^((A-1)/t)%A, 3^((B-1)/a)%B,
3^((B-1)/d)%B, 3^((B-1)/h)%B, 7^((C-1)/a)%C, 7^((C-1)/c)%C,
7^((C-1)/u)%C, 3^((D-1)/a)%D, 3^((D-1)/v)%D, 7^((E-1)/a)%E,
7^((E-1)/e)%E, 7^((E-1)/f)%E, 5^((F-1)/a)%F, 5^((F-1)/A)%F,
2^((G-1)/a)%G, 2^((G-1)/B)%G, 2^((H-1)/a)%H, 2^((H-1)/D)%H,
2^((I-1)/a)%I, 2^((I-1)/c)%I, 2^((I-1)/x)%I, 3^((J-1)/a)%J,
3^((J-1)/c)%J, 3^((J-1)/e)%J, 3^((J-1)/j)%J, 2^((K-1)/a)%K,
2^((K-1)/b)%K, 2^((K-1)/q)%K, 2^((K-1)/r)%K, 2^((L-1)/a)%L,
2^((L-1)/b)%L, 2^((L-1)/J)%L, 10^((M-1)/a)%M, 10^((M-1)/b)%M,
10^((M-1)/d)%M, 10^((M-1)/t)%M, 5^((N-1)/a)%N, 5^((N-1)/b)%N,
5^((N-1)/d)%N, 5^((N-1)/p)%N, 5^((N-1)/w)%N, 10^((O-1)/a)%O,
10^((O-1)/b)%O, 10^((O-1)/m)%O, 10^((O-1)/C)%O, 2^((P-1)/a)%P,
2^((P-1)/b)%P, 2^((P-1)/e)%P, 2^((P-1)/K)%P, 10^((Q-1)/a)%Q,
10^((Q-1)/b)%Q, 10^((Q-1)/c)%Q, 10^((Q-1)/f)%Q, 10^((Q-1)/g)%Q,
10^((Q-1)/E)%Q, 6^((R-1)/a)%R, 6^((R-1)/b)%R, 6^((R-1)/P)%R,
7^((S-1)/a)%S, 7^((S-1)/b)%S, 7^((S-1)/c)%S, 7^((S-1)/M)%S,
5^((T-1)/a)%T, 5^((T-1)/I)%T, 5^((T-1)/O)%T, 3^((U-1)/a)%U,
3^((U-1)/d)%U, 3^((U-1)/u)%U, 3^((U-1)/G)%U, 3^((U-1)/S)%U,
5^((V-1)/a)%V, 5^((V-1)/b)%V, 5^((V-1)/n)%V, 5^((V-1)/u)%V,
5^((V-1)/H)%V, 5^((V-1)/T)%V, 2^((W-1)/a)%W, 2^((W-1)/b)%W,
2^((W-1)/f)%W, 2^((W-1)/L)%W, 2^((W-1)/N)%W, 2^((W-1)/Q)%W,
2^((W-1)/R)%W, 2^((X-1)/a)%X, 2^((X-1)/f)%X, 2^((X-1)/F)%X,
2^((X-1)/W)%X, 3^((Y-1)/a)%Y, 3^((Y-1)/u)%Y, 3^((Y-1)/X)%Y,
7^((Z-1)/a)%Z, 7^((Z-1)/b)%Z, 7^((Z-1)/z)%Z, 7^((Z-1)/U)%Z,
7^((Z-1)/V)%Z, 7^((Z-1)/Y)%Z.
Brown 2y^2=x^3+x over 8^91+5 [Page 32]
Internet-Draft 2018-10-04
Note: Each base above is the same as the base in the previous
Fermat pseudoprime stage, and each list of prime factors is
deduced from the definition of positive integers b,c,...,Z. The
consistency between these stages of the proof must be verified for
rigor. For example, the Fermat base for Z was 7, and the
factorization of Z-1 was aabzUVY, so we must test 7^((Z-1)/a)%Z,
7^((Z-1)/b)%Z, ..., 7^((Z-1)/Y)%Z.
This proves that a,b,...,Z are primes.
Verify that Z=8^91+5 to conclude that 8^91+5 is prime.
Note: the Pratt certificate is essentially unique for each prime.
The presentation above is for illustrative purposes: the
formatting is not intended for an automated verification. A
sensible automation of the verification would simply generate the
154 Lehmer tests from integer definitions and the Fermat
pseudoprime tests, rather than rely on the listing provided above.
With only slightly greater cost, the Fermat pseudoprime test can
be derived from integers, by a separate search for each Fermat
base.
Note: A reader who wishes to verify, with greatest certainty, that
8^91+5 is prime, would be probably be most convinced by running a
provable prime test entirely independent of this document and the
primality certificate given in this section.
Note: the most expensive step in generating the Pratt certificate
for 8^91+5 was factoring the integer 8^91+4 = Z-1 = aabzUVY. The
other integers were generated in reverse alphabetical order, as
Y,X,...,c,b,a, with each integer appearing as an (seemingly) prime
factor of one less than number previously computed. All
subsequent integer factorizations took time negligible compared to
the factorization of Z-1.
Brown 2y^2=x^3+x over 8^91+5 [Page 33]
Internet-Draft 2018-10-04
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. If the reader has a
tool to generate a Pratt certificate (with decimal notation), the
reader should be able to find these numbers in the Pratt
certifcate for 8^91+5. (Since Pratt certificate generation is
slower than for other primality certificate types, some tools
require special configuration to generate a Pratt certificate.)
Note: the Pratt certificate for 8^91+5 might not be shortest
possible primality certificate (under some measure of length), but
optimizing the shortness of a primality certificate seems to add
little value.
D.2 Pratt certificate for size of the large elliptic curve subgroup
Using the same verification strategy of the previous strategy, but
now with 56 variables a,b,...,z,A,B,...,Z,!,@,#,$, with new
definitions:
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.
Note: The use of punctuation for variable names !,@,#,$, does not
scale (or fit into most programming languages), so is really just
a hack to avoid a multiplication operator.
A routine but tedious verification (Fermat and Lehmer tests)
converts the information above into a proof that $ is prime. (The
information above, obtained by repeated factorization, is also
routine, but more computatinally expensive, because it involves
integer factorization.)
Brown 2y^2=x^3+x over 8^91+5 [Page 34]
Internet-Draft 2018-10-04
The last variable, $, is the order of the base point, and the order
of the curve is 72$.
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 me
Pratt primality certificates (generated with mathetmatic, and
re-generated by me).
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 35]
```