1 /*
2 * In: b = 2^5 - 2^0
3 * Out: b = 2^250 - 2^0
4 */
5 static void
curve25519_pow_two5mtwo0_two250mtwo0(bignum25519 b)6 curve25519_pow_two5mtwo0_two250mtwo0(bignum25519 b) {
7 bignum25519 ALIGN(16) t0,c;
8
9 /* 2^5 - 2^0 */ /* b */
10 /* 2^10 - 2^5 */ curve25519_square_times(t0, b, 5);
11 /* 2^10 - 2^0 */ curve25519_mul(b, t0, b);
12 /* 2^20 - 2^10 */ curve25519_square_times(t0, b, 10);
13 /* 2^20 - 2^0 */ curve25519_mul(c, t0, b);
14 /* 2^40 - 2^20 */ curve25519_square_times(t0, c, 20);
15 /* 2^40 - 2^0 */ curve25519_mul(t0, t0, c);
16 /* 2^50 - 2^10 */ curve25519_square_times(t0, t0, 10);
17 /* 2^50 - 2^0 */ curve25519_mul(b, t0, b);
18 /* 2^100 - 2^50 */ curve25519_square_times(t0, b, 50);
19 /* 2^100 - 2^0 */ curve25519_mul(c, t0, b);
20 /* 2^200 - 2^100 */ curve25519_square_times(t0, c, 100);
21 /* 2^200 - 2^0 */ curve25519_mul(t0, t0, c);
22 /* 2^250 - 2^50 */ curve25519_square_times(t0, t0, 50);
23 /* 2^250 - 2^0 */ curve25519_mul(b, t0, b);
24 }
25
26 /*
27 * z^(p - 2) = z(2^255 - 21)
28 */
29 static void
curve25519_recip(bignum25519 out,const bignum25519 z)30 curve25519_recip(bignum25519 out, const bignum25519 z) {
31 bignum25519 ALIGN(16) a,t0,b;
32
33 /* 2 */ curve25519_square(a, z); /* a = 2 */
34 /* 8 */ curve25519_square_times(t0, a, 2);
35 /* 9 */ curve25519_mul(b, t0, z); /* b = 9 */
36 /* 11 */ curve25519_mul(a, b, a); /* a = 11 */
37 /* 22 */ curve25519_square(t0, a);
38 /* 2^5 - 2^0 = 31 */ curve25519_mul(b, t0, b);
39 /* 2^250 - 2^0 */ curve25519_pow_two5mtwo0_two250mtwo0(b);
40 /* 2^255 - 2^5 */ curve25519_square_times(b, b, 5);
41 /* 2^255 - 21 */ curve25519_mul(out, b, a);
42 }
43
44