5 |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
7 Write p=2^255-19; q=floor(h/p).
8 Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).
11 Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4.
12 Also have |h-2^230 h9|<2^231 so |19 2^(-255)(h-2^230 h9)|<1/4.
14 Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).
18 Have 0<=r<=p-1=2^255-20.
19 Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1.
21 Write x=r+19(2^-255)r+y.
22 Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q.
24 Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1))
25 so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q.
28 void fe_tobytes(unsigned char *s
,const fe h
)
30 crypto_int32 h0
= h
[0];
31 crypto_int32 h1
= h
[1];
32 crypto_int32 h2
= h
[2];
33 crypto_int32 h3
= h
[3];
34 crypto_int32 h4
= h
[4];
35 crypto_int32 h5
= h
[5];
36 crypto_int32 h6
= h
[6];
37 crypto_int32 h7
= h
[7];
38 crypto_int32 h8
= h
[8];
39 crypto_int32 h9
= h
[9];
52 q
= (19 * h9
+ (((crypto_int32
) 1) << 24)) >> 25;
64 /* Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20. */
66 /* Goal: Output h-2^255 q, which is between 0 and 2^255-20. */
68 carry0
= h0
>> 26; h1
+= carry0
; h0
-= carry0
<< 26;
69 carry1
= h1
>> 25; h2
+= carry1
; h1
-= carry1
<< 25;
70 carry2
= h2
>> 26; h3
+= carry2
; h2
-= carry2
<< 26;
71 carry3
= h3
>> 25; h4
+= carry3
; h3
-= carry3
<< 25;
72 carry4
= h4
>> 26; h5
+= carry4
; h4
-= carry4
<< 26;
73 carry5
= h5
>> 25; h6
+= carry5
; h5
-= carry5
<< 25;
74 carry6
= h6
>> 26; h7
+= carry6
; h6
-= carry6
<< 26;
75 carry7
= h7
>> 25; h8
+= carry7
; h7
-= carry7
<< 25;
76 carry8
= h8
>> 26; h9
+= carry8
; h8
-= carry8
<< 26;
77 carry9
= h9
>> 25; h9
-= carry9
<< 25;
81 Goal: Output h0+...+2^255 h10-2^255 q, which is between 0 and 2^255-20.
82 Have h0+...+2^230 h9 between 0 and 2^255-1;
83 evidently 2^255 h10-2^255 q = 0.
84 Goal: Output h0+...+2^230 h9.
90 s
[3] = (h0
>> 24) | (h1
<< 2);
93 s
[6] = (h1
>> 22) | (h2
<< 3);
96 s
[9] = (h2
>> 21) | (h3
<< 5);
99 s
[12] = (h3
>> 19) | (h4
<< 6);
106 s
[19] = (h5
>> 24) | (h6
<< 1);
109 s
[22] = (h6
>> 23) | (h7
<< 3);
112 s
[25] = (h7
>> 21) | (h8
<< 4);
115 s
[28] = (h8
>> 20) | (h9
<< 6);