```
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.
Brown 2y^2=x^3+x over 8^91+5 [Page 20]
Internet-Draft 2019-04-04
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.
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.
Brown 2y^2=x^3+x over 8^91+5 [Page 21]
Internet-Draft 2019-04-04
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.
- 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:
Brown 2y^2=x^3+x over 8^91+5 [Page 22]
Internet-Draft 2019-04-04
``````
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:
``````
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.
Brown 2y^2=x^3+x over 8^91+5 [Page 23]
Internet-Draft 2019-04-04
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).
``````
#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.
Brown 2y^2=x^3+x over 8^91+5 [Page 24]
Internet-Draft 2019-04-04
- 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.
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).
Brown 2y^2=x^3+x over 8^91+5 [Page 25]
Internet-Draft 2019-04-04
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:
``````
#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 26]
Internet-Draft 2019-04-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 27]
Internet-Draft 2019-04-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 28]
Internet-Draft 2019-04-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
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 two primes involved for 2y^2=x^3+x/GF(8^91+5) should already
resist [AMPS] because compact representation of these primes.
For further assurance, this section provides Pratt primality
certificates for the two primes.
Note: Recall that every prime p has a unique Pratt certificate,
which consists of the factorization of p into primes, and,
recursively, Pratt primality certificates for each of those
primes. Verification of a Pratt certificates is also recursive:
it uses the factorization data to conduct Fermat and Lehmer
tests, which together verify primality.
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: Writing % for modular reduction (with lower precedence than
exponentiation ^), a first step in verifying the Pratt certificate
is a Fermat pseudoprime test for each prime in the list, meaning
the all the numbers below are 1:
Brown 2y^2=x^3+x over 8^91+5 [Page 29]
Internet-Draft 2019-04-04
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.
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.
Note: A second step to verifying a Pratt certificate is to apply
Lehmer's theorem to each Fermat psuedoprime. To prove b,c,d,...,Z
are prime, it now suffices to verify that all of following 154
modular exponentiations result in a value different from 1.
Brown 2y^2=x^3+x over 8^91+5 [Page 30]
Internet-Draft 2019-04-04
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.
Note: The verifier should verify that each base in the Fermat and
Lehmer test are equal. For example, the Fermat base for Z was 7,
and the factorization of Z-1 was aabzUVY, so the Lehmer theorem
test 7^((Z-1)/a)%Z, 7^((Z-1)/b)%Z, ..., 7^((Z-1)/Y)%Z.
Note: The final step is to verify that Z=8^91+5.
Brown 2y^2=x^3+x over 8^91+5 [Page 31]
Internet-Draft 2019-04-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.
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.
Note: The same process (Fermat and Lehmer tests) verifies that $
is prime. This process includes search for bases for each of the
prime. These bases have not been included in the certificate.
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 multil-letter variable names.
E.g. replace, Z,!,@,#,$ by Za,Zb,Zc,Zd,Ze:
Brown 2y^2=x^3+x over 8^91+5 [Page 32]
Internet-Draft 2019-04-04
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 Za=1+ab3oHOT Zb=1+a3SUX
Zc=1+abNYZb Zd=1+a4kzFZc Ze=1+a3QZaZd
When parsing this, say 2nd last item Zd=1+a4kzFZc, the string Zd on
the left of = defines a new variables, while the string on the
right = gives its value. The string a4kzFZc can be unambiguously
parsed as a^4*k*z*F*Zc, scanning from left to right for previous
variables, or integers as powers.
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.
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 33]
```